== 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) =
{{:Státnice_-_Informatika_-_Zkazky_/_zkušenosti/I2}}
== 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.]]
