Hric 23.6.

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
vojta_vorel
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 14. 1. 2011 15:10
Typ studia: Informatika Ph.D.

Hric 23.6.

Příspěvek od vojta_vorel »

Pan Hric byl na nás celkem milý, i přesto že nejspíš neměl dobrou náladu.
Otázky byly:
> Dokázat, že ČČ-strom má logaritmickou hloubku, podrobně(!) popsat delete v AVL stromu.
> Dokázat nebo vyvrátit že lehké hrany všech řezů tvoří minimální kostru.
(o mém pokusu pan Hric řekl, že jsem to asi nějak nepochopil, a dál se mě na to neptal, to mi přišlo trochu nefér)
> Odhadnout složitost Jarníka (nevím co přesně chtěl, já udělal verzi s rychlou haldou a verzi s polem)
> Popsat řešení soustavy lin. rovnic, když máme LUP rozklad její matice, odhadnout příslušnou složitost.
(zarazilo mě že tam bylo LUP, na posledních přednáškách jsem nebyl, tak jsem preventivně předpokládal že se to nestihlo :), ale moje postřehy z letmého přelétnutí kapitoly pohledem na to stačily)

O honocení: půlku příkladu jsem měl branou jako blbě, zásadní chybu v tom delete, další nepříjemnou chybu v analýze jarníka, u ústního jsem věděl hledání min. cesty v DAG, úspěšně našel protipříklad k mému deletu a moc se neorientoval v LUP (podrobnosti o funkci a nutnosti matice P). Výsledek 2, myslím že spravedlivá známka.

zdraví vojta
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“