zkouška 17.5., MJ

Uživatelský avatar
Yawgmoth
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 17. 5. 2007 20:09
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

zkouška 17.5., MJ

Příspěvek od Yawgmoth »

všech 15 lidí mělo stejné zadání

Příklad A1 (5 bodů). Definujte AVL strom a dokažte, že má hloubku O(log n).

Příklad A2 (10 bodů). Popište Jarníkův algoritmus na hledání minimální kostry grafz a jeho implementaci. Dokažte, že funguje, a rozeberte časovou a paměťovou složitost.

Příklad B1 (5 bodů). Je dán orientovaný rovinný graf na n vrcholech. Popište co nejefektivnější algoritmus, který pro každou dvojici vrcholů (u,v) určí, zda existuje (orientovaná) cesta z u do v. (doplnění - pár lidí to pochopilo tak, že dvojice pro kterou hledáme cestu je na vstupu, ale správně to mělo hledat pro všechny dvojice najednou a vracet matici)

Příklad B2 (5 bodů). Robin Hood se rozhodl, že zastřelí co nejvíce šerifových poskoků jedním šípem. Navrhněte algoritmus, který, jsou-li dány souřadnice poskoků v rovině, nalezne přímku, na níž leží co nejvíce z nich.

Příklad C (5 bodů). Popište algoritmus, který pro danou posloupnost navzájem různých reálných čísel x1,...,xn nalezne její "největší díru", tj. čísla xi<xj taková, že žádné další xk neleží mezi nimi a xj-xi je největší možné. Nápověda: existuje řešení v lineárním čase.

v části A (teoretické) bysme měli vše precizně formulovat a zdůvodnit
v části B (praktické) se můžeme odkazovat na algoritmy a věty z přednášky, aniž bysme je museli odvozovat
část C slouží jako lahůdka pro ty, kdo budou s písemkou dříve hotovi
Ke každému algoritmu patří rozbor správnosti (není-li zjevná) a časové a paměťové složitosti.
Při zkoušce je zapovězeno používat zápisky, kalkulačky, mobily, své kolegy, jakož i jiné pomůcky. Společně vyřešené úlohy jsou bodovány taktéž společně.

(konec téměř doslovného zadání, pár postřehů navíc)

na písemku bylo hodinu a půl, pak půl hodiny opravoval a pak začal zkoušet ústně ... prvních 5 nás dostalo 1, jeden byl i na něco tázán - tuším měl 17 bodů - ostatním snad jen MJ vysvětlil co neměli úplně dokonale
na dvojku by měla stačit jen teorie z přednášek, tj část A.

Hodnotil celkem mírně, např Robin Hood na 4 body stačil v O(n^3) - brutální silou, pro každou dvojici bodů projít všechny ostatní a spočítat kolik leží na přímce .. lze popsat na řádku a hotovo :)
(správně, tj na 5 bodů, to mělo být O(n^2) )

u úlohy B1 strhával bod za nevyužití rovinnosti grafu - správné algoritmy se tváří mít ve složitosti něco jako mn, ale rovinný graf je řídký, O(mn)=O(n^2)

Snad vám to pomůže pro představu, hodně štěstí na dalších termínech :)
Odpovědět

Zpět na „2006“