Syntax highlighting of Archiv/Státnice - Informatika - Zkazky / zkušenosti

== Zdroje ==

* Skupina [http://groups.yahoo.com/group/mff-info/ mff-info] na [http://groups.yahoo.com/ Yahoo! Groups] – [http://groups.yahoo.com/group/mff-info/msearch?query=statnice&submit=Search&charset=UTF-8 dotaz na "statnice"]
* [http://mff.modry.cz/diskuse/ Diskuze na modry.cz] – [http://mff.modry.cz/diskuse/index.php?page_id=1&fast_form_sent=1&diskuse_from_page=0&diskuse_select_sekce=44&diskuse_datum_from=&diskuse_datum_to=&diskuse_id_from=&diskuse_id_to=&diskuse_name_rgxp=&diskuse_text_rgxp=&diskuse_per_page=1000&diskuse_nastavit_submit=nastav výběr příspěvků ze sekce "Státnice"]

== Rady a postřehy ==
* '''Opravdu dobre si na fakultnim webu proctete okruhy, ze kterych maji zkouset konkretne vas. Chudak kolega z I1 se ucil datovky s kamaradem podle I2. Nebyla tam dynamizace. Letel :('''
* U volitelné části byste měli znát i něco netriviálního, nejen to, co zná každý IT-ák (''by Petr Tůma''). (Asi to platí, pokud chce člověk hezkou známku, na prolezení toho netriviálního možná není potřeba tolik).
* U povninné části jsem měl dojem, že zkoušející se snaží vybírat vesměs nezákeřné otázky (ovšem záleží na komisi). (Oblíbené jsou NP-úplnost, pseudopolynomiální a aproximační algoritmy, nerozhodnutelné problémy, univerzální hašování.)
* Jeden podbod mého okruhu (v I4) se zdál, že s ostatními nesouvisí a předměty ho nepokrývají. Může se vám zdát, že je to nějaký relikt komisní konstrukce podbodů, a možná to tak je, ale u mého zkoušení se stalo, že přišel dost zvláštní i zkoušejícímu ''a proto'' se na něj zeptal. Mějte tedy připraveno něco ke každé otázce, i když se stává, že se dost často opakují.

== I1 (Teoretická informatika) ==

=== 12. 9. 2014 ===
* '''Slozitost[Petr Kucera[PK]]: Savitchova veta.''' 
Trochu predbehnu - v prubehu zkouseni jsem se zeptal, zda je na pruchod touto otazkou nutno umet vetu dokazat. Odpoved:ano, idea dukazu nestaci. V mych materialech, jsem mel zneni nepresne [s rovnitkem namisto podmnozinitka mezi NSPACE a DSPACE. Rovnost je az ve vztahu NPSPACE a PSPACE]. Trval jsem na rovnitku s tim, ze jedna implikace je trivialni, [PK] si nebyl jisty, ze to takto plati a rekl at teda prejdu rovnou k te druhe implikaci(soudim, ze pro me to byly body dolu). Dukaz jsem delal  [http://en.wikipedia.org/wiki/Savitch's_theorem|tento na eng.Wikipedii]. Nejprve jsem [spatne] zapsal algoritmus tak, ze snizoval delku cesty jen o 1 vrchol v kazdem zanoreni. [PK] nerekl co je spatne, ale chtel hned zanalyzovat prostorovou slozitost. Podrobne az na uroven zda se nacitani vstupu pocita nebo ne. Zde vyplynulo, "ze je neco spatne je" (napr. uz jen proto, ze pokud jen odecitam jednicku, nemusim pouzivat tento algoritmus, ale mohu proste prohledavat stavy do hloubky). V predpokladech jsem mel blbe "f nalezi o(log(n))" namisto "f nalezi male ci velke omega(log(n))". Nevzpominam si presne, ale rozdil (pro "o" vs. "omegy") byl v tom, ze jeden dovoluje prostor potrebny pro vstup stroje predpokladat "zadarmo" u druheho jej musim zapocitat do prost.slozitosti. Nahradil jsem odecitani jednicky pulenim intervalu a spolecne jsme uvarili prostorovou slozitost. Doplnujici otazky: def. prostorove konstruovatelna fce, ktere fce jsou prostorove konstruovatelne - ve smyslu je jich dostatecne (k rozumnemu analyzovani algoritmu)? Mj. jsem povedel, ze "problem maji ty vydatne sublinearni" s cimz [PK] nesouhlasil (log(n) je prostorove konstruovatelna - ale loglog(n) uz ne). Obecne [PK] jde do velkych detailu, zustava mily, dava prostor. Tato otazka byla nejspis za 3. U tohoto zkousejiciho velmi doporucuju pripravit si otazku na papir a precizne, nez povidat spatra o coz jsem se pokousel. 

* '''Vycislitelnost[Petr Gregor]: Algoritmicky nerozhodnutelne problemy. Halting problem.'''
Odrazkami jsem zminil: Postuv korespondencni problem, kachlikovani libovolneho NxN prostoru, rozhodnuti zda slovo bylo vygenerovano danou obecnou gramatikou, Halting problem. Postuv a Halting jsem zadefinoval. Nevedel jsem vsak, jak se u Posta dokazuje nerozhodnutelnost - nevadilo to (ukaze se prevod na vypocet TS (pripadne pomuze Riceova veta - vzata obecne = tj. problem zda nejaka funkce/mnozina ma netrivialni vlastnost je rekurzivne spocetny, netrivialni vlastnosti je zde "schopnost nastrkat za sebe Postovy kosticky"). Dukaz Haltingu velmi nemam rad, vzdy mi dela problem vytlouci na papire kyzeny spor. Chtel jsem se tomu vyhnout - dukaz jsem podrobne povedel slovne, nestacilo to. Prisel [PK]. Mel jsem na papire zminku, ze z toho, ze mnozina K je rekurzivne spocetna se da ukazat efektivni nerozhodnutelnost Halting problemu. Pri povidani o mnozine K jsem "jen tak mimochodem"povedel, ze je 1-uplna a co to znamena, oba panove se zacali ptat. A znicehonic jsme byli u definice 1-prevoditelnosti, kde jsem misto <=> dal jen =>. Tim jsem si zavaril a ukazal ze moc neznam kontext, v jednu chvili jsem si myslel ze mi v definici chybi druha funkce, ktera vraci prvky z cilove mnoziny zpet. Zde jsme se zdrzeli hodne dlouho, nakonec jsem to opravil, ale myslim, ze jsem mel na male. Dukaz Halting problemu jsem s drobnou pomoci p.Gregora dotvoril. Rikal, ze mu to staci, ze me dale trapit nebude, ale jednicka to nebude.
 
* '''Neuronove site[Iveta Mrazova] - Samoorganizujici site a rozebrat Kohonenovy mapy.'''
Vzorec pro uceni a en. funkci, priklad aplikace, popsal jsem LVQ1 a LVQ2, lat.inhibici. Dop.otazky: Je beznou vlastnosti, ze se sit rozvine? Umime to dokazat? (jen pro 1D pripad a spec. pripady 2D. Pro vyssi dimenze ne. Otazky na okoli, jak se meni v case, proc chceme alfa male. Prakticke pouziti. Problemy. Jak nastavit vahy na zacatku (o vlastnich vektorech z PCA jsem nevedel). Velmi prijemne zkouseni.

* '''Umela inteligence[Roman Neruda] - A* a jeho varianty.'''
Popsal jsem A*, heuristiky, fakt, ze monotonni a pripustna "hujeristika" vede k uplnemu a korektnimu alg., priklad s Rumunskem proc hladove-zvol-nejlepsi vede na neuplny algoritmus. IDA* [tak 6 vetama + obrazkem], Hierarchicky A* podrobneji [vyborny zdroj: Lukas Bajer slidy path-finding z um. bytosti H-likeAgents4_Bajer060410.pdf]. Povidani o tom co by se stalo, kdyz "bude heuristika kecat" (nadhodnocujici heuristika muze zdegradovat az k nefunkcnimu best-first searchi).

* '''Agenti[Cyril Brom] - Modely uceni zvirat.'''
Zustal jsem posledni v mistnosti,posledni otazka. Netusil jsem moc, co k tematu patri. Seznamem lehce komentovanych odrazek jsem si pripravil: Imprinting. Habituaci a jeji opak senzitivizaci, Chaining, Pavlovovske podminovani, papouska Alexe. Coz Cyril velmi rychle probehl a zacal se me ptat na rozdil mezi rozdil mezi operativnim podminovanim (B.F. Skinner-symbolicky vzato spojuje symbol a akci) a klasickym podminovanim (I.P.Pavlov-spojuje v mysli dva symboly). Cyril mel hodne hodne otazek (a ne vzdy bylo zrejme, zda jsem odpovedel spravne nebo ne, nebo zda spravna odpoved vubec existuje).
Napriklad pri rozebirani rysu podminovani (kdy prijde podnet, musi to byt bezprostredne pred stimulem? Cyriluv protipriklad zvire, co sezere neco spatneho, prijde na to samo po par hodinach az to vyblije a uz danou vec nesezere. Co kdyz zvireti rano rozsvitim svetlo a odpoledne dam zradlo, spoji si to? A co kdyz stimul prijde az po odmene, bude podminovani fungovat? Jdou podminovat jen vetsi tvorove? (primati, psi, lide, ... ne, napodminovat se da i drozofilie). Jak se treba da naucit pes aby udelal 2 kotrmelce (chainingem). Nakonec reinforcement learning u zvirat a u agentu, otazka co je a kde by se pouzilo Q uceni (jen ustne, zadne vzorce). Zkouseni bylo velmi prijemne, Cyril dost veci vysvetluje. Nemyslim si, ze by vylozene spatna odpoved (nebo jejich snura) vedla do pekla. 

Par obecnych rad:
* Statnice nejsou tresnicka na dortu studia, ale spise takovy dort samotny.
* Ackoli jsou zkousejici veskrze vstricni - nekteri az do levelu "u statnic prece zkousime to, co student umi, nikoli to, co student neumi" (citace) - NEZNAMENA to, ze projdete pokud nemate alespon definice na 100% a k nim obecny prehled. Nespolehejte, ze "uvarite pismenkovy gulas".
* Rozdil mezi jednotlivymi stupni znamek je maly a velmi fuzzy.
* Zda se, ze znamku (resp. prosel neprosel) zasadne udava povinna cast (Slozitost/Vycislitelnost/Datovky). 
* Zkousejici se termin od terminu meni, casto zkouseji "svou" podmnozinu, a nezridka kladou duraz na jine aspekty nez prednasejici.
* Zjistete si, kdo bude v komisi. Muze pomoci zajit si par tydnu pred statnici na konzultaci ke zkousejicim u "problemovych" predmetu.
* Na zkousce nenakusujte oblasti o kterych toho mnoho netusite. Zkousejici se casto snazi "pomoci" tim, ze jde po linii navedene studentem a ocekava hladky prubeh.
* Slozitost II jako predmet proste CHCETE pred statnicema vychodit. Tecka. 
* Naucenou latku si opakovat! Idealne na konci dne probehnout ten den naucene + aspon proletet ocima dosavadni poznamky. Krivka zapominani je mrcha.
* Cas na pripravu?  5tydnu poctiveho (8hod+ denne) uceni s kolegou(Diky Michale!). Zbylo ~5 dnu na opakovani. Presto existovaly otazky, u kterych bych pripadne noreni do detailu neustal. Prosel jsem za 2. Posledni zkousku na MFF jsem mel pred vice nez 2.5 lety, nektere predmety jsem si nechaval uznat jeste z bakalare - o zazitky "jeee UI II, vitej zpet po 6letech" nebyla nouze. Pokud nenacitate predmety "z nuly" muze byt cas na pripravu kratsi. ~3 tydny jsme venovali povinne casti, zbytek odborne + opakovani.
* Russell/Norvig AI modern approach, je uzasne cteni, navic kopiruje prednasky UI/UI 2. Aspon prolistujte relevantni kapitoly!


=== 12. 9. 2014 ===

Zkouška začala paní doc. Mrázovou, která obešla účastníky s tím, že musí jít pryč, tak si máme nejprve zpracovat neuronky...

NN (Mrázová [přisedl si Hric, ale pozdě, tak se na nic neptal]): Perceptron a jeho učení. Nevzpomněl jsem si na důkaz, jen na to, že maximalizuji zlomek v "t" a zároveň mám omezený cosinus. Důkazem mě paní docentka protlačila, občas jsem zahlásil něco jako "jo a tenhle člen má být normovaný", v průběhu se ukázalo, že mám u perceptronu prohozené přičítání/odečítání 1.

Vyčíslitelnost (Kučera P.): Riceova věta. Zeptal jsem se, zda chce i větu o rekurzi, řekl mi že ano, pokud to přes ni budu dokazovat [má ve skriptech jinou možnost]. Napsal jsem tedy větu o rekurzi, Riceovu větu, dokázal ji, zavolal ho, on se na to podíval, zeptal se jestli bych to uměl bez věty o rekurzi (já že ne), ptal se, zda z Riceovy věty můžu říct něco o K (k čemuž jsem odtušil "o tom jsem takhle nikdy nepřemýšlel"). Nakonec to nechal být, že ho to jen
zajímalo...

Umělá inteligence (Neruda a přisedl si Hric): Prohledávací algoritmy obecně a pak povyprávět o svém oblíbeném. Napsal jsem informované, neinformované, více jsem řešil neinformované (proč je DFS špatné, co zase nevyhovuje na BFS, iterativní deepening). Řešili jsme i hill climbing a rozdíl od simulovaného žíhání. Pak nějak došlo na A* ("představte si nějakou zemi... namátkou třeba rumunsko, a jak by to tam vypadalo" "tak v Russelovi je Rumunsko kreslené takto" "aha... ono je i v Russelovi? dalsi knizka s Rumunskem..."), nějak se mi podařilo zamotat do toho, že když nadhodnotím h(x), tak dostanu BestFS.... v tom jsme se chvíli patlali, protože se toto tvrzení Nerudovi s Hricem nezamlouvalo ("tak já to radši nebudu rozpatlávat" "no to už musíte, když jste si s tím začal"), ale nakonec jsme to všichni tři vymysleli :D Nakonec začal Hric mě a Nerudu zkoušet z toho, jestli zname Beam search... neznal jsem, nějak jsem s nápovědami odvodil, co by to mohlo dělat, Hric si povzdechl "To už  se v UI neučí?" a tím jsme uzavřeli UI

Složitost (Koubek): Pravděpodobnostní algoritmy. Večer předtím jsem to načítal a řešili jsme to ve skupině na facebooku, takže jsem naštěstí jel z aktivní paměti. Nakreslil jsem vztahy P, ZPP, RP, coRP, BPP, PP, NP, co-NP a PSPACE, 
namapoval na to Las Vegas, Monte Carlo a Atlantu a napsal, že to jde definovat i přes stroje s hádací páskou. Jako příklady jsem uvedl u LV randomizovaný QuickSort, u MC Fermatův algoritmus a WalkSAT (když už jsem se ho
učil na UI). Chtěl vědět, co Fermatův dělá, tak jsem mu to popsal, on se zeptal, zda je něco lepšího - Rabin Miller, proč? Fermata matou Carmichaelova čísla. Pak mi začal rozporovat definici u BPP, tak jsem mu řekl, že to má ve svých skriptech opačně a takhle to definuje Arora Barak a další zdroje, což vzal. Pak se zeptal znova, jak to má být, tak jsem svedl řeč na to, jaký je rozdíl mezi PP a BPP (BPP tam má konstantu [oproti PP, které tam nemá nic, tedy může dávat výsledek s prstí > 1/2 + 1/2^n], ta konstanta pak umí zařídit to, že když pustím algoritmus víckrát, tak tlačím dolů pravděpodobnost chyby, je na to věta v jeho skriptech). Pak rozebíral randQuickSort, ale to povídal spíše on a semtam dal kontrolní otázku. Této části jsem se bál (jak kvůli zkoušejícímu, tak kvůli otázce), ale nakonec to docela šlo...

Adaptivní agenti (Brom): Navigační pravidla, repre terénu. Klasika, "ne A*". Popsal jsem steering (leč jen překážkový a vyhýbání jiných agentů, už jsem nepopsal navigační steering apod.. ten jsme s Cyrilem dali dohromady). Na papír jsem napsal leccos od Bug algoritmů až po hierarchický A*, ale nakonec jsme víc zůstali v tom steeringu, a konečně jsme řešili, proč je navmesh lepší než waypointy (není to proto, že by ten agent chodil pořád stejně, to bude i tak, ale navmesh se nemusí složitě klikat). Pak už mu to stačilo...

Celkem za 1 (z většiny předmětů 1-2 s tím, že celkově spíš k tomu lepšímu).

=== 12. 9. 2014 ===
Adaptivní agenti (Brom) : Etologické modely, Populační dynamika - trochu jsem se v tom motal, ale věděl jsem nějaké ideje, tak jsme to dali dohromady

NN (Mrázová) : Asociativní sítě (obecně) + do detailu Hopfield a jeden způsob učení - v pohodě, nevěděl jsem důkaz konvergence (jen náznak, že jde o minimalizace E funkce) - stačilo to

UI (Neruda) : Strojové učení, do detailu popsat rozhodovací stromy - úplně v pohodě, popsal jsem ID3 algoritmus a pak jsme si dobře pokecali :).

Složitost (Kučera ml.) : Úplné problémy pro různé třídy - tady padly dva zajímavé dotazy (jiné PSPACE-úplné problémy než TQBF, Existují #P úplné problémy, kterých verze bez mříže je jen v P?). Jinak v pohodě, jen jsem měl trochu problém s definicí NP přes certifikáty. (stačilo bez důkazů, jen jsem naznačil důkaz Cook-Levinovy věty).

* ''poznamka jineho studenta: dalsi PSPACE-uplne problemy existuji (ruzne pocitacove a kombinatoricke hry, v podstate cokoli, kde Vam davam na vyber mezi dvema moznostmi a vy je ani od sebe neumite rozlisit -- to je sila posloupnosti univ. kvantifikatoru). #P-uplny problem, jehoz nepocitaci varianta je v P, je treba maximalni parovani.''

Datovky (Koubek) : Univerzální Hashování - MIT konstrukce bohatě stačila, padly nějaké dotazy na obecné vlastnosti, které chceme od univ. systému, proč to vůbec děláme, jak ˇje to ovlivněné pseudonáhodností místo náhodnosti.

Celkově za 2 (ústní část).

=== 3. 6. 2014 ===

Adaptivni agenti (C.Brom): Navigace ve virtualnim svete (ne A*): je dobre rict steering, navigace od bodu k bodu v navigacnim grafu, mesh a jak navigovat mezi poligovny. Ja jsem pripsal bug algoritmy. OK

Hopfiled model(I.Mrazova): Hopfield model, slusne okno, vsechno co se mi vybavovalo bylo BAM. Horko tezke odlekotane.

Vycislitelnost(P.Kucera): Vlastnosti rekurzivnich a rekurzivne spocetnich mnozin. Dokazal jsem K RS, K' neni RS, K neni R (to se ale nechtelo). Zkouseno operace sjednoceni(i spocetne), prunik, doplnek. OK

UI(Vomlelova): Rozhodovaci stromy, nemel jsem cas na pripravu tak jsem napsal ID3, Information gain vzorecky a pak jsem dostal priklad abych postavit rozhodovaci strom. celkem. Nevedel jsem nejakou doplnovaci otazku. Celkem OK


Datovky(Majerech): Trie(tak to jsem opravdu nechtel). Zakladni jsem dal, prvni komprimaci jsem se s nima trochu hadal, protoze me to prijde uplne blby (videl jsem to jinde definovane jinak, ale asi jenom pro asymptoticke vypocty, protoze tak jak je to v Koubkovy to opravdu dava smysl pro implementaci na realnym pocitaci). Komprimaci do listu mi Majerech vysvetlil, ja jsem o tom neco rekl (no OK to fakt nebylo).

Vysledek 2(spis jsem se bal 4;-)), tak asi i s 1 oknem se da projit, nicmene po par napovedach jsem o vsem neco rekl.

=== 3. 6. 2014 ===

'''Neuronové sítě (Neruda):''' Dostal jsem dokonce na vyber: Hopfield nebo Backprop a metody uceni(zvolil jsem to druhe)

Klasicka otazka a klasicky Neruda. Popsal jsem backprop a ideje tech metod uceni, vzorecky netreba, jen rozumet myslenkam, co se tam deje. Easy.

'''Adaptivní agenti a evoluční algoritmy (Obdržálek):''' Evolučních algoritmy - jak se v nich branit degradaci

Popsal jsem zakladni veci o EA:populace, selekce, krizeni, mutace, kodovani. Jak se branit degradaci me napadal jen elitismus. Jeste se me doptal, co je to vlastne degradace
a zminil, ze se to taky nejak vyuziva(to uz ani nechtel slyset). Prisedici Neruda se jeste ptal, co je explorace a eploatace. Obdrzalek se jeste ptal na aplikace. Pak prekvapive prohlasil, ze mu to staci.

'''Umělá inteligence (Hric):''' Automaticke planovani
Popsal jsem zakladni definice jako plan. domena, operator, akce, atom, .... Zpusoby reprezentace, planovani v prostoru stavu a v prostory planu. Dopredne a zpetne retezeni,
tam se vyptaval na detaily, jak to presne funguje a ktere ma jake vyhody. Celkem pohoda, zadne zakernosti. STRIPS jsem si nemohl vzpomenout, ale ani ho nechtel.

'''Slozitost (Hladik):''' Pseudopolynomialni algoritmy a silna NP-uplnost

Tuhle otazku jsem dostal uz potreti:o) Takze v pohode, napsal jsem definice, tvrzeni a pozorovani, co jsou v Cepkovych slajdech. Ptal se hodne na souvislosti a na priklady.

'''Datové struktury (Koubek):''' Dynamizace

Prekvapive velice v pohode(tyden pred statnicema jsem byl jeste s par dalsimi lidmi na konzultaci, mozna pomohlo, ze si nas pamatoval). Poucen predchozim terminem, dlouho jsem si pripravoval definice a text na papir, az Koubkovi dosla trpelivost a sebral mi prvni popsany papir. Obeslo se to bez vzorecku, chtel jen ideu,
jak funguje semidynamizace a ptal se, aby bylo jasny, ze rozumim algoritmum. Dynamizaci jen precetl, co jsem napsal(a jeste uplne nedopsal) a rekl, ze dobry.

Celkove jsou statnice dost o stesti na otazky, na zkousejici a na doplnujici otazky. Atmosfera celkove byla prijemna a zkousejici se ptali hlavne na souvislosti.

=== 3. 6. 2014 ===

'''Neuronové sítě (Neruda):''' Perceptron & algoritmus zpětného šíření

Klasická otázka, ovšem Neruda nevyžadoval vzorec pro výpočet gradientu, že prý původně nikdo nevěřil, že by to vůbec mohlo jít spočítat a že se to odvodilo až po třiceti letech, takže se není čemu divit, pokud to nevymyslím.

'''Adaptivní agenti a evoluční algoritmy (překvapivě Obdržálek):''' Aplikace evolučních algoritmů

Hodně se vyptával, ale na téhle otázce asi není moc co zkazit.

'''Umělá inteligence (Hric):''' Prohledávání prostoru verzí

Tahle otázka mě docela zaskočila. Pamatoval jsem si pouze že ve slajdech byl nějaký obrázek se stromy, linií oddělující dobré od špatného + jak se to aktualizuje. Hric se hodně vyptával (alespoň jsem si při tom ujasnil, o co vlastně jde), ale stačilo to.

'''Vyčíslitelnost (Gregor):''' Rekurzivní a rekurzivně spočetné množiny

Překvapivě hodně se vyptával, ale spíš jen aby si ověřil, jestli člověk ví, co napsal, nebo jestli se jen náhodou trefil. Důkazy nebyly moc potřeba. Na závěr ještě otázka kolik je rekurzivních, rekurzivně spočetných a ostatních množin.

'''Datové struktury (Koubek):''' Univerzální hašování

Po chvíli psaní mi to vzal a nakoukl (má poslední otázka a zbývali jsme tam poslední dva). Měl jsem tam úvodní povídání, první univerzální systém ze skript, lepší univerzální systém ze skript (vše bez důkazů). Stačilo mu to, jen měl pár kontrolních otázek.

=== 3. 6. 2014 ===

'''UI (Obdržálek - taky jsem se divil):''' A*

+doplňující otázky typu: jak najít nějakou heuristiku? Kde se A* nehodí?

'''Složitost (Koubek):''' Úplné problémy pro různé třídy

Tady je zajímavý poznatek, že se Koubkovi nelíbila definice třídy #P - prej je to špatně. Ale měl jsem to přesně podle Čepokových slidů, asi by se měli kluci domluvit jak to teda je.

'''Datové struktury (Hladík):''' Univerzální hashování

Ukázal jsem tu konstrukci podle videa z MIT. Zajímaly ho jak je to obecněji pro c-univerzální systémy, měl doplňující otázky k velikosti množiny, něco jsem věděl něco ne.

'''Neprocedurální programování (Hric):''' Normální tvar a Church-Roserova vlastnost

Doplňující otázky na to jak je to s norm. formou v typovaných systémech (v některých systémech je to tak, že pokud term má typ, tak potom má normální tvar).

'''Logika a výpočtová složitost (Gregor):''' Věta o úplnosti a věta o kompaktnosti ve VL

Tohle byl docela porod, ale nakonec to prošlo. Důležité je ve větě o kompaktnosti mít "pro každou '''konečnou '''podmnožinu" ...

=== 28. 1. 2014 ===
Stav: 6 lidí(z toho 3 na druhý termín), 2x za jedna, 4x vyhazov:(
Komise: Barták, Koubek, Neruda, Brom, Petr Kučera, Surynek, ???

'''Slozitost(???,Koubek,Petr Kučera)''': Pseudopolynomiální alg., Silná NP-úplnost
Po minulém neúspěchu právě na této otázce jsem si myslel, že už ji umím.
Ovšem jak se ukázalo, nebyla to úplně pravda. Neuměl jsem odpovědět na otázku, jestli je SAT číselný problém, protože jsem nevěděl, jak v něm zadefinovat max(X),
abych to napasoval do tý definice číselnosti. (není číselný a max(X) lze dodefinovat libovolně, třeba jako konstantu).
Pak jsem ještě přidal drobnou chybu v definici NP-těžkosti. Padalo hodně doplňujících otázek na ty pseudopol. alg. a jejich vztah k NPU problemum.
Celkove nakonec 2-.

'''UI (Barták):''' Bayesovské sítě
Tuhle otázku jsem fakt nechtěl, nějak mi na ní nezbyl moc čas. Barták se ze mě ovšem snažil vydolovat maximum, postupně jsem si vzpomněl
na většinu věcí, které byly na přednáškách, tak nakonec to nebyla taková tragédie, ovšem známku nevím.

'''EvA (Neruda):''' Věta o schématech
Až na pár detailů jsem to uměl. V pohodě zkoušení formou povídání. Když jsem náhodou nevěděl, Neruda mi to sám začal dovysvětlovat.

'''Datovky (Koubek):''' Fibonacciho haldy
Další nemilá otázka, navíc jsem podcenil přípravu na papír, kterou Koubek podrobně zkoumal. Čekal jsem, že to doplním během diskuze, ale nedostal jsem moc šanci. Pokud vás bude zkoušet, raději si vezměte víc času na přípravu na papír a pořádně to tam napište. Koubek je puntičkář a nelíbí se mu, když člověk zapomíná předpoklady k tvrzením, apod.
Koubek byl velmi zklamaný, nakonec mi dal 3-, že se mám ještě snažit.

'''Neurony (Surynek):''' Vrstevnaté NS
Klasická otázka, popsal jsem strukturu, jak to funguje, jak se to učí(důkaz nechtěl), energetickou funkci. Hodně se ptal, co by se stalo, když...
Třeba když vyměníme přenosovou funkci(sigmoidu za skokovou)=>nemůžeme použít gradientní metodu, protože ta krajina bude hranatá.
Proč si data rozdělujeme při učení na učící a testovací, apod.
Celkově v pohodě, když člověk rozumí principům, vzorečky nejsou skoro potřeba.

Celkově hlavně kvůli těm Datovkám, ale i Složitosti druhý neúspěšný pokus:(

=== 17. 9. 2013 ===
Komise: Majerech, Čepek, Petr Kučera, Mrázová, Vomlelová, Neruda
První tři zkoušeli povinné předměty a někdy seděli všichni u jednoho studenta(jeden zkouší a dva poslouchají + občas položí dotaz)

'''Datovky (Majerech+Čepek+Petr Kučera):''' Dynamizace, relaxované vyhledávací stromy, samoupravující datové struktury
Dynamizaci jsem věděl, stačilo popsat ty dva způsoby semidynamizace a dynamizaci. Bez důkazů. To se jim celkem líbilo, a protože jsme tím zabili dost času, popsal jsem princip relaxovaných struktur jen stručně. Pak jsme se ještě zasekli u Splay stromů, ptali se, jak se u nich měří složitost, což jsem nějak nebyl schopný zodpovědět, aby s tím byli spokojeni. Zpětně mě napadá jen možnost, že jsem neřekl, že měříme amortizovanou hloubku stromu.

'''UI (Vomlelová):''' Rezoluce, unifikace
Tuhle otázku jsem zrovna moc neuměl, dal jsem dohromady preprocessing jako skolemizace, standartizace stranou,... a jak se vytvoří počáteční formule pro rezoluci. Pak jsem ovšem nebyl schopen vysvětlit, jak funguje rezoluční krok. Vomlelová byla nicméně nesmírně hodná a postupně to ze mě vydolovala. Unifikaci jsme nějak probrali v průběhu.
Příklady a ted rezoluční krok jsem se snažil popsat v syntaxi prologu, tak mi bylo navíc vysvětleno, že ok, ale rezoluce je obecná metoda.

'''Agenti (Neruda):''' Na začátek jsem dostal otázku, zda radši agenty nebo evu, což bylo potěšující. Vybral jsem si agenty a dostal Reaktivní plánování, hybridní přístupy, BDI, Soar.

Nejvíc v pohodě otázka, tohle jsem studoval i v rámci diplomky, takže z toho bylo spíš příjemný popovídání.

'''Neuronové sítě (Mrázová):''' Hopfield. model(učení, rozpoznávání, konvergence + náznak důkazu)
Tady jsem slušně zazmatkoval a popsal bidirektivní asoc. sítě, Mrázová to vlídně komentovala slovy: "No, to jste popsal něco jiného než jsem po vás chtěla, ale nevadí, ono je to podobné, tak povídejte." Takže jsem pokračoval hebovské učení, rozpoznávání, konvergenci jsem dal dohromady s dopomocí. Náznak důkazu jsem pak zjistil, že stačí vědět, že se ukáže, že žádný krok aktivního režimu sítě nezvýší energetickou funkci.

'''Složitost (Čepek):''' Pseudopolynomiální alg., Silná NP-úplnost
Tady jsem dostal okno a nedal pořádně dohromady ani definice a tím pádem jsem nedostal ani šanci povídat dál. :(

'''Poznámky''' Celkově velice příjemná atmosféra, kdybych uměl líp složitost, tak na projití jsem nepotřeboval imho vědět žádný důkaz(ale nečekejte za 1, asi ani za 2), ale asi taky záleží na otázkách. Zkoušelo se hlavně přehledově, jestli vím, jak ty věci fungují a k čemu jsou dobré, bez detailních podrobností.

=== 17. 9. 2013 ===

'''Slozitost (Koubek):''' Uplne problemy, P-uplnost, NP-uplnost.

U P-uplnosti jsem napsal ze prevod se provadi v logaritmickem prostoru a ze jde o obtizne paralelizovatelne problemy. Koubek ze me tahal co znamena "obtizne paralelizovatelne" a pak mi prozradil, ze jde o snizeni casove slozitosti na logaritmickou pri pouziti polynomialniho poctu paralelnich procesoru. Nicmene prislo mi to spis jako tresnicka navic.

'''Datove struktury (Koubkova):''' Vyvazovani binarnich vyhledavacich stromu - co, proc jak, priklad, algoritmy ne, radsi obrazky.

U vyvazovani stacilo popsat rotace, nejaky prilad insertu, pak jsme pokecali o tom jak se to da delat obecne v AVL stromech (jen zhruba) a nakonec me nechala zadefinovat RB-stromy.

'''Umela inteligence (Bartak):''' Hry, minimax, alfa-beta.

Alfa-betu jsem kdysi implementoval v zapoctaku, takze pohoda. Doplnujici otazky na problem horizontu a dalsi vylepseni algoritmu (symetrie, databaze vzoru)

'''Neuronove site (Surynek):''' Algoritmus zpetneho riseni a nejake jeho vylepseni.

Napsal jsem algoritmus i s odvozenim upravovacich pravidel pres derivace, Surynek jeste zminil Quickprop ale to se nastesti zakecalo a pak jsme si povidali obecne o tom jak se da minimalizovat funkce v n-rozmernem prostoru. Kratce jsme zabrousili k adaptivnimu parametru uceni.

'''Logika (neznamy mladik):''' Veta o uplnosti v predikatove logice.

V dukazu vety jsem se dostal k bodu kde potrebujeme model uplne henkinovy teorie a byl jsem byl 30 minut mucen na tom jak se to dela. (Neumel jsm henkninovu teorii ani poradne nadefinovat, natoz abych stavel jeji kanonickou strukturu z konstatnich termu atd...) Nastesti to byla uz posledni otazka, takze to ze jsem se uplne ztrapnil uz nemelo fatalni nasledky.

=== 17. 9. 2013 ===

'''Složitost (Majerech) - Základy pravděpodobnostních algoritmů.''' Očekávalo se ode mě definování složitostních tříd pro pravděpodobnostní algoritmy a uvedu příklad nějakého algoritmu využívajícího náhodu. Naštěstí jsem je uměl (učil jsem se z knížky ''Computational Complexity: A Modern Approach'', můžu jen doporučit). Zadefinoval jsem BPP, RP, ZPP a popsal myšlenku univerzálního hašování. Když jsem byl zkoušený, byl jsem doplněn ještě o existenci třídy PP. Pak jsem ještě doplňoval vztahy mezi těmito třídami a těmi klasickými (NP a spol.). Konkrétní algoritmy jsme už nepitvali.

'''Vyčíslitelnost (neznámý teoretik) - Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti.''' Popsal jsem, všechno možné. Definice ČRF, ORF, RM, RSM, 1-úplnost a spol. (K je jednaúplná, Myhill). Generování RM a RSM. Postova věta, lemma o selektoru. Zapomněl jsem na uzávěrové vlastnosti a ty chtěli nejvíc, tak jsem je rychle řekl. U některých vět jsem uvedl důkaz, ale nikdo to moc neřešil a bylo to víceméně bez doplňujících otázek.

'''Neuronové sítě (Mrázová) - Vrstevnaté neuronové sítě a algoritmus zpětného šíření.''' Protože měla paní Mrázová ostatní vyzkoušené, nabídla mi, jestli nechci mluvit "spatra". Než jsem si rozmyslel, jestli je to dobrý nápad, už u mě seděla, tak jsem se do toho dal. Popsal jsem neformálně, co je neuron a vrstevnatá síť a jak to v ní funguje. Napsal jsem chybovou funkci a odvodil adaptační pravidlo pro BP. Pak jsme si povídali o strategiích pro urychlení učení - hlavně adaptivní parametr učení, stručně pak metody 2. řádu. Poslední otázka byla na aplikace.

'''Adaptivní agenti a evoluční algoritmy (Neruda) - Evoluce expertních systémů.''' Měl jsem na výběr tohle nebo neuroevoluci. Dost jsem to podcenil (a asi bych i k neuroevoluci napsal víc). Popsal jsem základní myšlenku Michiganu a Pittsburgu, ale moc detailů jsem k tomu nevěděl, takže mi pan Neruda hodně pomáhal a hodně věcí mi objasňoval. Doporučuju si přečíst víc do detailu jak to funguje.

'''Umělá inteligence (Vomlelová) - Markovské procesy, zpětnovazební učení'''. Začal jsem zpětnovazebním učením. Popsal metody z Bartákových slidů. Porůznu jsem popletl indexy, ale ideu jsem měl všude dobrou (různě jsem je opravoval a trochu jsem se v tom zamotal). Trochu jsem váhal, co je to ten Markovský proces, věděl jsem jen co je skrytý Markovský proces, přes který jsme se k tomu dostali. Paní Vomlelová byla velmi hodná a když byla někde chyba, společnými silami jsme ji opravili.

=== 17. 9. 2013 ===

'''Vyčíslitelnost''' (Gregor): ''Věty o rekurzi a jejich aplikace''
* Jsem přeskočil úvodní definice (co je ČRF atd.) a asi to byla chyba. Ptal se kolik je ČRF.
* Chtěl základní větu o rekurzi i s přesným důkazem. Pak další věty o rekurzi - generování pevných bodů, pevný bod s parametry, dvojný pevný bod.
* Aplikace: Riceova věta s důkazem, pak další aplikace, např. důkaz, že existuje program, který vypíše sám sebe.
* Hodně jsem se motal, ale byl fajn a snažil se poradit. Nakonec řekl, že jsem tam toho hodně neměl a dá mi 2.

'''Datovky''' (Koubek): ''Samoorganizující seznamy''
* Hodně hnusná otázka, v podstatě mi to ani nezadal. Jen mi to zapsal do protokolu a zrovna tam stál i Hric a povídá: "Samoorganizující seznamy, o tom jsem neslyšel." Koubek se zasmál a povídá: "No, doufám, že tady pan kolega jo." významně se na mě podíval a odešel.
* Chtěl MFR, TR. Napsal jsem ten odhad na počet operací, na to se hodně ptal. Bylo potřeba rozumět tomu do hloubky, ptal se hodně na podrobnosti a co to znamená, jestli existuje něco lepšího, jestli to nejde zlepšit randomizací atd.
* Nakonec ještě Splay stromy.

'''UI''' (Barták): ''A*''
* Co je A*, jaké jsou heuristiky, optimalita a úplnost. Chtěl i úpravy jako memory bound, iterativní atd.

'''Neprocedurální programování''' (Hric): ''Beta redukce, normální forma''
* Tady jsem poučený vyčíslitelností začal od definice lambda kalkulu.
* Chtěl definici beta redukce, jestli existují nějaké další redukce (např. alfa, pak nějaká eta, o které jsem teda nikdy neslyšel). Vlastnosti Beta redukce, term redukujici se v jednom kroku, redukujici se, relace ekvivalence.
* Definice normalni formy, jednoznacnost, Church-Rosserova veta, jeji dusledky, konzistence lambda kalkulu.
* Vyberova pravidla, leve pravidlo vede k normalni forme, pokud existuje.

'''Neuronové sítě''' (Surynek): ''Asociativni paměti, vybavování, učení''
* Heteroasociativní, autoasociativní, ty třetí. Jaký je rozdíl mezi heteroasociativní a autoasociativní, když oboje zobrazuje do stejné dimenze.
* Hebbovské učení, crosstalk, co když dostaneme zašuměný vstup, jak to ovlivní výstup (váhová matice je lineární zobrazení).
* BAM, Hopfield, jak složité je s nimi počítat.
* Multiflop, jak definujeme n-královen, tsp, jaké problémy jím jdou řešit, najde optimum?
* Ptá se hodně na doplňující otázky, nezajímají ho až tak vzorce (jak mi přišlo ze zkazek u Mrázové), ale jestli to člověk chápe.

Nakonec za jedna, i když ty datovky a vyčíslitelnost mi to určitě kazily. Je důležité vše chápat a umět odpovědět na doplňující otázky. Pokud se okruh týká fakt jen nějaké věty (Riceova věta, Savitchova věta, Věty o rekurzi), tak důkazy nejspíše jsou potřeba. U přehledovějších otázek (jako ty asociativní sítě) je jim to asi dost šumák.


=== 17. 9. 2013 ===

'''Složitost (Majerech) - Vztah tříd složitosti determinismu a nedeterminismu + Savičova věta''' 

Tady bych jen dodal svou zkušenost se Složitostí II - ''Pokud jen trochu můžete vychoďte tento předmět. Není nic horšího než vidět to poprvé 6 týdnů před státnicema.''

Pozor že rozhodně nestačí znát věty, pokud nebudete umět důkazy, tak vás mohou klidně vyhodit.

'''Datové struktury (Čepek) - Univerzální hashovaní.''' Popsal jsem motivaci, pak konstrukci jak je v Koubkových skriptech. Pak očekávaný počet kolizí (takové to <math>O(1+c\alpha)</math>). A pak dolní odhad na <math>|I|</math>. Všechno jsem psal samozřejmě s důkazy. Stačilo to a nic víc doc. Čepek nechtěl. Padly ještě nějaké dotazy ohledně hašování obecně. Nicméně otázka byla nakonec jedna z příjemnějších. 

'''Neuronové sítě (Mrázová) - Samoorganizace + Ojův algoritmus (s ideou důkazu)''' Stačilo popsat samoorganizaci, jak se liší od učení s učitelem (to bylo taky v zadání otázky). Pak jsem napsal ještě něco krátkého o Kohonenových mapách. Ojův algoritmus jsem psal tak, jak to bylo na slajdech a stačilo to. Ptala se třeba na parametr gamma a proč má být malý.

'''Adaptivní agenti a evoluční algoritmy (Neruda) - Architektury podle Wooldridge a vybrat si nějakou a o té napsat víc''' Stačilo napsat [http://wiki.matfyz.cz/index.php?title=Adaptivn%C3%AD_agenti_a_evolucn%C3%AD_algoritmy#Metody_pro_.C5.99.C3.ADzen.C3.AD_agent.C5.AF.2C_.C5.99.C3.ADd.C3.ADc.C3.AD_architektury shrnutí] a okomentovat ty architektury. Jako konkrétní architekturu jsem si vybral STRIPS, který je popsaný ve slidech prof. Bartáka. Psal jsem to formálně a následovaly doplňující otázky typu: "Jak tedy plánovat deterministicky v dopředném/zpětném plánování?" (Stačí libovolná rozumná heuristika, která vás napadne).

'''Umělá inteligence (Vomlelová) - EM algoritmus''' Tahle otázka mě vyvedla z míry. Nejdřív jsem popsal Bayesovské učení a motivaci k tomu, v jakém smyslu jsme na UI EM algoritmus používali. Poté co jsem toto přeříkal, tak paní Vomlelová to shrnula tak, že je to pěkné, ale že na to se vlastně neptala. Takže že přistoupíme k EM algoritmu. Vzoreček jsem si náhodou zapamatoval asi dva dny před státnicemi s tím, že co kdyby, ale EM algoritmus jsem jinak podcenil, protože mi na to nezbýval už čas. Neměl jasno v tom, jak přesně to funguje. Paní Vomlelová se hodně snažila a nakonec sérií otázek mi to vlastně vysvětlila. Prošlo mi to, ale neměl jsem z toho vůbec dobrý pocit. Opravdu doporučuji to nepodcenit.


Poznámky na závěr:

* Na teoretické informatice se očekává, že věcem rozumíte a umíte je dokázat (rozumně oargumentovat, vymyslet důkaz, ...). Takže pokud čtete zkazky ze státnic, že nebylo potřeba nic moc dokazovat a stačilo mít základní přehled, tak pro vás to neplatí! Tak to zřejmě bývá na softwarovém inženýrství.

* Učil jsem se přes pět týdnů. Nechodil jsem na Složitost II ani na Datovky II a zpětně musím zhodnotit, že to bylo málo, přestože státnice jsem úspěšně složil.


=== 27. 5. 2013 ===
'''Slozitost''' (Kucera ml.): Psedopolynomialni algoritmy. Stacilo sepsat definice a zneni vet, plus ukazat pseudopnm alg na Batoh. Chvili jsme se hadali, co je Batoh a co Soucet podmnoziny, nicmene shodli jsme se na tom, ze je v tehle terminologii bordel a celou ji muzeme strcit do Pytle (nebo na Dno Pytle? :) ).

'''Datovky''' (MJ): Haldy. Popsal jsem definice a (hodne) strucne i operace. D-reg se vsim vsudy, i dotaz na vysku stromu. Leftist haldy byly jen s definici a popiskem, ze se vyvazuji utrzenim podstromu a prohazovanim synu. Binomialni v pohode bez dukazu (stacilo rict |B_i| = 2^i). Line haldy - motal jsem se v amort. slozitosti, takze me nechali ji spocitat, jinak by to ale asi slo i bez ni. Fibonacciho opet bez dukazu, jen jsem opet motal amort. slozitost, tak jsem jim ji radsi spocital. Pak chteli nejake aplikace - heapsort, dijkstra.

'''AAaEA''' (Neruda): Geneticke a evolucni programovani. Klasicka nerudovina, nic necekaneho.

'''Neuronky''' (Mrazova): Asoc. pameti, BAM, Hopfield, Multiflop. Popsal jsem ty modely jen hodne strucne, zminil se o atraktorech, napsal energeticke funkce (chybove ne). Popsal jsem Hebbovske uceni, zminil jsem i perceptronove uceni, ale to nekomentovala. Pak jsem nejak okecaval Multiflop, ale nakonec ze me vymamila cele odvozeni te energ. funkce, i kdyz pri tom hodne pomahala :)

'''UI''' (Volmelova): Markovske modely. Popsal jsem slovne, k cemu slouzi a co to je, pak Mark. a senzor. predpoklad. Nasledne jsem napsal, ze existuje filtrace, predikce, atd., vzdy jen s "levou stranou", tj. bez jakychkoli vypoctu nebo zprav. Popsal jsem Kalmana a jak se da nalozit se spojitymi promennymi. Na zaver jsem pridal cca tri vety o Skrytych MM - na ty se bud ani nepodivala, nebo je nekomentovala. Chtela pak po mne Viterbiho algoritmus, ktery jsem plodil dost dlouho - slovne jsem ji ho popsal dobre, ale chtela to na papire a to mi delalo potize, ale nakonec jsme to porodili.

'''Neuronové sítě''' - paní Mrázová - perceptron & algoritmus učení - hodně podrobně (na úroveň jednotlivých pidipředpokladů atd.), ale šlo to. Nemám úplně dojem, že by šlo o myšlenky a porozumění, spíš prostě vyplivnout ty vzorce a vědět, co se tam děje (ve vzorcích, ne globálně)... ale třeba se pletu.

'''Složitost''' - pan Koubek - pravděpodobnostní algoritmy - říkal, že mám smůlu, že jsem ho dostal - no, měl celkem pravdu :-) Podstatná věc - NEučit se to z wikipedie, nebo aspoň co je Monte Carlo/Las Vegas - říkal, že to je blbost, co tam píšou (teda, neřekl to doslova takhle...). Pak ze mě tahal, proč se používají randomizované algoritmy (1 - potlačují "divné" rozložení dat; 2 - za určitých mně naprosto neznámých předpokladů - které po mě chtěl - jsou rychlejší v očekávaném čase. To, že někdy jsou jsem řekl sám od sebe, ale ty předpoklady jsem opravdu nevymyslel). No, to bylo celkem nepříjemné. Pak jsme překormidlovali k příkladům, které jsem napsal (Randomizované BVS, treap, univerzální hashování, hledání perfektní hashovací funkce, quicksort) - tak jsme zabrousili více do hloubky v univerzálním hashování, což už bylo v pohodě (říkal jsem tu verzi z MIT přednášky a prošlo to). To mi trochu zlepšilo pocit z jinak dost děsivé otázky. No, každopádně poučení - to, že se pravděpodobnostní algoritmy nebraly opravdu nikoho nezajímá a je potřeba to nějak umět. No a z wikipedie očividně ne... takže moc nevím odkud - možná poprosit pana Čepka, aby to stihnul na Složitosti.

'''Umělá inteligence''' - paní Vomlelová - Reinforcement learning - když jsem začal psát motivace, tak mi řekla, ať nepíšu romány, že chce vzorce... tak to jsem si říkal, kde to teda jsme, jestli na medicíně, nebo na matfyzu (tady o ty vzorce imho fakt nejde v první řadě)... No, vzorce jsem vyprodukoval - zapomněl jsem v jednom bodě na sumu; byl jsem upozorněn, že mi tam něco chybí a když jsme se nad tím zamysleli, co to má říkat, tak jsem už vymyslel co. Pak jsem ještě prý měl jednu chybu ve vzorci TD-učení - což se mi nezdálo - ale v průběhu času na to, abych si to opravil, za mnou paní Vomlelová zaběhla a řekla, že to je vlastně dobře (což na mě tedy taky působilo zvláštně, že jde jenom o vyplivnutí vzorce a ne motivaci, proč ten vzorec vypadá, jak vypadá - fakt nikoho nezajímalo, proč jsou ty vzorce takhle udělané, což je imho špatně).

'''Datové struktury''' - MJ (Martin Mareš) - Dynamizace - tvářil se při zadávání, že kdybych hodně protestoval, tak by mi dal i něco jiného, ale mně se zrovna dynamizace celkem líbí, takže jsem to bral rád. Celkem v pohodě, příseděl pan Koubek, bylo to celkově příjemné - řekl jsem semidynamizaci pořádně (i s odvozením složitostí), u té vylepšené semidynamizace jsem popsal myšlenku, jak a proč to je udělané, jak je; u dynamizace jsem popsal algoritmy a složitost už jsme neřešili (uff). Na konci se mě ještě ptali, jestli se dá dobře dynamizace použít na perfektní hashování (ne - problém s generováním velkého počtu perfektních funkcí), prý je to třeba dobré na různé geometrické problémy (ale rozložitelné, tj. ne konvexní obal třeba), případně vícedimenzionální (a vícekriteriální) BVS... ufff. Ale celkově příjemná část zkoušky.

'''Adaptivní agenti''' - pan Neruda - chudák měl zlomenou nohu, naštěstí nebyl vůbec nerudný, ale klasicky v pohodě. Otázka byla na architektury agentů, něco o BDI a subsumpční architektuře - nebyl problém. Bokem - u BDI pozor, že Cyril Brom se s chutí ptá do větší hloubky (právě ve vedlejší místnosti tak činil) - podle mého nepokryté i těmi knížkami doporučenými. Asi se hodí přečíst komplet Wooldridge, ale po tom jsou ty informace hrozně roztahané, bohužel.

SLO - '''Uplne problemy (nie len NP) a priklady z nich.''' - napisal som definicie relativne k NP-uplnym a obecne k uplnym. Problem na PSPACE-uplny som bohuzial nevymyslel. Celkom sa ma pytali na definicie a tak.

VYC - '''RM a RSM a ich vlastnosti''' napisal som vsetko co som vedel. Bez dokazov. Tiez celkom podobne vypytovanie. Mal som tam toho malo, ale asi na prechod stacilo.

AGENTI - '''Modely populacnej dynamiky''' - nevedel som co presne tam mam pisat. Napisal som vzorec pre jednu populaciu a pre vlk-zajac. Pytal sa ma rozne podrobnosti. Najema je dobre vediet ake existuju ekvilibria a ako sa to bude spravat a tak. 

UI - '''CSP''' - napisal som vsetko co som vedel. Trochu sme sa zdrzali pri doprednom a zetnom retazeni. Mal som za to ze to viem, ale nevedel som. Konecne som pochopil aky bol rozidel. Podobne ako v predchadzajucich pripadoch, padali upresnujuce otazky, tak aby som riesenie nejako vymyslel.

NN - '''Neuron a lin. separabilita.''' - nechcel dokaz lin. separability. Ale to, kolko neuronov/vrstiev treba na separovanie akejkolvek mnoziny. XOR, konvexne a nekonvexne mnoziny.

=== 1.2.2013 ===
* DS (Pokorny) '''BVS a vyvazovanie'''
* Sloz (Kucera ml) '''Polynomialne hierarchie'''
* NN (Mrazova) '''Perceptron, dokaz konvergencie ucenia'''
* Agenti (Brom) '''Reprezentacia terenu''' (vyslovene povedal ze nechce A*)
* UI (Bartak) '''Automaticke planovanie'''

Boli sme tam traja, lahke otazky, bolo vidno, ze nas vyhodit nechcu. Bohuzial som nemal ponatie o Polynomialnych hierarchiach, (pri uceni som ich z casovych dovodov preskocil), tak som sa informoval, ci ma zmysel robit ostatne otazky. Bohuzial nemalo, tak som sa zbail a siel prec :)

=== 10.9. 2012 ===
; Koubek (datovky) - Univerzální hašování
: popsal jsem základní vlastnosti, odhad délky řetězců, minimální velikost a konstrukci 1-univerzálního hašování podle Leiserssona - doplňující dotazy na min. velikost c a ještě jestli lze zmenšit tu množinu funkcí

; Kučera (vyčíslitelnost) - Rekurzivní množiny a rekurzivně spočetné množiny
: definice, sjednocení, průniky, doplňky, omezené kvatifikace, postova věta, selektor, úsekové funkce a generování, nadstandardem už byly definice imunních, produktivních, simple a kreativních množin

; Brom (agenti) - Navigační pravidla, reprezentace v terénu
: popsal jsem A*, LPA*, rozsekání na dlaždice/polygony, waypointy... přišlo i na steering, kde jsme se trochu zdrželi

; Barták (UI) - CSP
: prostě všechno co je na jeho slidech

; Mrázová (neuronové sítě) - Perceptron, techniky na urychlení konvergence učení vrstevnatých sítí
: perceptron - definice, učení, důkaz konvergence; techniky - Silva Almeida, Delta-Bar-Delta, Super SAB, slovně už jen o perturbaci vah a technikách s druhou derivací chybové funkce


=== 8.2. 2012 ===
; Koubek (složitost) - Úplné problémy
: otázka byla obecná - šlo tedy o C-úplné problémy obecně a věci co s tím souvisí (C-těžkost, převoditelnost mezi problémy atd.)
Poznatek: když definujeme P-úplnost, jakou použijeme převoditelnost? Převod v polynomiálním čase nám moc nepomůže. V logaritmickém čase nestihneme přečíst ani celý vstup, takže co? Používá se tu převoditelnost v logaritmickém prostoru. To jsem nevěděl.

; Koubek (datové struktury) - haldy
: popsal jsem d-regulární haldy, zmínil jsem se o tom, že existují leftist haldy a popsal jsem binomiální haldy. Pana profesora ale zajímaly hlavně Fibonacciho haldy, jejichž složitost jsem nedokázal uspokojivě vysvětlit. Doporučení: ty algoritmy si OPRAVDU projděte.

; Majerech (Logika a výpočtová složitost) - Třídy složitosti a vztahy mezi nimi
: popsal jsem TS, co je to složitost TS, co je to složitost jazyka a potom třídy DSPACE,NSPACE,DTIME,NTIME. Na základě toho všeho jsem definoval
třídy P a NP, uvedl jsem pár základních inkluzí a znění Savičovy věty. Je dobré umět si nějak utřídit v hlavě vztahy mezi složitostními třídami aby člověk dovedl doplnit správnou inkluzi mezi dvě složitostní třídy

; Hric (Umělá inteligence) - Strojové dokazování vět
: popsal jsem rezoluční metodu, hornovské klauzule a jak je lze využít při dopředném řetězení a zpětném řetězení. Padla otázka na to, jak se řeší dokazování v predikátové logice a co je to subsumpce

; Neruda (Adaptivní agenti a evoluční algoritmy) - Architektura autonomního agenta
: reaktivita, plánování, BDI. Popsal jsem základní 3 přístupy podle Wooldridge: 1. agent se symbolickou reprezentací, 2. reaktivní agent, 3. hybridní přístup. Doporučuju přečíst si původní Wooldridgeův článek - odtamtud jsem pochopil zásadní rozdíly. U BDI stačilo popsat hlavní princip fungování, proč je to hybridní a v čem jsou výhody.

== I2 (Softwarové systémy) ==


=== 18. 9. 2014 ===

'''Složitost a vycíslitelnost''' - Dynamické programování

Mel jsem srovnat s metodou Rozdel a panuj + ukazat nejaky priklad

'''Datové struktury''' - Vyvazovani binarnich vyhledavacich stromu

'''Formální základy databázové technologie''' - Relacni kalkuly

'''Databázové modely a jazyky''' - Prikaz SELECT - srovnani standardu SQL-89 a SQL-92

Az ve standardu SQL-92 pribyly prikazy spojeni, do te doby se musel pouzivat kartezsky soucin jako

SELECT *

FROM table1, table2

Pomoci klicovych slov definovanych standardem SQL-89 neslo ziskat vysledek ekvivalentni vysledku, kde je pouzit OUTER JOIN. Vnejsi spojovani muze do vysledku zahrnout null hodnoty, ale kartezskym soucinem to neudelame.

'''Implementace databázových systému''' - Indexace relacnich dat - B-stromy a hasovani

	
=== 18. 9. 2014 ===

'''Vývoj sw. sytémů (Kofroň):''' Testování, testovací scénáře, testování uživatelského rozhraní, testování bílé, šedé, černé skříňky

Popsal jsem co je testování, k čemu je dobré, několik nástrojů a jak se používají.

'''Překladače a výkonnost sw. (Yaghob):''' LL(1) parsování

Definice gramatiky, Follow, First. Parsování rekurzivním sestupem a zásobníkovým automatem.

'''Datové struktury (Fiala):''' Stromové vyhledávací struktury

Přehledově trie, binární vyhledávací stromy, (a,b)-stromy. Podrobně haldy d-regulární, leftist, binomiální, líné binomiální, Fibonacciho.

'''Složitost a vyčíslitelnost:''' Dynamické programování

Motivaci a základní princip dynamického programování. Ukázáno na algoritmech výpočtu Fibonacciho čísel, batohu a Floyd-Warshalova algoritmu. U posledního jmenovaného ze mě zkoušející dostával formální důkaz proč požadujeme nezáporné hrany.

'''Analýza, návrh a management sw. sys (Bednárek): ''' Styly softwarových architektur

Definice architektury, pohledů a jejího stylu, příklady, souvislost s návrhovými vzory.

Atmosféra je při zkoušení příjemná. Zkoušející vnímají nesmyslnost některých otázek a zadávají je neradi.


=== 2. 6. 2014 ===

'''Výj. sw. sytémů (Kofroň):''' Testování, Black-gray-white box, testovací scénáře

Úvod proč testujeme, pár slov k test driven developmentu. A pak k jednotlivým boxům a pojmům.
Pohodová otázka na úvod.

'''Překladače a výkonnost sw. (Yaghob):''' Flynova tax., SMP, NUMA, Amdahlův zákon

Nakreslení Flyna, pár vět ke každé kategorii. Popis výhod SMP, co je NUMA, coNUMA, jaké jsou její výhody. Padl dotaz jak je paměť přístupná (z jednoho adresového prostoru) a jak jsou tam ty jednotlivé paměti namapovány (za sebe, prokládáním). Amdahlův zákon + jeho limitní verze, vzoreček pro zrychlení.

PS, OT: Ke konstrukci LR "překladače" se dají najít videa na youtube, kde možná není vše, ale je to o hodně lehčí než, se učit ze slajdů.

'''Složitost a vyčíslitelnost (Kučera):''' Pseudopoly. alg., silná NP-úplnost

Definice len, max, číselnosti, NP-úplnosti, pseudopoly alg., silné NP-úplnosti (napsal jsem bez kvantifikátorů a tedy jsem je musel doplnit). Příklad silně NP-úplného (obchodní cestující) a slabě (součet podmnožiny, loupežníci). Pak padl dotaz k čemu je možné pseudopoly alg. využít - základ pro aproximační schémata.

'''Datové struktury (Hladík):''' Fibonacciho haldy

Lehce nečekané (jedna z těch věcí, kde si člověk říká o haldách člověk něco řekne ale pak ...). Začal jsem úvodem co jsou haldy, napsal něco o Leftist, D-Reg., Polynom a nakonec Fibonachi. Popis struktury (les) a omezení (oproti poly. je rozvoleněné), jak pracuje "konsolidace" (spojování stromů stejných stupňů), označení vrcholů, vztah k Fibonacciho číslům. Popsání operací insert, merge, delete, delete-min + v diskusi pak složitosti. Padla otázka na definici .?. nakonec to prošlo +- přes "operace".

Zmínění ostatních hald pan Hladík nejprve při diskusi přeskočili (neb to nebylo otázkou), ale dalo se na ně hezky referovat pro "porovnání".

'''Analýza, návrh a management sw. sys (Zavoral): ''' Datové a procesní modelování

Motivace modelování, model driven development (jen tak z rychlíku), šlo více méně o to popsat proces tvorby digramů a kde se tam ta data a procesy berou - inspirace v MSA.
Do jisté míry jsem měl při diskusi pocit, že jde o to dokázat dost dlouho a dost rozumně mluvit (improvizovat) k tématu, ale možná je to tím, že obě předešlé otázky byli z více formální roviny.

Zkoušející byli moc příjmení, nikdo se nemračil a snažili se pomáhat. Konec konců je to potenciálně poslední zkouška s oblíbenými zkoušejícími a tak je třeba si to užít.


=== 17. 9. 2013 (okruhy od r. 2011) ===

''' Základy složitosti a vyčíslitenosti - Halting problém (Kolman) '''. Tu som zadefinoval TS, spomenul som kódovanie TS (nič konkrétne iba že to je číslo), Postovu vetu a dokázal som, že L HALT nie je rekurzivný, na záver som spomenul, že to isté sa dá urobiť aj cez množiny. Žiadne doplnkové otázky.

''' Datové struktury - Hašování (Kolman) '''. Mal som rozprávať o hašování všeobecne, čo to je, prečo to riešime a pridať čo prináša univ. a perfektné hašovanie. Vydal som zo seba nejaký všeobecný úvod, spomenul som štandardné spôsoby riešenia kolízii a čím sa od seba odlišujú (bez presného popisu algoritmov), spomenul som univerzálne hašovanie a perfektné hašovanie. Spolu so zopár otázkami na univerzálne hašovanie (c-univerzálny systém) to bohato stačilo.

''' Operační systémy - Procesy a vlákna (Kofroň) '''. Tu som povedal nejaky uvodny pokec k procesom a vlaknam, typy vláken a mierne som spomenul plánovanie, kde sa skúšajúci chytil práve nepreemtívneho plánovania a pýtal kde sa to používa (OS IX, Win 3.11) a ako to asi mohlo fungovať. Z jeho veľkou dopomocou a otázkami sme to nejak dali dohromady. Na záver povedal, že vlákna a procesy som povedal pekne takže za 1, čo ma mierne prekvapilo.

''' Věstavěné systémy a systémy reálneho času - Plánovanie a analýza naplánovateľnosti (Bureš) '''. Povedal som čo to je RM, DM, EDF a čo sa týka naplánovateľnosti tak som hovoril o Least upper bound a response time analýze. Nakoniec som iba spomenul ze existuje aj processor demand analýza ale to som už presne nedefinoval.

''' Objektově orientované a komponentové systémy - Garbage collection (Bednárek) '''. Hovoril som, čo to je načo je to dobré, výhody, nevýhody a potom konkrétne algoritmy pre tracing (mark and sweep, 3-color mark and sweep, generational collectors) a reference counting. Pan Bednárek povedal že s tým súhlasí a potom sme prešli na otázky, typu porovnajte tracing, reference counting a ručné uvoľnovanie pamäti z pohľadu využívania cache, multi processingu a podobne. Nad týmto som sa nikdy nezamýšľal a tak to zo mňa musel ťahať ale dával dobré otázky ktorými ma naviedol, k tomu čo chcel počuť. Aj napriek tomu ťahaniu som mal za túto otázku asi 1- alebo niečo veľmi blízke

''' Poznámky '''
Atmosféra ako to už mnohí spomínajú je príjemná.
Od skúšajúceho závisí do akej miery vrtá v tom čo ste povedali resp. to čo tam chce počuť ale stále platí ak máte základ a úkážete aspoň drobnú mieru pochopenia problematiky tak to prejde.
Z toho čo som videl mi príde, že to čo spomínaju kolegovia predo mnou tak je silne prehnané, že musíte vedieť dôkazy a podobne, skôr som sa stretol s tým, že dôkazy vyslovene nechcú. Samozrejme závisí od otázky ak je tam čo hovoriť tak dôkazy nie sú potrebné ale napr. pri takej vete o rekurzi by asi nejaký náznak dôkazu potrebný bol, keďže tam nie je čo povedať.
Organizácia skúšania bola veľmi zaujímavá, každý skúšajúci aj skúšaný mali rozpis s časmi, kedy budú skúšaný z ktorých otázok a v podstate sa ten harmonogram aj dodržiaval. Času na prípravu bolo podľa mňa viac než dosť a tak som tam pomerne dlho znudene posedával a čakal kedy sa dostaví skúšajúci.


=== 16. 9. 2013 (Podle okruhů do r. 2010) ===

'''Složitost a vyčíslitelnost''' (mladý Kučera): ''RM, RSM a jejich vlastnosti'' – Napsal jsem:
* definice RM, RSM vč. definice ORF a ČRF (s drobnou chybou – dal jsem dohromady prvky a operátory nad funkcemi),
* generování (tři věty o oborech hodnot) (Tady se mě ptal, jak fungují ty programy pomocí kterých množiny generuji. Neměl jsem to rozmyšlené, takže to ze mě musel tahat a část říct),
* 1-převoditelnost, 1-úplnost, K je 1-úplná. Ptal se mě, k čemu ta 1-převoditelnost je. Dával mi návodné otázky a potom jsem si končeně vzpomněl, že asi myslí to, že můžu převést jednu množinu na druhou. Jen tak mimochodem se ptal, kolik je RM a kolik RSM.
Všechno jsem psal bez důkazu a nechyběly mu. Nakonec mi řekl, že to mám tak za 1− a jestli chci čistou 1, tak ať mu formálně dokážu, že K je 1-úplná. Řekl jsem mu, že o 1 mi až tak nejde.

'''DS''' (Koubek): ''Vyvážené binární vyhledávací stromy'' – Napsal jsem:
* co je BVS (měl jsem tam chybu v podmínce),
* co je vyvážený strom a ústně jsem na jeho dotaz doplnil, že jeho hloubka je <math>O(\log n)</math>,
* definici AVL a Č-Č (u Č-Č jsem měl i nějaký odhad hloubky, ale Koubek vypadal, že si ho ani nevšiml),
* základní algoritmy – jen slovně a občas jsem tam měl drobnou chybku (např. jsem předpokládal, že vrchol má při odstraňování jednoho syna, ale on to mohl být i list),
* na příkladu AVL jsem se snažil popsat vyvažování. Neměl jsem to připravené, ale Koubek ty operace stejně přesně nechtěl. Spíš chtěl, abych mu řekl, že při vyvažování se nejen upravuje strom, ale také mění ta hodnota o vyvážení uložená ve vrcholech.
Celkově mě překvapilo, že byl Koubek docela hodný (čekal jsem to horší podle předchozích zápisů). Když odcházel vypadal spokojeně. Koubek občas chytne za slovo, když člověk řekne něco co není pravda. Je třeba se nenechat zaskočit (což je samozřejmě těžké) a popřemýšlet nad tím, co se mu nelíbí.

'''Analýza a návrh SW''' (Mlýnková, nyní Holubová): ''ER-schémata'' – Napsal jsem:
* že je to na datové modelování (chtěla to zařadit do takové té hierarchie fyzická, logická, ???, to jsem nevěděl, ale moc jí to nechybělo,
* z čeho se může ER-schéma skládat (ptala se mě, co znamenají kardinality, tak jsem jí to řekl, chtěla příklad, dal jsem jí ho, ona se zeptala, jestli mám kardinality na správných stranách, znovu jsem provedl úvahy o tom, jak to měl Skopal na slajdech, řekl jsem jí, že to mám správně a ona řekla, že to každý píše stejně jinak :-D),
* co je to relační model – to jsem neznal formálně, tak jsem to tam napsal slovně a ona to chtěla formalizovat, tak jsem řekl že tabulka je název a n-tice, ona ze mě tahala nějaké pojmy, ale ty jsme nevěděl, pak se mě zeptala, jak se jmenuje ta operace se sloupci, když potřebuji doménu hodnot, vůbec jsem nechápal, co po mně chce a ona po mě chtěla „kartézský součin“ :-).
* Jak se to převádí – entity na tabulky atd. Hlavně ji zajímaly kardinality, kde jsme došli k tomu, že se to dá převést všechno na jednu tabulku a může tam dojít k duplicitám.
* normální formy – kdybych to tam prý nenapsal, tak by se na to neptala, ale když už jsem to tam měl, tak to zkontrolovala a chtěla po mě příklad porušení a jak to opravím. Tak jsem jí ho dal.
Řekla, že je spokojená a odešla.

'''Objektové a komponentové systémy''' (Bureš): ''Garbage collection'' (původně zadával Kofroň, ale potom si otázky prohodili) – Napsal jsem:
* Co to je a k čemu to je.
* výhody, nevýhody,
* základní algoritmy a jejich vlastnosti
** počítání referenci
** zjišťování dostupnosti
U toho zjišťování dostupnosti chtěl ještě nějaké dělení, ale to jsem vůbec nevěděl, protože jsem ani nevěděl, ve kterém předmětu se to učí a studoval jsem to z internetu. Celkově za 3.

'''Modely a verifikace programů''' (Kofroň): ''LTL, CTL, jak se pomocí nich verifikuje, model-checking obecně'' – Napsal jsem:
* Co je to model-checking.
* Trochu jsem popsal Kripkeho strukturu.
* Popsal jsem, jak vypadají CTL.
Pak přišel Kofroň, že už začneme (byl jsem v místnosti už poslední). Říkal, že je to OK a ptal se na to, jak probíhá model-checking pomocí CTL, tak jsem mu to řekl ± správně. Potom se zeptal, jak se tedy kontroluje LTL. To mě zaskočilo a vůbec jsem nevěděl. Tak mi to řekl a řekl že to mám za 2.

Celkově mě docela překvapila uvolněná atmosféra (všichni byli sice v obleku, ale byli veselí).


=== 28.1. 2013 ===
; Loebl (SV) -- Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce.
: Churchova-Turingova teze. Definoval jsem TS a popsal, jak počítá. Rekurzivně spočetné/rekurzivní jazyky. Postova věta. Definice PRF, ORF, ČRF (a predikáty) - zmínit, jakým programovacím konstruktům odpovídají odvozovací fce. Základní lemmata (konečný součet, popis ekvivalentní fce pro switch, atd.). Nakonec bez důkazu, že ČRF a TS jsou ekvivalentně silné. Ptal se na existenci UTS (stačila idea). Vše jsem měl přesně, takže řekl, že mu to stačí na 1.

; Hladík (DS) -- Fibonacciho haldy.
: Základně jsem popsal d-regulární a binomiální haldy a složitost operací (to ho moc nezajímalo). Pak, že FH jsou definované pomocí posloupnosti operací + popis operací (stačilo slovně). Trochu jsem plaval v dokazování složitosti (stačila amortizovaná), ale důležité bylo ukázat, že vím, proč jsou ty operace definované tak, jak jsou (jak ovlivňují složitost). Nakonec dotaz, kde se využívají a jaké mají výhody proti ostatním strukturám/haldám. Celkově byl zkoušející v pohodě.

; Bulej (OOKS) -- Dědičnost, subtyping, variance signatur.
: Popsal jsem hlavní důvody využití dědičnosti (reusability, prostředek pro subtyping). Subsumption a možné vztahy mezi subtypingem a dědičností. Další druhy subtypingu (pomocí interface, strukturální). Variance při definici typů, pro parametry a návratové hodnoty metod. Možnosti variance v C# (in a out při typové parametrizaci) a Javě (? extends T, ? super T). Pak jsme už v rámci diskuze zabrousili na virtuální metody, výhody/nevýhody vícenásobné dědičnosti a mixiny. Nakonec jsme se bavili o implementaci (vtable).

; Bednárek (ANSS) -- XML, XML Schema.
: Popis modelu, jak vypadají dokumenty + well-formed vs. validní podle schématu. XML Schema - že určuje strukturu typu dokumentů, konstrukce pro definice typů, základní typy. Pak jsem lehce popsal XPath, XSLT, XQuery a API (DOM a SAX) - to ho však až tak moc nezajímalo. Ptal se na podobnosti/rozdíly s relačním modelem/techologiemi (plochý vs. hierarchický, typování, specifikace klíčových atributů (XML Schema má i cizí klíče - ale v první verzi to prý nebylo moc použitelné, tak se o tom moc neví :-) )) Nakonec, zda vím něco o teoretickém backgroundu, což jsem přiznal, že ne (použití stromových gramatik při parsování). 

; Hnětynka (DS) -- RPC - obecně + nějaká imlementace.
: Princip fungování RPC, související pojmy a problémy (IDL, reprezentace dat, globální kontext, naming/trading). CORBA - lehce problémy s mapováním typů a výstupních parametrů, IOR, POA a policies, implementace servantu (xxxPOA vs xxxPOATie), naming/trading. Java RMI - stuby pomocí reflexe (ale jdou i generovat -> RMI-IIOP), Remote interface, naming a že jde využít JNDI, leases, serializovatelnost. V rámci diskuze technické detaily pro RMI (dynamicky generované stuby mají každý vlastní typ (aby mohly být použité na místě interface), jak servant pozná jestli dostal objekt referencí nebo hodnotou (stub vzd. objektu se serializuje jako reference)).

=== 11.9. 2012 ===
; Mlynkova (ANSS) -- E-R modely a prevod na relacni modely
: E-R schema, jak vypada, jak se pak prevadi na relace (kterou jsem nepojal formalnim zpusobem a la predemt 3 roky zpet, ale hovoril o relacnich DB), jak se jednotlive kardinality implementuji + nejake demo v SQL, nakonec jsme zabrousili k normalizaci a prosel muj vyrok o tom, ze v praxi muze nakonec normalizace skodit, protoze takova zmena schematu u replikovane DB je moc prijemna zalezitost. Nic dalsiho nebylo potreba, cili otazka v pohode.

; Yaghob (MSS) -- Paralelni programovani a lockless algoritmy
: To jsem si pral, protoze jsem si precet moc hezkou knizku Concurrent programming in C++, ktera popisuje nove featury od C++11, memory model a tak. Urcite by to slo i bez toho, treba kdyby nekdo mel za sebou OSy, ale me ta knizka bavila a zajimala.

; Kucera P. (SV) -- Pseudopolynamialni algoritmy a silna NP uplnost
: Definice obojiho, jedna veticka o tom, ze silne NP-uplne nemaji pseudopol. alg., strucne napsany pseudopol. problem pro batoh, veta o tom, ze pokud bychom nasli pro silne NP-uplny problem pseudopolynamialni alg., muselo by platit, ze P=NP. Nic dalsiho nebylo potreba vedet.

; Majerech (DS) -- Reseni kolizi v hashovani a univerzalni hashovani
: Na uvod klasicky vycet ruznych reseni kolizi ("ten sklep v tom, jak ho popisujete, vam k nicemu nebude, podle me"), pak dlouhe paceni toho, ze se pri velkem load factoru da tabulka zvetsit (vubec me nenapadlo, ze je potreba to rict, ale M. byl chapavy a pockal si, az jsem se chytil za nos), pak povidani o rozdilu mezi randomizovanou slozitosti a ocekavanou slozitosti ("co kdyz budete mit robota nad pacientem, co z nej strika krev, bude vam tohle hashovani stacit?"), diskuse o doplneni RB stromu do jednotlivych bucketu a tak. Slabsi povahy by si mohly myslet, ze je to na vyhazov, ale to vubec neni pravda, M. je velmi inteligentni a korektni a i zkouseni je u nej prilezitost k vysvetleni zajimavosti. Bylo fajn, ze se neptal na algebraicke principy fungovani c-univerzalnich systemu, ale spis mu slo o porozumeni, jak to funguje a v cem je to dobre/spatne.

; Obdrzalek (OOKS) -- Diamond problem
: "V cem pisete?" -- "V C++" -- "super, tak to popiste v tom, a pak jak by se to mohlo delat i jinde". Prijemna tecka, zadne zaludnosti, ale pravda je, ze jsem mu popsal i [[wen:Thunk (object-oriented programming)]].

; Koubkova(DS) -- Haldy
:Regularni haldy -- co jsou, k cemu jsou, Min/Max heap, Insert,  ExtractMin, Delete, pouziti, implementace v poli, Binomiální haldy, Fibbonaciho haldy, nasledne diskuse

; A.Kucera - tusim (SV) -- Nerozhodnutelné problémy
: Halting problem - jak se dokazuje, Postuv problem, rozhodnuti zdali dana funkce vycisluje dany program

;Wilkie + Skopal + kdosi (Analýza a zpracování obrazu, počítačové vidění a robotika) -- Detekce hranic objektu
: Segmentace - Thresholding, deformovatelne modely, watershed, grafove algoritmy, shlukova analyza, Detekce hran - 1.,2. derivace - filtry ktere se pouzivaji, jak se pouzivaji, DoG, vysoke frekvence...

;Wilkie + Skopal + kdosi (2D počítačová grafika, komprese obrazu a videa) -- Rozptylovani a pultonvani
:vicemene to co je v Pelikanovych slidech - Rozptylovani - iterativni, pravidelne, priklady matic, souvisle, otaceni slozek; Pultonovani - Maticove, Nahodne, Distribuce chyby, Floyd-Steinberg

;Wilkie + Skopal + kdosi (Realistická syntéza obrazu, virtuální realita) -- Prime metody pri visualizaci objemovych dat
: Pelikanovy slidy - co jsou objemova data, hodnoty/souradnice, 3D-DDA, Raycasting, Splatting, vice ve slidech (vic nemam v zapiskach, ale vedla se diskuse o spouste veci)


=== 12. a 13. 9. 2011 ===
; Koubek (slozitost a vycislitelnost) - Cook-Levinova veta
: definoval jsem NP, NPC, atd., dokazal vetu kachlikovanim. Pak se me ptal co znamena pojem uplnosti obecne a naky jeho zneni nebo dusledek Cook-Levinovy vety (neco jako ze kdyz bych umel polynomialne resit NPC problem, tak uz vsechny NP problemy jdou resit polynomialne). Pak chtel co je PSPACE uplnost a nakej priklad (obecna booleovska formule). SAT ve zneni s KNF se mu uplne nelibil, prej se vetsinou definuje obecne. Kdyz mu prisedici Majerech rikal, ze jak jsem ho definoval se to u nas vetsinou dela, tak se Koubek mracil :)

; Majerech (DS) - binarni stromy, vyvazovani
: AVL, RB, hlavne definice a invarianty a hloubky, operace a rotace vlastne ani nechtel. Spocital se mnou minimalni pocet vrcholu pro danou hloubku u obou stromu a prestoze mi to moc neslo, tak byl nakonec spokojenej.

; Kofron (OCS) - model checking
: napsal jsem co je na wiki, chtel vedet, jak se to teda prakticky delat a jaky sou tam omezeni. Pak chtel priklad, kdy program vede k nekonecnosti stavu (napr. dynamicka alokace). Napsal jsem mu k tomu i LTS, CSP a naky prikladky maly. V logikach nestoural.

; Obdrzalek (OSY) - sprava pameti
: obecne, o co se OS musi starat, pak virtualni pamet, vyhody a nevyhody, jak se to dela, strankovani, TLB, inverzni. Vypadek stranky a jak se obsluhuje. Obsah zaznamu ve strankovaci tabulce (strucne). Pak se ptal, proc je vyhodny / nutny pouzivat zarovnany adresy v programu (kvuli architekture HW). Mel hodne otazek, ale nic extra zaludnyho. Na segmentaci ani nedoslo.

; Yaghob (prekladace) - generovani kodu, alokace registru, scheduling
: nakreslil sem diagram, jak se postupuje pri generovani kodu (rozsekani na BB az po OBJ vystup), napsal algoritmy na live-range analysis, alokaci registru a scheduling z Bednarkovych slidu. Pripadalo mi, ze je Yaghob bud neznal nebo uz byl unavenej, protoze sem mu je musel docela vysvetlovat (mozna proto mi pri zadavani rikal, ze je to takova vtipna otazka). Jinak v tom nestoural (taky sem tam byl uz sam).

; Kucera (slozitost a vycislitelnost) - NP-uplnost, Cook-Levinova veta
: definice NP, prevoditelnost, NPC, prevod na kachlikovani a na SAT

; Koubek (DS) - reseni kolizi v hashovani
: napsat vsechny algoritmy a porovnat je z hlediska pametove a casove narocnosti, prumerna delka retezcu, jak to ovlivni cachovani

; Yaghob (prekladace) - LL analyza
: definice FIRST, FOLLOW, LL gramatiky, leva rekurze a faktorizace, analyza shora dolu (rekurzivni, nerekurzivni, jak se sestavi ten automat), jake atributy lze pri teto analyze rovnou spocitat

; Bures (OCS) - prototypy a klony
: co je to prototyp, klon, jake jsou zpusoby klonovani, jak se resi dedicnost, vyhody oproti class-based, priklad v Selfu

; Kofron (ANSS) - informacni bezpecnost
: autentizace, autorizace, kryptografie (symetricke, asymetricke sifry - na cem jsou zalozene, kdy se pouzivaji), bezpecnosti utoky, hashovaci funkce

=== 26. 5. 2010 ===

; Surynek - ČRF
: Základní definice, funkci x+y definovat jako ČRF, detaily ostrých inkluzí PRF/ORF/ČRF. Otázka: Je univerzální funkce pro třídu PRF také PRF? Ne, dokonce není ani ORF, protože nemůže být totální.

; Kopecký - BVS a jejich vyvažování
: BVS, AVL stromy, RB stromy, rotace. Vytvoření statického stromu pomocí dynamického programování. Mluvili jsme také o splay stromech.

; Bureš - Synchronizace procesů, synchronizační primitiva.
: Popis primitiv, TSL. Synchronizační problémy, detailní implementace producent/konzument pomocí zadefinovaných primitiv.

; Bulej - virtualni stroje
: Obecny prehled, shadow PT, virtualizace diskoveho zarizeni.

; Hnětynka - Middleware
: Klasifikace, příklad protokolů. Detailní rozebrání RPC a CORBA, případně RMI. Jde se skutečně do detailů.

; Peterka - detaily 802.11
: Běžné základy, rozdíly mezi verzemi. K tomu detailnější rozebrání PCF. Navíc detaily frequency hoppingu.

; Hladík - Úplné problémy pro třídu NP + Cook Levinova věta.
: Definice (od TS až k NPÚ), Důkaz Cook Levinovy věty (KACHL + převod na SAT), vyjmenovat problémy co byly na přednášce (zadání, otázka), ukázat převod SAT na KLIKA.

; nějaký teoretik - B-stromy + jejich varianty.
: Def., operace, složitosti bez žádných větších důkazů.

; Yaghob - Mezikód.
: Formy, reprezentace, optimalizace + k čemu to je vůbec dobré.

; Hnětynka - Objekty a třídy v Javě. (obj + komp. systémy)
: Co to je, proč se zavádí, vlastnosti, implementace VMT, object layout, dědičnost, jak je to v C++ s vícenásobnou dědičnoustí, rozdíly C++ templates a Java generics. Příklady.

; Nečaský - Značkovací jazyky + XML (analýza + návrh soft. systémů)
: jak to vypadá, značkovací jazyk jiný než z rodiny XML (př. TeX), XML, XML Schema, DTD, Schematron (jaký je rozdíl oproti DTD a XML Schema), XPath, XQuery, XSLT - malé příklady v každém z jazyků.

; Zavoral - algoritmy virtualni synchronie
: Definice virtualni synchronie, formalni definice pohledu, drobne detaily TRANS, TRANSIS, ISIS

; Koubkova - haldy
: d-regularni, binomialni, leftist, fibbonaci. Ukazat pridavani / odebirani prvku v d-regularni a binomialni.

; Slozitost - pseudopolynomialni algoritmy
: formalni definice pseudopolynomialniho algoritmu, silne NPU problem. Algoritmus reseni SP. Priklad silne NPU (TSP s omezenim na vaze hran) a proc je silne NPU (prevod na HK). Nekolik otazek jak souvisi pseudopolynomialni algoritmy a aproximacni algoritmy.

=== 9. 2. 2010 ===

; Bulej - Virtuální stroj  (Osy)
: Popis, co to je, co to dělá, type I, II. Všechno dobré, ale pak se začal ptát: jak se to přesně dělá, příklad "citlivé" instrukce třeba na x86, jak se to udělá, aby se traplo, jak to funguje (třeba když se zapíše na disk, jak se to musí udělat, abz se to traplo). Potom JVM - jak vypadá instrukční sada, čím se liší třeba od MIPS nebo x86.

; Peterka - Emaily (SMTP, POP)
: Příjemné popovídání, jak funguje SMTP, jak se to posílá (MX záznamy atd.)

; Löebl (AVL, CC stromy)
: Bez problému, definice, rotace, nic moc do hloubky.

; Zavoral (Distribuovaný konsenzus)
: Generálové a důstojníci, dvě armády.

; Alg. nerozhodnutelné problémy
: Co to je rozh. problém, halting problém, že to souvisí s tím, že množina K není rekurzivní, Riceova věta s důkazem.

; Mlýnková - Relačí algebra + kalkuly + SQL
: Stačilo vědět nástřel definice a hlavně, jak to přirovnat k SQL (prvky jsou tabulky/řádky/atributy ... algebra/n-ticový/doménový). U popisu algebry a kalkulu ukázat nějaké příklady. Vědět že je to ekvivalentní (kalkuly a algebra), ale že SQL je silnější protože má navíc agregačí funkce.

; Mlýnková - XQuery a XSLT
: Popsat co to je a k čemu to je. Stačí vědět jak to funguje, není nutný znát help zpaměti. Vědět jakou má který jazyk sílu a co umí. A pak vědět, že jsou vzásadě ekvivalentní. Akorát že XSLT umí přepínat mezi různými výstupními soubory.

; Kopecký - Vnitřní a vnější třidění (Datové struktury)
: Vnitřní=CPU operace, vější=přistupy na disk. Rozdělení (porovnávání prvků/ostatní). Příklady. U quicksortu hledání pivota v lineárním čase. U merge jak se to má s výhodamy/nevýhodami s různým počtem pásek. Vytváření běhů pomocí haldy/dvojité haldy.

; Richta - Distribuované transakce
: Stačilo jen základy. Centralizovaný/decentralizovaný přístup. Dvoufázový potvrzovací protokol.


=== 9.9.2009 ===
; Čepek - Haldy (okruh Datové struktury)
: Definice + operace binární haldy, binomiální haldy, Fibonacciho haldy + dotaz, jak se (implementačně) řeší přístup na prvek haldy (třeba fuprostřed nějakého stromu Fib. haldy) (Odpověď: pole ukazatelů do haldy indexované čísly vrcholů)

; Majerech - Aproximační algoritmy a schémata (okruh Složitost a vyčíslitelnost)
: Definice AA, poměrová a relativní chyba, AS, PAS, ÚPAS, ÚPAS pro SP (pozor na písmena v popisu PROŘEŽ (1-d)z < y < z), AA pro TSP

; Peterka - Přenosové služby - spojovanost/nespojovanost, spolehlivost/nespolehlivost, pohled dle TCP/IP a RM ISO/OSI (okruh Architektura počítačů a sítí)
: Definice, rozdíl mezi nespolehlivostí a best-effort (nespolehlivost - příjemce nežádá nápravu při chybném přenosu, best-effort může být i spolehlivá, je to spíš věc odesilatele), navíc ještě tag switching (např. MPLS) a jestli ATM je přepojování paketů nebo okruhů (paketů, ale dokáže v CBR simulovat virtuální okruh)

; Obdržálek - Správa paměti (okruh Operační systémy)
: Celkem detailně: Proč VP, Fixed partitions, Variable partitions, Fragmentace, Segmentace, Stránkování, Stránkování + segmentace (u všeho k čemu to je, co to řeší), konkrétně jak funguje stránkování na Intel IA32 bez PAE, co je PAE (Physical Address Extension), jak je to u 64-bit procesorů, proč jsou 64-bit adresy vlastně jen 48-bit (programátoři zneužívají zbylé bity, 64-bit paměť je moc, žádný OS by to nevyužil)

; Tůma - Komunikace, zprávy, RPC (okruh Distribuované systémy)
: Co je to zpráva, jak vypadá, že se ztrácí, co s tím
: RPC - co je IDL, jestli to jde i bez toho, co se generuje (stub, skeleton (přilinkování) a headry (includovani) pro klienta a server), transparentnost - globalni promenne, pointery, objekty v RPC (jsou na serveru, klient má proxy, kde se vezme? naming služba. Kde běží? Jak se tam vezmou reference na objekty?)
: Threading model serveru. Podle čeho poznám kolik vláken má mít Thread pool? (podle workloadu - 1) processor-intensive = cca tolik vláken kolik procesorů 2) hodně s diskem a čekání = trochu víc), jak se liší použití RPC a messagingu (synchronnost, one-to-many u messagingu), JMS, může si každý naimplementovat svojí name service?

; Surynek - Binární stromy a vyvažování
: Definice BS, BVS, operace, jejich složitosti, nejhorší případ. AVL - definice, důkaz logaritmické výšky, rotace, příklad vkládání několika prvků. RBT - definice, důkaz logaritmické výšky, výhody/nevýhody oproti AVL, hustota AVL vs. RBT, stejný příklad s vkládáním. Stručně BB-<math>\alpha</math>, splay stromy (kdy se hodí), optimální BVS.

; Matoušek - NP-úplnost
: Přesná formální definice - rozhodovací problém, jazyk problému, NTS pro rozhodovací problém, složitost výpočtu NTS, NP. Převoditelnost aritmetických funkcí, problémů, NP-těžkost, NP-úplnost. Příklady problémů. Vztahy P, NP, NPC (obrázek s podmnožinami, je NPC doplněk k P v NP?). Alternativní definice NP přes ověřování řešení. Jak popsat NP, NPC laikovi.

; Peterka - Přístupové metody
: Přehled - co a proč řeší, centralizované vs. distribuované a deterministické vs. nedeterministické metody + příklady. P-persistence, CA, CD. CSMA/CD Ethernet podrobně - binary backoff, proč 1-persistence, další vývoj v rychlejších verzích Ethernetu (1Gb, 10Gb). Aloha, DCF (RTS/CTS), PCF. Jak se volí časy DIFS, CIFS. Přístupová metoda v sítích kabelové TV.

; Bureš - Souborové a adresářové služby, souborové systémy
: Co poskytuje OS aplikacím - operace na souborech a adresářích. Implementace - blok, alokace bloků, správa bloků, volného místa, atributy, adresáře. Jeden FS podrobně (třeba ext2/3/4). Podrobně a přesně popsat, co se děje, když uživatelská aplikace čte ze souboru (syscall, OS, HW, ...).

; Hnětynka - Komunikace, zasílání zpráv, RPC
: Unicast - spolehlivost, potvrzování. Spolehlivost v multicast. RPC - podrobně, jak se řeší dynamické struktury. Přehled alternativ k RPC v různých situacích - RMI (předávání hodnotou, referencí + analogie v CORBA), MPI (rozdíl oproti RPC), SOAP, JMS. Další otázky: jak se řeší BE/LE reprezentace v IP, jak vypadá broadcast adresa v IP.

=== 28.5.2008 ===

; Zavoral - distribuovaný konsenzus
: Chtěl vědět definici (přesnou), problém nespolehlivosti uzlů, nespolehlivosti zpráv, kdy je řešitelné a jak (jde v podstate o byzantske generaly + zobecneni & neresitelnost potvrzovani zprav pri nespolehlivem prenosu).

; Yaghob - podpora multiprocesoru v OS
: Je třeba ošetřovat paměť, procesy, synchronizaci, ... Myslim že jsem to fakt uměl, Chtěl toho vědět fakt hodně, kromě klasických věcí dokonce škálovatelnost synchronizačních primitiv na velké množství procesorů, barrier instrukce, problémy s prefetch a reorderingem...

; Obdržálek - virtuální pamět
: Chtěl vědět +- klasiku - proč, jak, podpora hw, stránkování, segmentace, co se používá, co se nepoužívá, kde jak. Ke většině odpovědí má nějakou záludnou otázku typu a jde to i bez toho? A nejde to jinac? Pouziva se tohle ci tamto v praxi? Pouzivalo se v historii?

; Zemlicka - trideni ve vnitrni pameti
: Klasika, nejake ty vychytanejsi, kdy jaky se vyplati vic (asort s malo inverzemi, prihradkove pri malem univerzu). celkem o.k., meli jsme trochu problemy s terminologii, jelikoz zemlicka pouziva jinou nez koubek

; Jakysi mily teoretik - savitchova veta
: Napsal jsem vetu, myslenku dukazu (sestrojime turingac, simulujeme vsechny vetve, recyklujeme + pamatujeme stavy...) v pohode stacilo, zeptal se me jeste na par otazek a o.k.

; Trpělivý teoretik - Pseudopolynomiální algoritmy a aproximační schémata
: Napsal jsem špatnou definici pseudopolynomiálních algoritmů, aproximací, AS, a ÚPAS. Na dotaz jestli znám nějaké AS jsem zmínil ÚPAS pro SP, a to že patrně obsahuje nějakou proceduru co cosi prořezává. Posléze se mi podařilo přijít na správnou definici pseudopolynomiálních algoritmů, a to jak by zhruba měl vypadat pseudopolynomiální algoritmus pro problém batohu. Tou dobou ale už všichni ze zkoušky odešli tak mě nechal jít :-)

; Spěchající teoretik - Stromové vyhledávací struktury
: Popsat jsem A4 binárními stromy, jejich procedurami insert a delete, popisem jak se vyvažují AVL stromy, a stručnými pravidly jak vypadají červenočerné stromy. Chtěl jsem si udělat i něco o B-stromech, haldách a triích, ale zkoušející si prohlédl můj papír s binárními stromy a prohlásil, že mu to stačí.

; Adámek - Komunikace a synchronizace procesů, uváznutí
: popsal jsem spinlock, synchronizační primitiva a zodpověděl nějaké otázky na to jak se to použití liší na SMP; pak jsme mluvili o klasických synchronizačních problémech a zablokování (Coffmanovy podmínky, předcházení, řešení)

; Adámek - Middleware (CORBA, DCOM, EJB)
: rozepsal jsem princip RPC a RMI u CORBY, mluvili jsme o POA a default servantu (k čemu je to dobré apod.), pak jsem měl napsané Java RMI, EJB (typy beanů), JMS (modely doručování) a DCOM

; Peterka - Přenosové služby (spojované/nespojované)
: napsal jsem rozdíl mezi spojovanými a nespojovanými službami, jednotné řešení v ISO/OSI a tím že v TCP/IP si člověk může vybrat mezi TCP a UDP, dál se ptal na fungování TCP, a to nad čím běží které protokoly (DNS, RTP)


==== Statnice - databaze: ====
Komise asi 7 lidi, skupina zkousenych asi 12, obsadili jsme cele treti patro (chodba vlevo + prilehle kabinety). Slozeni komise (s prominutim v celem prispevku bez krestnich jmen a titulu :-) - Pokorny, Kopecky, Skopal, Galambos, Cepek, Mlcek, Kucera. Na zacatku si to nejak rozdelili, takze zkouseni dostali zadano pet otazek - 2 ze spolecne a 3 z volitelnych. Povinne okruhy zkouseli Mlcek (vycislitelnost), Cepek (slozitost) a Kucera (snad nekoho i ze slozitosti :-) U Kopeckyho nevim, co zkousel, kdyz mi prisel zadavat otazku, tak zjistil, ze uz mam vsechny zadany, tak zas odesel, trosku tam byl v tom pridelovani otazek na zacatku chaoz...co se tyce mych zkusenosti s jednotlivymi zkousejicimi:

1) Skopal - R-stromy: tuhle otazku jsem tak nejak cekal :-) Bohuzel pan Skopal zkousi pro me dost neprijemnym stylem .. po prvni vete vas dokaze zaskocit nejakou treba i jednoduchou a ne spatne minenou otazkou, na kterou rychle nevite, co odpovedet a pak se do toho tak zamotate, ze zacnete placat nesmysly..on se vas snazi k necemu dokopat, ale kdyz nevite kam presne miri, da se to jen tezko odhadnout..navic z jeho vyrazu nejde vycist, jestli je to jeste v pohode nebo jste na pokraji vyhozeni :-) Nastesti jsem u pana Skopala delal predtim jednu zkousku, tak uz jsem vedel, ze takhle zkousi, ale zas tak zly to neni, jak to v prubehu zkousky vypada...navic me potesilo, ze me nerozebral hned na zacatek uplne a vcas toho nechal..

2) Pokorny - semantika Datalogu pomoci NPB
Takhle by se podle me melo u statnic zkouset. S prihlednutim k tomu, ze je clovek zkousen nejen z ty jedny otazky, ale i ctyrech dalsich. Pritom docela proklepnout, zjistit, co clovek umi, neumi a pustit. Zadnej stres.

3) Cepek - pseudopolynomialni algoritmy: typickej Cepek - ferovej pristup. Bere to tak, ze kdyz clovek neco nevi, je to jeho chyba, ale muze se to stat ... proste definice muze vypadnout a je blbost nechat cloveka pul hodiny sedet a vymejslet definici, kterou nezna..

4) Mlcek - vety o rekurzi: Ze zacatku jsme se bavili o tom, co jsem si pripravil, pak se to stocilo nekam, kde uz jsem se moc nechytal, ale prislo mi, ze mi spis chtel ukazat, jak se ty vety taky daj taky hezky a elegantne pouzit pro dukaz ruznejch kuriozit, takze to pak byla spis takova prednaska. Bohuzel jsem byl v takovym rozpolozeni, ze jsem si z ni moc neodnes :-) Kazdopadne docela pohoda.

5) Galambos - Veta o tranzitivnim uzaveru relace: jeste ze jsem si tu otazku nechal az na konec, jinak bych tam sedel asi az do vecera. Nebyl jsem jedinej, koho otazka tohoto zkousejiciho dost zdrzela, spis to bylo pravidlo. Styl zkouseni podobny tomu pana Skopala s tim rozdilem, ze "se teda hezky snazte, vas necham chvili uzrat" a takhle se to opakuje nekolikrat..si osobne myslim, ze tenhle styl zkouseni je pro matfyz potrebnej, ale nikoliv u statnic, kde ma clovek dalsi ctyri otazky. Uz takhle tam nektery lidi sedeli a "zrali" u tech statnic celkem pres pet hodin (nebo i dyl-vyhlaseni melo bejt ve tri, ale ve trictvrte prisla pani Dejmkova, at prej mame strpeni, ze dva lidi jsou jeste zkouseny. Zacinali vsichni v devet..) Vubec si neumim predstavit, ze by v jedny komisi bylo takovejchhle zkousejicich vic. Navic nutit lidi na fleku (navic u statnic pod takovym tlakem) vymejslet veci, ktery treba nikdy neslyseli, protoze v doporucenejch kurzech ke statnicim se neberou, ale podle nazoru zkousejiciho se "do toho tematu daj zahrnout" (abych nekrivdil - to nebyl zrovna muj pripad, ale u nekterejch kolegu jo) podle me neni uplne stastnej pristup..

Celkove bych rekl, ze se to da udelat, ale ten system se mi moc nelibi. Neslysel jsem o zadny jiny skole, kde by statnice trvaly takhle dlouho.. Celkove jsem dostal z diplomky jednicku (ale to je zas jina kapitola sama pro sebe), z ustniho dvojku...tipuju asi spis horsi, protoze vysledna znamka taky dvojka. Bylo nas tam snad 35 (podle pana Pokornyho historickej rekord :-), ustni neudelalo tusim asi 5 lidi.

==== Statnice - databaze 2: ====
1) N-ticovy kalkul (priklad relacie, dotaz, realne pouzitie) - Riha
Napisal som zakladne veci, ze je to rozsirenie jazyka logiky 1. radu. A uviedol som priklad na filmoch a hercoch. Realne pouzitie som nevedel. Zacali sme to rozoberat, presli sme ake veci su v jazyku logiky a ako si odpovedaju s NDK. Ked chcel to pouzitie a ja som to nevedel, tak mi napomohol poznamkou, aby som si ukazany dotaz napisal v SQL. Realne pouzitie je SQL :)
Aj ked som sa dost tazko nechytal na niektore otazky, tak to uzavrel tym, ze som vlastne vsetko podstatne napisal. Celkovo velmi prijemne skusanie.

2) SQL SELECT - Skopal
Mal to byt popis syntaxe. Teda co vsetko sa da selectom zapisat. Kolko ma casti, co robia, opytal sa ako sa vyhodnocuju, popisal som rozne spojenia a pokracovali sme pokecom nad vnorenymi dotazmi a fungovanim IN, ALL, EXIST. Tiez sme niekde po ceste chvilu kecali o agregovani riadkov, agregacnych funkciach.
Tiez celkom v pohode.

3) B-stromy a ich varianty - Kopecky
Napisal som si zakladne definicie B, B+, B* a VB stromov. Pobavili sme sa o redundantych/neredundantych stromoch. Potom o dotazoch na viacero atributov z coho sme sa dostali k hasovaniu a dotazom na ciastocnu zhodu a koncilo to iba otazkou na priestorove data. Tam stacilo povedat, ze je na to dobry R-strom. (Tiez niekde v debate padla otazka na paralelny pristup do B-stromu.)
Prijemne aj ked pomerne podrobne sa snazil preverit znalosti.

4) Vety o rekurzii a ich aplikacie - Mlcek
Napisal som 2 z 3 zakladnych viet. Ukazal som ako sa to pouzije pri dokaze Rice. Samozrejme nasledovala otazka na 3. z viet o rekurzii (resp. pevnom bode), co vlastne viedlo na program, ktory na kazdom vstupe vypise vlasny program. Aj ked som nebol 100%-tny vo vsetkom, tiez prijemne skusanie.

5) Aproximacne alg a schemy - Fiala
Pripraveny papier posluzil na prvu minutu, kedy si to skusajuci precital. Mal som tam plus minus vsetko. Este sa opytal preco nemozem TSP aproximovat s lubovolne malou chybou (v nejakom rozumnom case). Nevedel som , tak mi pomohol otazkou: Co sa stane, ak mi niekto da graf na 100 vrcholoch a povoli chybu pod 1%? Musel by som najst optimalne riesenie. Velmi rychla odpoved.

Celkovo som mal zo ustnej casti za 2.

==== Statnice - databaze 3: ====
Moje priprava 5 tydnu (po 9ti letech na mff clovek nechce nechat nic nahode...).

Na otazky i zkousejici jsem mel asi hodne stesti:

1) Datalog s negaci (Pokorny)
Co to je ten datalog s negaci, kde se muze negace vyskytovat. (Otazka.. a co kdyby byla negace v hlave pravidla?) Vylozil jsem kde je problem (vic minimalnich modelu), zadefinoval stratifikaci, algoritmus na vypocet datalogickeho programu s negaci, porovnal (bez dk) s Ar.

2) Dynamicke programovani (Fiala)
Nastesti zadna veta o dynamickem programovani. Stacilo rict k cemu je, jak se pouziva (odshora, odspodu). A uvest par prikladu - Fib. cisla, batoh a floyd warshall. Dal nasledovala otazka, jak jde pomoci algo pro soucet podmnozin - odpoved UPAS s prorezavanim seznamu.

3) Vety o rekurzi a jejich dusledky (+ Riceova veta) (Mlcek)
Formuloval jsem a dokazal Vo pevnem bode, Vo generovani PB a Riceovu vetu (+ jeji dusledek). Dale to uz byl jen dialog jak se daji ty vety aplikovat (program co vypise svuj kod). Dalsi otazky jako co je to ze predikat Psi e x konverguje - rek. spoc. (halting problem), co je to mna K, Ko, jejich ekvivalence (jiz bez dukazu jen ustne).

4) Uzamykaci protokoly, casova razitka (Riha)
Serializovatelnost rozvrhu, legalni rozvrh, dobre formovane transakce. Nevedel jsem si rady s pohledovou x konfliktovou ekvivalenci (nejak tak?). Dale casova razitka, jako priklad stromoveho protokolu jsem dal B-stromy se zamykanim a na zaver byla otazka na optimisticke algoritmy.

5) Indexace v DIS (Kopecky)
Boolske systemy - reprezentace matici - moc velke, signatury, zbytek ze mne musel pan Kopecky dost pacit (invertovany soubor, jak ho ziskame - setridim dvojice (term, dokument) vnejsim tridenim a pak k nim sestrojim ten invertovany index).
Vektorove systemy - formulovat vsechny vzorecky na TF, ITF, NTF, normalizovany vektor pro dokument. Takze tam jsem uz dalsi otazku nedostal..

Muj odhad 1-(2), 1, 1, 1-, 2(-) Celkem za 1

==== Statnice - databaze 4: ====

1.) Amortizovana zlozitost (Fiala)
2.) Nerozhodnutelne problemy (Mlcek - Halting a Riceova s dokazom, ostatne len nazov)
3.) DRK (Riha -kde sa vyuziva prakticky - QBE, Oracle - dake formulare ci co)
4.)xPath (Pokorny)
5.) vektorovy a boolovsky model (Kopecky - princip, tvar dotazu a odpovede, implementacia)

=== 18.9.2008 ===

; Hnětynka - distribuované objekty
: Napsal jsem krátký obecný kec, CORBA IDL, mapování do jazyků, pár problémů s nimi, POA, znínil pár jejich policy, stručně popsal Naming Service, zmínil Trading Service, v bodech popsal Java RMI. Hnětynka si to přečetl a pak se ptal na nějaké další "vychytávky":
:* dynamic invocation
:* zda se objekt vždy úspěšně zaserializuje
:* jak funguje Naming Service, kde se vezme reference na něj
:* zda se v RMI generují stuby a skeletony, (a nějaké další)
: Z těch doplnujících otázek jsem věděl (či uhodl) tak každou třetí, známka: 2 - 3 (asi)

; Tůma - podpora pro OOP v překladači
: Znal jsem jen principy (z "uživatelského" hlediska), jak se to překládá jsem vymýšlel. Prvotní řešení volání virtuálních metod Tůma označil za bezmála debilní (extrémě neefektivní, i když asi zhruba funkční), efektivní řešení ze mě vytáhl až návodnými otázkami. Přetypování a virtuální dědičnost jsem dal taky jen tak zhruba. Známka: 3

==  I4 (Diskrétní modely a algoritmy) ==

=== 2. 9. 2013 ===

'''Složitost''' (MJ): PSPACE a jeho úplnost. Definice, úplný problém, TQBF jako PSPACE-complete. Savichova věta. PH je celá v PSPACE. Bonus: jde udělat rekurze TQBFjen za O(1) na vrstvu)? (MJ říká ano.) Jaké jsou další PSPACE-complete problémy? (Třeba hry jako Sokoban.) Jsou randomizované třídy v PSPACE? (Ano.)

'''DS''' (Fiala,MJ): Vyhledávací stromy. Řekl jsem dospělácké věci: RB stromy jsou (2,4)-stromy, AVL jsou RB, RB jsou polovyvážené. Náhodné stromy jsou randomizovaný Quicksort. Splay tree, dynamická optimalita, statická optimalita. Počítání nebylo potřeba, ale chtělo by to trochu lépe znát operace.

'''Grafy''' (Valtr): Ramseyova teorie. Nekonečný Ramsey s důkazem, konečný jako důsledek. Erdös-Szekerés, Hales-Jewett (znění), Van der Waarden jako důsledek HJ. Dolní odhady jsem znal, ale neznal jsem dobře horní odhady. Rozmyslete si nějaké, třeba z konečného Ramseyho.

'''Kombinatorická optimalizace''' (Matoušek): Toky. Řekl jsem toky jako algoritmický a toky jako algebraický (nowhere-zero) problém, ale Matouška zajímal nejvíce optimalizační problém, i vícekriteriální toky. Doporučuji si projít základy Toků, cest a řezů. (Moc jsem je neuměl). Bonus: jak počítat párování algebraicky? (Přes permanent.)

=== 2. 9. 2013 (jiný student) ===

'''Vyčíslitelnost''' (Mareš): Riceova věta. S důkazem.

'''DS''' (Fiala): Třídění ve vnitřní a vnější paměti. Pokažen Mergesort v externí paměti. Rozhodovací strom.

=== 2. 9. 2013 (jiny student, jiny nez jiny student) ===
'''Slozitost''' (zadal matousek, zkousel l. kucera): Trida NP. Napsal jsem definici pres ndtm a certifikaty, a pak jsem se rozepisoval o hierarchii, ruznych redukcich, pcp theoremu, np-complete problemech, vztazich s dalsimi tridami... ale kucerovi se furt nelibila definice np (i kdyz byla spravne), takze jsme celou dobu babrali v detailech o turingacich

'''Datove struktury''' (zadal mares, zkousel l. kucera): Dynamisace datovych struktur. Stacilo popsat takovou tu vec z koubkovych skript, jak se to rozseka na podstruktury velikosti 2^i a amortisovane upocita. Poucen prubehem predchozi otazky jsem kuceru nepustil k dotazu a zvitezil.

'''Kombinatorika a grafy''' (valtr): parovani a toky. Hallova veta s naznakem dukazu, tutteho veta s naznakem dukazu, koenigova veta se slovy ze je equi maxflow-mincut, nekonecna hallova veta, maxflow-mincut dukaz pres ford-fulkerson, jeste jsem zminil o existujicich algoritmech (bez toho ze bych je nejak popisoval) -- dinitz, 3 indove, nagamochi-ibaraki, karger-stein. Valtr se jen zeptal na teoreticke aplikace maxflow-mincut, tak jsem rekl ze mengerova veta a linkovanost (coz neznal :) )

'''Kombinatorika a grafy''' (matousek): algebraicke vlastnosti grafu. Nepsal jsem vubec zadny dukaz, jen prehled tvrzeni, ze se napr. vezme adj matrix a pomoci rank argumentu se odvodi bounds na velikosti set systemu (oddtown, fisher inequality); ze se v tehle oblasti pouzivaji hodne self-symmetric graphy typu johnson ci kneser (napr. pro constructive lower bound na ramseyovky); o vlastnich cislech (nejake triviality typu ze existuji, ze diameter dava lb na pocet ruznych cisel, ze alg a geom multiplicity je stejna, ze jsou vsechna realna, nanejvys maxdeg...), ze se daji pouzit na ten moore bound, ze spectral gap koresponduje s expansi. Matousek se pak akorat ptal na nejake aplikace expanderu (na omezeni poctu rand bitu), na presnejsi zavislost spectral gapu a expanse napr. cheeger inequality (to jsem nevedel), na konkretni konstrukci expanderu (jen jsem rek gabber-galil, detaily nechtel), zig-zagy expandery (to jsem nevedel). A byl spokojen.


=== 9. 9. 2014 (Ještě jiný student, jiný než Jiný student a Jiný než jiný student)===

Komise: Zimmerman, MJ, Šámal, Pultr, Hladík, Klazar
Průběh: Všichn byli milý a ochotní a snažili se aby byla příjemná atmosféra.

Otázky:
Datovky(MJ): perfektní Hashování: popsal jsem 1-univerzální systém, jak se vytvoří a jak ho použiji na perfektní hashování. To jsem popsal a nastínil jak se to spočítá.

Vyčíslitelnost(MJ): Vlastnosti rekurzivních a rekurzivně spočetných množin: všechny definice, větu o RS a RS doplňku, množina K, převoditelnost, úplnost atd. Psal jsem přehledově, ale spoustu věcí i s náznakem důkazu s tím že bych ho případně rozšířil, kdyby bylo třeba. Měli tam patřit také charakterizace ČRF pomocí úsekových ORF.

(RS): Algebraické vlastnosti grafů: Tutteho polynom, vlastní čísla a jak je použít-zde mě aplikace moc nešly. Měl jsme připravené Moorovy grafy, ale úplně se mi to vykouřilo z hlavy že jsem je chtěl říct i v této otázce.

(RS): párování a toky v sítích: Edmonds, charakterizace PP, souvislost párování a toků (Hall,König), alg na klasické toky, dualita, celočíselnost, nakousl jsme nikde nulové toky a multikomoditní toky. 

celkově jsem čekal (2-3) dostal jsem 1. (vysledek všech 4×1, 1×2)

=== 9. 9. 2014 (jiný student, jiný než jiní studenti) ===

'''Složitost''' (Hladík): Savičova věta. Napsal jsem ve znění omylem rovnost místo jedné inkluze a dokázal jen tu jednu inkluzi. Když se mě pak Hladík ptal, co ta druhá inkluze, radši jsem po chvíli změnil znění věty, i když si ani jeden z nás nepamatoval, jestli tam rovnost je nebo není. Ještě jsem ukázal PSPACE = NPSPACE jako důsledek a byl spokojen.

'''Vyčíslitelnost''' (Hladík): Věty o rekurzi (slovně zmínil "a jejich použití"). Napsal jsem ty čtyři hlavní varianty (u dvou jsem jen prohlásil, že mají podobný důkaz jako ostatní) a Riceovu větu jako důsledek, ale Riceovu větu měl někdo jiný, tak jsem o ní musel mlčet (zůstala jen na papíře). Místo toho se zeptal na s-m-n větu (napsal jsem jen hrubé znění) a pak se mě zeptal na definici PRF a ČRF (jen jsem zhruba řekl definice základních fcí a operátorů), čímž jsme s touto otázkou skončili.

'''Kombinatorická optimalizace''' (Pultr): Problém obchodního cestujícího. Pultra zajímalo, co má vlastně zkoušet, ale nakonec vypadal, že všechno, co jsem řekl, dobře zná. A jak je u Pultra obvyklé, stačilo říct jen hlavní myšlenky důkazů. Ukázal jsem důkaz NP-těžkosti redukcí z Hamiltonovské kružnice, Christofidesův 3/2-apx. alg. a neaproximovatelnost, pokud vzdálenosti nesplňují trojúhelníkovou nerovnost. A byl spokojen. Pak se ptal, jestli znám nějaké použití, nenapadlo mě nic netriviálního, tak se rozpovídal o použití na výrobní zařízení, které musí objet všechny vyráběné čipy a něco na nich udělat.

'''Kombinatorika a grafy''' (Pultr): Algebraické vlastnosti grafů. Pultr se mě zeptal, jestli k tomu mám něco připraveno, odpověděl jsem, že ano, i když jsem si pak říkal, že by mi jinak třeba dal něco jiného a nechodil bych po tenkém ledě. K tomuhle jsem se naučil důkaz okolo Moorových grafů s obvodem 5 (viz Matouškův text 33 Miniatures). Nestihl jsem ho zrekonstruovat, když mě Pultr přerušil a ptal se na jiné algebraické vlastnosti. Řekl jsem expandery, čímž jsem se pustil do oblasti, v níž jsem si nebyl vůbec jistý. Naštěstí stačila definice hranové expanze a zmínka, že druhé největší vlastní číslo souvisí s expanzí. A byl spokojen.

Hladík mi ještě chtěl dát celočíselnost jako pátou otázku, čemuž jsem se vyhnul dotazem, kolik že máme dostat otázek :-) (správná odpověď byla čtyři, i když na jiných oborech se dává pět otázek, tak by se možná i na I4 mělo dávat pět otázek ... ale lobovat za to žádný student asi nebude :-)

Bylo nás pět (zkoušených) a obhajoby jsme stihli asi za dvě hodiny (každý cca 15 min. prezentace, pak předseda nebo vedoucí a oponent přečetli posudky, následovalo vyjádření k posudkům a případné dotazy). Zkouška pak trvala další necelé dvě hodiny. V průběhu byla jen menší pauza během porady komise nad známkami z diplomek.


[[Category: Státnice Informatika Mgr.]]