Zkouska 3.2. Kucera

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkouska 3.2. Kucera

Příspěvek od Ellrohir »

no jo, zajímavej dotaz...to by ses ovšem nesměl ptát mě, kterej byl u Kučery akorát na dvou přednáškách - jedný o Ford-Fulkersonovi a druhý o Dinitzovi :)

ty seš stejně taková anomálie - první člověk za celej den, kterýho se zeptal na něco jinýho než na jednu z pěti otázek, který od rána točil :lol:
Sandro
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 5. 2. 2009 03:22
Typ studia: Informatika Bc.

Re: Zkouska 3.2. Kucera

Příspěvek od Sandro »

Ahoj,
omlouvam se, ze to sem pisu az ted, driv jsem se k tomu nedostal. Asi uz jste sem vse podstatne napsali, presto pro jistotu napisi vsechny otazky, o kterych jsem slysel. Jeste jsem se ale na zkousku moc neucil, takze nektere otazky mozna napisu nesmyslne. :-)

Je to usporadano +- podle toho, jak casto byly jednotlive otazky kladeny. Prvni byla nejcastejsi a posledni 2 byly zadany, myslim, kazda pouze jednou.

- Goldberg: dokazat do jake vysky vystoupa vrchol nejvyse
- Binarni scitani
- Fourierova transformace
- Kolik probehne fazi v Dinicove algoritmu?
- Jak dlouho trva v Dinicove algoritmu 1 faze?
- Dokazani poctu nasycenych/nenasycenych prevedeni v Goldbergove algoritmu
- Goldberg: maximalni pocet prevedeni toku po hranach
- Aho-Corasick: dokazat spravnost
- Aho-Corasick: dokazat slozitost
- Voronoi diagram
- Konvexni obal
- Knuth-Morris-Pratt

+ Doplnujici otazka byla NP uplnost: asi je potreba znat definici + umet prevest na sebe vzajemne 3 SAT, 3-barevnost grafu a nezavislou mnozinu v grafu.

Vlastne mozna stacilo kratce rict, ze se zkouselo uplne vsechno. ;-) Preju hodne stesti pristi utery! :-)
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zkouska 3.2. Kucera

Příspěvek od Him »

Nemate nekdo pls zapisky s FFT a DFT od Kucery? (v textech k algovizi toho moc neni)
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: Zkouska 3.2. Kucera

Příspěvek od Donarus »

sice uz mam po zkousce a DFT FFT jsem neschytal, ale kdyby se ty zapisky nasly, tak bych byl taky vdecny.. rad bych to konecne znal vice, nez jen tak povrchne, jak to znam ted..
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“