Zkouska 3.2. Kucera

Tak zkouška byla úmorná, přišel jsem v 9:00 a do dvou čekal na otázku a ve čtvrt na čtyři odešel... doporučuju si zjistit, kolikátí budete na řadě podle data narození :roll:
Nu, otázky kolovaly a dědily se ze studenta na studenta, zaregistroval jsem tyto:
Dokázat, že v Goldbergovi má vrchol výšku max. 2N
Dokázat, že Dinitz má max. N fází
Něco o FFT, co to je, jak to je, moc přesně nevím, co chtěl
Binární sčítačka (ten Carry Look Ahead) - vždycky se všichni těšili a pak začal rýpat do důkazů, takže nekončili nijak štastní.
Počet nenasycených převedení v Goldbergovi.

A asi ještě něco, ale už si to nepamatuju :D

Takže přeji hodně štěstí dalším.

Bylo tam i neco, co nebylo odprednaseno?

Ja som mala dokazat zlozitost jednej fazy v Dinitzovi. V podstate v poriadku, ale nieco sa mu tam asi nepacilo, takze za 2. A este k tej FFT, co viem, chcel aj inverznu (!).

dostal jsem dokazat korektnost knuth m.p. ... napsal jsem mu algoritmus a napsal jsem mu dukaz korektnosti pro ten napsany pseudoalgoritmus... nakonec za 2 bo tam ze me pul hodiny tahal neco, co jsem si myslel, ze ze me netaha a tak jsem mu to porad nerikal .. ...

EDIT: tahal to ze me sice pul hodiny, ale predtim jsem tam teda 2 hodiny sedel :D

Donarus: On rikal tenhle dukaz na prednasce nebo jsi se ho ucil odjinud?

to já seděl 7 hodin venku, pak hodinu tam a za 5 minut byl se mnou hotovej, že "tohle na udělání zkoušky opravdu není"...měl jsem tu výšku vrcholu max. 2N...eště sem si to 2x předtím četl a vypadalo to, jak to v pohodě chápu...jenže pak jsem najednou nebyl ani schopnej vyslovit to lemma o spádu natož abych něco korektně (nebo aspoň nekorektně) dokazoval...a kde nic není, tam holt ani Kučera nebere :roll:

ja na prednasky nechodil, takze nevim co rikal a nerikal za dukazy, kazdopadne tenhle jsem si vymyslel :D :D :D :D ... jedine, co jsem pretim vedel je, jak ten algoritmus funguje... pul hodiny jsem si na to vzpominal... pak jsem si dalsi hodinu snazil nejak pseudokodersky zapsat a pak jsem to chtel dokazat, ze je to korektni..

Donarus: tak to uz ses druhej, od kteryho jsem slysel, ze si dukaz vymyslel.. doufam, ze nedopadnu stejne :-D

EDIT: no jo, chybicka se vloudila..

bejt tebou, tak se spíš bojím, že ten důkaz nevymyslím :twisted: jako se to stalo mě... :roll:

Him wrote:Donaurus: ... ... nejsem zadnej "Donaurus" :D :D

Him wrote:Bylo tam i neco, co nebylo odprednaseno?

jeste k tomu se vratim.. bych to spis formuloval takto: "Bylo tam i neco, co bylo odprednaseno?" :)

bylo :P :twisted:

http://kam.mff.cuni.cz/~ludek/NTIN061.html - myslel jsem, jestli tam bylo jen to, co bylo "oficialne" odprednaseno. Jestli se nahodou nemam ucit jeste neco jineho..

takhle - za těch 8 hodin co jsem tam seděl jsem nepotkal nikoho, kdo by si stěžoval na otázku na téma, které nebylo... :wink:

Díky ;-)

no tak mi treba rekni, jestli se delalo dokazovani ke knuthmorrisprattovi.. esli ano, tak se omluvim :D esli ne, tak.... tak se neomluvim :)

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:

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! :-)

Nemate nekdo pls zapisky s FFT a DFT od Kucery? (v textech k algovizi toho moc neni)

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..