Zkouška 29.5. Hric

[Germoe]

1a) Floyd-Warshallův algoritmus, invariant, důkaz platnosti algoritmu
b) Zda jde využít jen jedné matice délek a výsledky průběžně přepisovat
2a) Dokázat substituční metodou že T(n)=T(n/4)+T(3n/4)+bn ~ THETA(n log n)
b) Pomocí MT složitost T(n)=6 T(n/3) + O(n^2)
3a) Zda je vypouštění z AVL stromu komutativní
b) Spočítat pro jednotlivé hloubky maximální počet nefalešných (=nepočítáme listy) vrcholů, je-li černá hloubka 4

[Turista]

Tak se učím na zkoušku, a zjišťuju, že je toho nějak strašně moc - opravdu se na Hrice vyplatí učit všechny ty důkazy? Například u hašování je jich docela dost...

Na co je dobré se soustředit? Koukám, že master theorem je tam vždycky...

[Germoe]

Tak se učím na zkoušku, a zjišťuju, že je toho nějak strašně moc - opravdu se na Hrice vyplatí učit všechny ty důkazy? Například u hašování je jich docela dost...

Na co je dobré se soustředit? Koukám, že master theorem je tam vždycky...

Až tak moc toho není, jeden nebo dva dny na to stačí...
Myslím, že se vyplatí naučit se ty důkazy (a to i ty, které nás neučil - viz. dnešní Floyd-Warshall) minimálně ti to pomůže u dokazování případné platnosti optimalizací...
Asi všechno Spočítej si pár příkladů na substituci a Master theorem, pořádně se nauč invarianty a důkazy u těch grafových algoritmů... Ověř si, že vymyslíš důkazy u ostatního...

Jinak písemka sice nic moc, ale pak Hric dává body i za to, co tam nenapíšete

[Jan K.]

Hmm, invariant... - co to přesně je u grafového algoritmu? Třeba konkrétně u Floyd Warshalla? Fakt, že cesty nehledá podle délky ale podle toho, přes které vrcholy může jít? (délka nejkratší cesty, jejíž vnitřní vrcholy jsou v nějaké množině?) To je invariant, nebo něco jiného?

[Návštěvník]

Grafove algoritmy jsou dobre vysvetleny zde: http://kam.mff.cuni.cz/~kuba/ka/ka.pdf ...najdes tam i odpoved ohledne invariantu u Floyd Warshalla

[Návštěvník]

Hele jen bych se zeptal co znamena otazka 3a ? a opoved ?
a jeste co je nefalesny vrchol u 3b?
Diky

[Návštěvník]

podivej se tady: http://forum.matfyz.info/viewtopic.php?f=355&t=1818 ...vsechny tve otazky jsou tam zodpovezeny