# Zkouska 3.2. Kucera

<{ForumPost(poster="Pepicek", timestamp=2009-02-03 16:07:43)}>
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.
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-03 17:19:38)}>
Bylo tam i neco, co nebylo odprednaseno?
<{/ForumPost}>

<{ForumPost(poster="Armi", timestamp=2009-02-03 18:40:02)}>
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 (!).
<{/ForumPost}>

<{ForumPost(poster="Donarus", timestamp=2009-02-03 21:07:06)}>
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
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-03 21:33:08)}>
Donarus: On rikal tenhle dukaz na prednasce nebo jsi se ho ucil odjinud?
<{/ForumPost}>

<{ForumPost(poster="Ellrohir", timestamp=2009-02-03 22:23:46)}>
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:
<{/ForumPost}>

<{ForumPost(poster="Donarus", timestamp=2009-02-03 22:29:38)}>
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..
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-03 22:32:42)}>
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..
<{/ForumPost}>

<{ForumPost(poster="Ellrohir", timestamp=2009-02-03 23:19:03)}>
bejt tebou, tak se spíš bojím, že ten důkaz nevymyslím  :twisted:  jako se to stalo mě... :roll:
<{/ForumPost}>

<{ForumPost(poster="Donarus", timestamp=2009-02-04 01:22:30)}>

 > 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?" :)
<{/ForumPost}>

<{ForumPost(poster="Ellrohir", timestamp=2009-02-04 07:37:11)}>
bylo  :P  :twisted:
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-04 11:04:10)}>
[http://kam.mff.cuni.cz/~ludek/NTIN061.html](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..
<{/ForumPost}>

<{ForumPost(poster="Ellrohir", timestamp=2009-02-04 14:20:03)}>
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:
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-04 14:21:54)}>
Díky ;-)
<{/ForumPost}>

<{ForumPost(poster="Donarus", timestamp=2009-02-04 19:15:33)}>
no tak mi treba rekni, jestli se delalo dokazovani ke knuthmorrisprattovi.. esli ano, tak se omluvim :D esli ne, tak.... tak se neomluvim :)
<{/ForumPost}>

<{ForumPost(poster="Ellrohir", timestamp=2009-02-05 01:04:12)}>
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:
<{/ForumPost}>

<{ForumPost(poster="Sandro", timestamp=2009-02-05 03:57:12)}>
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! :-)
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-05 17:00:17)}>
Nemate nekdo pls zapisky s FFT a DFT od Kucery? (v textech k algovizi toho moc neni)
<{/ForumPost}>

<{ForumPost(poster="Donarus", timestamp=2009-02-05 17:27:44)}>
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..
<{/ForumPost}>