Fórum studentů MFF UK

Ja jen strucne doplnim, ze sem dostal perfektni hashovani. Fakt sem to moc neumel, takze sem 3 minuty premejslel, jestli to ma vubec cenu, a pak to se cti vzdal.

Jedna prakticka rada: uz o vikendu jsem dost tusil, ze se to nestihnu naucit, ale prosvih jsem termin na odhlaseni ze zkousky. Tak sem mu napsal mail, ale na ten neodpovedel, takze sem si rek, ze to teda zkusim, beztak nemam co ztratit. Kdyz sem se s nim ale bavil, tak jsem pochopil, ze kdybych to mel zapsany, ale vubec tam neprisel nebo mu nejlip rek dopredu, za to vzdavam, tak mi ten termin nepocital.

PS: tri dny je na uceni opravdu malo

Já jsem měl ten A-Sort, takže vám můžu podat přesné svědectví o tom, že na 3ku stačí pár obecných vět (třídící algoritmus vhodný pro předtříděné posloupnosti...), popis algoritmu (klidně svými slovy, hlavně aby to bylo správně, můžete kreslit obrázky a on asi bude jedině rád ) a jeho složitost. Zeptal se mě jenom na to, co myslím tím "předtříděné posloupnosti" a stačila odpověď "počet inverzí ve vstupním poli", což je stejně součástí složitosti algoritmu.

Já doplním, že vedle mě byl člověk, který měl externí hašování. Já jsem měla AVL-stromy. Hodinu jsem psala, napsala jsem odhad na hloubku a všechny případy pro insert a delete. Trvalo mi to asi hodinu, pak si to Koubek 15 minut četl. Vadilo mu, že jsem si v definici hloubky podstromu zapomněla dodefinovat 0 pro prázdný podstrom, jinak si nestěžoval. Můj dojem je, že člověk má tolik času, kolik potřebuje, takže je lepší toho dobře využít a napsat všechno přesně. Nevadí, když použijete jednodušší odhad třeba s horšími konstantami, ale když už něco píšete, tak je to třeba napsat dosti přesně. Jinak Koubek se mi zdál při zkoušení velmi příjemný a nápomocný.

Bylo nás tam 10-15, jeden jenom přišel říct, že na zkoušku nejde , druhý dostal téma univerzální hashování (moje minulé) a se slovy "tak to taky neumím" opustil místnost. Dostal jsem vyhledávání v uspořádáném poli. Krom toho jsem ještě zaslechl A-sort, Fibonacciho haldy a počítání se separovanými řetězci (průměr, maximum atd.).

Moje téma bylo docela v pohodě. Popsal jsem obecný princip, různé metody výpočtu funkce "next" s očekávanými časy a podrobně napsal algoritmus obecného kvadratického vyhledávání (pseudokód). Pak se mě Koubek ještě ptal, proč je očekávaný čas maximálně O(log n) a průměrně O(log log n). O(log n) jsem ukázal konkrétním případem: na posloupnosti typu 1, 2, 3, 4, ..., atd a (hafo strašně moc veliké číslo) jako poslední prvek (A[n] >> A[n-1]) algoritmus degeneruje k normálnímu binárnímu prohledávání. K O(log log n) jsem řekl základní myšlenku, čili že interval, ve kterém se hledá, se zmenšuje s odmocninou. Ukázal jsem, že trvá log log n dlouho, než se odmocňováním dostanu na konstantu (snadný důkaz na 4 řádky) a dál jsem to neuměl, nechtělo se mi to vymýšlet a chtělo se mi na záchod

Takže za dva, spokojenost. Odcházel jsem jako druhý se známkou po hodině a třech čtvrtinách další hodiny, těsně přede mnou byla jednička.