Zdroje

• Skupina mff-info na Yahoo! Groups – dotaz na "statnice"

• Diskuze na modry.cz – 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í.

IUI (Informatika - umělá inteligence)

2. 2. 2017

Obecně nevím známky u konkrétních otázek, ale celkově to bylo za 1.

• Základy složitosti a vyčíslitelnosti [Mlček] - Algoritmicky nerozhodnutelné problémy - V zásadě halting problém. Stačilo pečlivě definovat, naznačit proč existuje univerzální Turingův stroj a ukázat halting problém. Mluvil jsem i o Riceově větě, dostal jsem se do půlky důkazu ale o to mu tak úplně nešlo, pak chtěl vědět, jak z Riceovy věty okamžitě plyne Halting problém, to jsem nedal (za C zvolte doménu univerzální ČRF. tj. ČRF odpovídající UTS), ale prý to žádný student u státnic nedá, tak z toho žádný problém nedělal. Obecně byl šokován, že lidi neví co je to rekurzivní / rekurzivně spočetná množina a chtějí mluvit jen o jazycích a TS, ale vzal to a s Riceovou větu jsem byl skoro hvězda...

• Datové struktury [Fink] - Algoritmy využívající cache - Tady jsem plaval asi nejvíc. Dával jsem definici cache aware a cache oblivious, včetně toho že se tam analyzujou počty přenosů, ale dost jsem plaval v těch samotných algoritmech a v analýze počtu přenosů. Doporočuju projít pečlivě, neni to vždy jen "rekurzivně tak dlouho než se vejde do cache". Trochu jsem to asi zachránil důkazem efektivity LRU vs. OPT, který jsem měl nadrcený. Nevyhodil mě. Obecně ale Fink trávil se studenty nejvíc času, jestli je topil nebo jestli toho ostatní uměli o tolik víc to nevím.

• Strojové učení a jeho aplikace [Neruda] - Učení s učitelem a bez učitele - Pohoda. Zaprvé s Nerudou se dá vždycky mluvit, za druhé tohle je moje parketa. Popis problému, dělení supervised/unsupervised/reinforcement, spousta metod (linear classifier, kNN, decision trees/random forest, SVM, logistic regression, linear regression, z Reinforcement Q-learing, ADP, Temporal difference,...) Ptal se na různý loss funkce ale ne do podrobna (v SVM je hinge loss...). Zmínil jsem i lehce něco o neuronkách, ale ostatní metody naplnily čas bez problémů. Mohl bych tam mluvit celý den, nevim co by stačilo. Na boosting/bagging/bootstrapping, krosvalidaci apod. ani nedošlo.

• Lokalizace a mapování [Mareš] - Metody Monte Carlo - definoval jsem lokalizaci, popsal základní particle filter. Ptal se na úskalí - různé ztrácení, kidnap problem,... dalo se domyslet na místě. Pokud vám nestačí slidy Davida Obdržálka doporučuju Cyril Stachniss SLAM course: https://www.youtube.com/watch?v=U6vr3iNrwRA&list=PLgnQpQtFTOGQrZ4O5QzbIHgl3b1JHimN_ Došli jsme nakonec až ke SLAMu, resp. FastSLAM 1.0 pomocí particle filteru a malých EKF pro landmarky. Přešlo to spíš do diskuse o běžných potížích při MCL, na to že jsem to nikdy ani nenaprogramoval docela pohoda.

• Plánování a navigace [Vomlelová] - Základní plánovací algoritmy - popsal jsem plánovací problém a doménu, výrokovou i klasickou reprezentaci. Potom forward, backward, bidirectional search, lifting. Na STRIPS ani nedošlo (backward s liftingem), diskuse byla spíš o detailech (např. přesná definice cílového stavu - je to seznam predikátů, nebo je to množina stavů, nebo...?). Potom ještě plan space planning, ten chtěla, ale nakonec taky ne až do nejmenších detailů. Flaws/threats jsem popsal spíš myšlenkově než precizní definicí. Na Graphplan nedošlo vůbec.

2. 2. 2017 (jiný student)

Stejné zkouškové okruhy a komise jako předchozí záznam. Obecně byla komise příjemná. Byli jsme celkem čtyři, s tím že dva jsme si měli nejdříve připravit volitelné okruhy a druzí dva okruhy povinné. Zkoušející poté buď chodili nebo si člověk mohl "zamávat". Také když přišli tak případně byli (minimálně někteří) ochotni si vyslechnout povídání bez přípravy (s tím že by student kdyžtak chvilku času ještě dostal). Známku a výsledek SZZ jsme se dozvěděli téměř rovnou po dozkoušení poslední otázky každý student nezávisle, celkem to trvalo cca 2-3h od začátku.

• Základy složitosti a vyčíslitelnosti [Mlček] - Základní třídy složitosti a jejich vztahy -

• Datové struktury [Fink] - Haldy (k-regulární, binomiální) -

• Strojové učení a jeho aplikace [Neruda] - Evoluční algoritmy - popsat obecně EA/ES/EP/GP a trochu víc říct o jednom z nich. Zvolil jsem si GP a hledání předpisu funkce (stavbou funkčního stromu), což Neruda přivítal, že to je aspoň změna. Příjemné povídaní s Nerudou, občas to vypadalo že ho víc baví povídat než mne nechat mluvit :)

• Lokalizace a mapování [Vomlelová] - Vztah lokalizace a mapování, SLAM -

• Plánování a navigace [Mareš] - Základní navigační postupy: dead-reckoning, odometrie, triangulace a trilaterace, inerciální navigace. - Popis fungování jednotlivých metod, vhodné mít představu jak se co v praxi používá.

I1 (Teoretická informatika)

11.9.2017

• UI [Hric] - Plánování. Definoval sem plánovací doménu, plánovací problém. Popsal sem algoritmy dopředného a zpětného plánování a plánování v prostoru plánů. Hric četl celkem detailně, co sem napsal, měl jenom pár doplňujících otázek jako proč se v praxi používá zpětné plánování místo dopředného.

• Logika [Mlček] - Věta o úplnosti v predikátové logice. Popsal sem spíš tak osnovu důkazu než nějaké detaily: Vemem teorii, uděláme z ní Henkinovskou, rozšíříme na úplnou Henkinovskou, zkonstruujeme kanonickou strukturu, tu pak restringujeme na původní teorii a hurá, máme model T. K tomu definice Henkinovské teorie, úplné teorie, jak vypadají ty Henkinovy axiomy a konstanty, jak vypadá kanonická struktura. Důkazy žádných z těch lemmat sem nedělal.

Mlček tak prohlídl papír a řekl, ať mu teda povídám – tak sem povídal, co je na papíře, on mě po pár větách zastavil, že jestli není nějakej problém s tou konstrukcí Henkinovy teorie. Chtěl slyšet, že T musí být v jazyku bez proměnných. Pak sem povídal dalších pár vět, dostali sme se k rozšíření té Henkinovy teorie na úplnou. Pak se rozmluvil Mlček, že prý proč to de – to sem moc nevěděl, co mu říct, ale on ani moc nečekal, až mu něco odpovim, a rovnou že když model je spočetný, tak je to jednoduché, ale když je nespočetný, potřebuju axiom důkazu. Pak se rozmluvil nějak o modelech a vlastně sem ani nerozuměl, co povídá. :)

Nějak sem přimručoval – když se ptal, tak nechápavě, když vysvětloval, tak sem mručel chápavě. (Pořád nevim, o čem mluvil.) Pak se mě ptal na příklady nějaké úplné teorie – žádný sem moc nevymyslel, tak mi řekl, že teorie těles komplexních čísel. (Co sem pochytil, tak je úplná kvůli algebraické uzavřenosti. Nevim, jak tuhle informaci dát dohromady s Godelovými větami, které říkají, že každá teorie, která obsahuje aritmetiku, je neúplná – ale asi spíš něco nechápu já než Mlček.)

Pak sme se posunuli o kousek dál ke konzervativním rozšířením – a Mlček se hned začal ptát, jak je to s modely konz. rozšíření – jestli dokážu vzít model nějaké teorie a rozšířit ho tak, aby to bylo konzervativní rozšíření. To sem taky moc nevěděl. Řekl mi, jak se to dělá, ale moc sem to nepochopil. :)

Celkově to působilo spíš tak, že si Mlček chce povídat o logice než zkoušet. Po chvíli tohohle odešel – tvářil se docela spokojeně. (Dílčí známku nevim.)

Učil sem se ze Štěpánkových skript. Na Bc. sem dělal logiku u Mlčka, takže sem pořád měl přibližnou představu, jaký používá značení a definice (Mlček rád definuje symboly, Štěpánek rád všechno definoval slovně), takže sme si rozuměli. I když ty jeho otázky na modely ve Štěpánkovi nejsou a technicky vzato nejsou ani v oficiálních okruzích, pořád to stačilo na projití. Mlčkovy skripta sem při přípravě neotevřel ani jednou. :) Obecně mám pocit, že i když Mlček je s logikou o pár úrovní výš, než by měl být (mám pocit, že sylabus a státnicové okruhy ho prostě nudí a nezajímají ho), je to poměrně hodný zkoušející.

• Vyčíslitelnost [P. Kučera] - Algoritmicky nerozhodnutelné problémy – hlavně halting problém. Tak jsem napsal halting problém s důkazem, že je alg. neřešitelný. (Tzn. asi tak tři řádky.) Pak sem napsal definici množiny K, že je to ekvivalent halting problému ve vyčíslitelnosti. Uvedl sem Riceovu větu (bez důkazu) a že z ní plyne, že nejde efektivně poznat, jestli dva programy počítají tutéž funkci. Popsal sem necelý jeden papír – nevím, co bych k tomu dodával, když otázka je tak úzce zaměřená – tim spíš, když ji Kučera ještě víc omezil tim, že se mám zaměřit na halting problém.

Kučera si nechal převyprávět, co sem napsal. Pak se ptal, jak z K poznám, že nějaká množina je ekvivalentní halting problému – napsal sem, že je to, když pro A platí K ≤1 A a přidal sem definici 1-převoditelnosti. Kučera sice souhlasil, ale že proč 1-převoditelnost, že je to zbytečně silné. Tak sem zmínil m-převoditelnost, že jenom vynecháme prostotu té převodní funkce. Kučera zase, že jo, ale že je to pořád zbytečně silné. Tak sem řekl, že se ještě dá použít Turingovská převoditelnost – to už mu stačilo. Tvářil se spokojeně a odešel.

• Složitost [Mlček] - Savičova věta. Napsal sem větu, rekurzivní algoritmus pro zjištění, jestli jedna konfigurace je dosažitelná z druhé, ukázal hloubku rekurze, max. počet stavů původního stroje a prostorovou složitost na každou úroveň rekurze. Zase stěží jedna stránka popsaná. Mlček si to zběžně prohlídl, zeptal se, co ta věta vlastně říká (že z NTS umim vyrobit DTS, kterej potřebuje prostor, kterej je jenom čtverec původního prostoru). Přišlo mi, že to moc detailně nečetl a že ani neví, na co se ptát, tak zase spokojeně odešel.

• Neprocedurální programování [Hric] - Definice definovaná neúspěchem. Tak sem obecně popsal, jak se v logickém programování odvodí, že predikát neuspěje (pokusim se ho splnit, pokud se povede, tak selžu, jinak se buď zacyklim donekonečna nebo uspěju). Napsal sem, že v Prologu je to not(P) :- P, !, fail. not(P). Řekl sem, že pro program booked(4). booked(7). a dotaz not(booked(X)), Prolog sice řekne no, ale nedá žádné X, pro které booked(X) neplatí. Ještě sem heslovitě uvedl předpoklad uzavřeného světa. Tady sem toho měl asi jenom půl stránky. :)

Hric se ptal na věci okolo toho dotazu not(booked(X)) – že jak souvisí s negací v normální logice a kdy se not chová jako negace (když mám termy bez proměnných – problémy vznikají, když se ptám na něco s volnou proměnnou). Pak chvíli tápal, na co se zeptat, nic ho nenapadlo, tak spokojeně odešel.

Celkově za 1. Dílčí výsledky neznám.

Z ostatních zkušeností tady mi příde, že lidi se občas snažej vygenerovat co nejvíc informací, který aspoň přibližně souvisej s otázkou – mně přijde, že skutečně stačí odpovědět jenom na otázku a ušetřit si tim čas. :) (Samozřejmě, pokud otázku tak úplně nevíte, napsat aspoň něco je daleko lepší než nenapsat nic.)

08.6.2017

• Vyčíslitelnost [Mlček] - Primitivně a částečně rekurzivní funkce. První otázka super, napsal jsem definice a ty základní věci okolo, ekvivalenci s TS, nevlastní podmnožiny atp. Pan Mlček ze mě pak mámil, co dokážeme říct o definičním oboru universální funkce jedné proměnné, respektive zda dokážeme říct,proč ta množina není rekursivní. Když jsem netušil, na co se ptá, tak mi ukázal, že je to ekvivalení zápisu Halting problému.

• Datové struktury [Fink] - Binární vyhledávací stromy, trie a B-stromy. Druhá skvělá otázka, i když jsem se na ní dost zapotil. Nejdřív jsem se dost zamotal v rotaci AVL stromu, když si na dvou patrech potřebuju prorotovat prostřední větev, a pak kde se používají B-stromy a červenočerné stromy v praxi.(B stromy snad v kompilátoru, červenočerné v nějaké kolexi v Cčku. Jinak, vzorečky potřeba nebyly, i když jsem jich pár měl, kdybych o nich nemluvil sám, tak se nezeptá. Jinak opět definice a jak probíhají operace, občas padly další nepříjemné otázky, ale snad nebyly na výsledek tak zásadní.)

• Adaptivní agenti [Pilát] - Komunikace a ontologie. U komunikace jsme si povídali v podstatě o tom,co má Roman neruda ve slajdech z multiagentních systémů, u ontologie chtěl Martin slyšet, že v ní funguje hiearchie, a že v ní lze mít vynucená některá pravidla, například neprázdnost určitého seznamu, což ze mě postupně tahal.

• Neuronové sítě [Mrázová] - Evoluční algoritmy a věta o schématech, aplikace s neuronovými sítěmi - Další dobrá otázka. Mluvil jsem zpatra, ale tu větu o schématech jsem si měl rozplánovat předem. Je dobré si pamatovat ten odhad na pravděpodobnost přežití mutace, že ten exponent je přibližně roven násobku. Pak stačilo odpovědět, jak se používají evoluční algoritmy s neuronovými sítěmi, oběma směry...(přes GA lze mj. určovat váhy NN, NN zase může například počítat fitnes GA)

• Umělá inteligence [Hric] - Plánováni - V podstatě to, co je v Bartákových slidech.

Na státnicích nás bylo 11, 4 z teoretické informatiky a 7 z umělé inteligence. Rozdělili nás na 2 skupiny po 6 a 5 lidech a v S4ce nás pak zkoušeli. Na začátku se zkoušející trochu zamotali, protože někteří jedeme podle starách osnov a tak hledali koho mají zkoušet z čeho. Obecně bych řekl, že všichni zkoušející byli hodní, a z naší skupiny jsme prošli všichni. 21, 22, 2*3.

13.9.2016

• Složitost [Gregor] - Aproximační algoritmy a schémata - definice etc, pak jsem popsal aprox pro bin packing, jednořádkový důkaz poměru, ukázal jsem úpas pro součet podmnožiny, bez důkazu. Gregor neznal ten algoritmus pro součet podmnožiny, ale přišlo mu že to funguje, takže ok. Nakonec se mě zeptal, abych vymyslel co nejlepší aprox algoritmus (ve smyslu poměrů), co zjistí kolika barvami je obarvitelný rovinný graf. Hodně mi pomáhal, ale bylo to jednoduchý, stačí poznat jestli je graf bipartitní => 2 barvy, nebo nemá hrany =>1 barva. Jinak odpovědět 4 => aprox poměr 4/3.

• Datové struktury [Gregor] - Vyhledávací stromy - základní BVS, vyvážené stromy, perfektní, AVL, důkaz výšky, příklad jedné rotace (+,-,. ve vrcholech podle rozdílu a jeden z případů), definice RB stromů, idea důkazu výšky, bez operace, že to je podobné jak v AVL, (a,b) stromy a ukázka operace insert a štěpení. Gregor spokojený, akorát se nakonec ptal, jak bych konstruoval co perfektní strom, když budu mít množinu prvků a k nim pravděpodobnosti toho jak budou vybraný. Takže perfektní a navíc ještě optimalizovat aby ty s vysokou pravděpodobností byly vysoko. Já nevěděl, řekl sem že bych to ocheatoval - seřadit prvky s rostoucí pravděpodobností a v tomhle pořadí je vložit do Splay stromu. To ho pobavilo, že to asi neni blbej nápad, ale nebude to perfektní, pak mi řekl jak se to dělá (dynamické programování a prakticky procházení všech permutací).

• Adaptivní agenti a evoluce [Hric] - Zpětnovazební učení - Typy učení a pozice RL v ní (je to učení s učitelem, ale ne tak jako ostatní metody s učitelem). Základní princip - posloupnost stav, akce, reward za dosažení určitých stavů. Existence optimální policy, co bude maximalizovat odměnu, RL se k téhle snaží přiblížit. Q-učení s tabulkou SxA očekávaných odměn, propagace odměny do minulosti. Zmínka problému explore/exploit. Hric se mě ptal na detaily o tom, jak to funguje - nakreslení obrázku nějaké jednoduché šachovnicové vyhledávání cesty a to, že to chce udělat gradient v té matici odměny. Pak se ptal jak by se dal řešit explore/exploit, já že můžeme s nějakou v průběhu učení klesající pravděpodobností explorovat, jinak exploitovat. Nakonec se ptal jak by se dalo zrychlit učení, že se to přes ty řetězce dost pomalu propaguje. Nějak sem to okecával, protože sem nevěděl, tak mi pak načtrtl nějakou konkrétní hru, kde jsem vymyslel že řešením bylo vždy po získání odměny vypropagovat odměnu po celém řetězci najednou.

• Neuronové sítě [Mrázová] - Kohonenovy mapy - klasika, cíl metody (mapování n dimenzí do 2 se zachováním topologie), mechanismus výběru vítězného neuronu, učení, zmínka o rostoucích SOM, hierarchických SOM. Měl sem chybu v vzorečku pro učení, tak ze mě Mrázová vytáhla jak to opravit, nakreslení obrázků. Mrázová se mě pak zeptala jestli máme zaručené, že to nějak dobře bude zachovávat tu topologii, dala mi hint slovo motýlek. Já okecával že to asi zaručené nemáme ale že většinou to dopadne dobře. Pro 1D mapy máme důkaz, jinak ne, degenerovaný případ - motýlek kde mapa udělá takový svazek ve prostředku.

• Logika [Gregor] - Věta o kompaktnosti - Tahle otázka mě rozložila, věděl jsem znění, ale udělal jsem v něm chybu (T0 jsem napsal spočetné, má být konečné) a důkaz jsem si jen pamatoval, že přes kompaktnost součinu topologických prostorů. Mlček to dokazuje přímo, Gregor po mě chtěl důkaz téhle věty jako důsledku věty o úplnosti. Když máme úplnost tak je důkaz na řádek (T|=A <=> T|-A a tedy má konečný důkaz v T, z něj dostanem to T0). Pak ze mě tahal nějaké aplikace, řekl jsem že tim můžem dokazovat úplnost, pak jsem řekl že o nekonečných objektech můžeme dokazovat všelicos právě díky kompaktnosti. Chtěl příklad, nic sem nevěděl, řekl že třeba o nekonečných grafech můžeme věci dokazovat takhle. S odřenýma ušima mě nevyhodil xD

• Slozitost [Kucera] - polynomialna hierarchia. okrem klasiky se ptal na typicky problem, ktory spada do sigma n pro libovolne n. Nakoniec mi pomohol si spomenut, ze omezene QBF je ono. Tady rozne what-ifs: co kdyby PH spolabovala, kdyby se rovnala PSSPACE,...

• Vycislitelnost [Gregor] - RM a RSM. Trosku som zahaproval, ked sa ptal na mnozinu, ktora nie je RSM a asi 5 minut tahal zo mna, ze je to doplnok K. (Lebo podla postovej vety keby nebola, tak K je rekurzivna)

• Lambda kalkulus [Hric] - Typovany lambda kalkulus, rozdiely medzi Church a Curry, tu vetu o substitucii v presnom zneni zo mna tahal

• Neuronky [Mrazova] - Vrstevnate site. Backprop, odvodit vahy. Hodne se ji libil uvod, ked som zacal, ze backprop proste len vypocitava gradient a ze je to len efektivna metoda na pocitanie gradientu zlozenej funkcie, ze bez nej by sme proste klasicky derivovali slozenu funkci. K momentu som len povedal, ze usmernuje to ten pohyb, aby to neoscilovalo. K metodam druheho radu som povedal len, ze je to rychlejsie na pocitanie (ona potom povedala ze proto, ze se snazi uz odhadnut priamo to minimum, miesto pomaleho posunu "slepeckou hulkou dolu z kopce") a ze ma to velku pamatovu narocnost, kvoli Hessovskym maticiam. Ziadne vzorce k tymto dalsim veciam nebolo potreba, jedine zakaldny backprop.

• Logika [Gregor] - Rezolucia. Tu som popisal docela obstojne, popisal som, ze je to zamitaci procedura a jej kroky, SLD rezoluciu. Korektnost rezolucie. Nevedel som uplnost, ale asi to nebol az taky problem.

• Datove struktury [Hric] - B-stromy a ich varianty. Popisal som definiciu, insert, delete (slovami). Varianty som spomenul upravu pre paralelne pouzitie, A-sort, a hladinovo prepojene s prstom. Pan Hric bol velmi prijemny, porozpraval mi aj nejake zaujimavosti :).

• Slozitost [Gregor] - Pseudopolynomialne algoritmy a silna np-uplnost. Napisal som definicie a popisal pseudopolynomialny algoritmus pre riesenie batohu. Nejaku chvilku zo mna mlatil ako ukazeme ze TSP je silne np-uplny (prevodom hamiltonovskej kruznice s vahami 1 pre hrany a 2 pre nehrany na rozhodovacie tsp kde max dlzka tour je pocet vrcholov povodneho grafu).

• Umela inteligence [Hric] - Strojove uceni obecne a konkretne rozhodovaci stromy. Popisal som ID3, zadefinoval rozhodovaci strom a stacilo. Padla otazka co s tym ked vieme ze napr 5% trenovacich dat ma nespravne urcenu triedu a

• Neuronky [Mrazova] - Vrstevnate site. Backprop, strategie pre urychlenie ucenia. Velmi zhruba som popisal backprop (len zaverecne vzorecky pre akutalizaciu vah), ako sa pocita vystup neuronky. Velmi vagne som tiez popisal momentovu metodu.

• Logika [Kucera ml] - Predikatova logika, realizace splnitelnost a pravdivost.

21.6.2016

• Složitost [Petr Kučera] - Savičova věta (klasika). Zmínil jsem, proč má být funkce S(n) aspoň logaritmická (konfigurace musí evidovat m.j. pozici hlavy čtecí pásky, což zabere aspoň log(n) znaků). Dále pamatujte, že čtecí páska se do paměťové složitosti nepočítá (jinak by nebylo možné realizovat S(n) "podlineární").

• Datové struktury [Jan Hric] - B-stromy a jejich varianty. Popsal jsem (a,b)-stromy, operace na nich. Podle toho jsem definoval B-stromy, B+, B*. Ještě jsem popsal neredundantní stromy, kde jsou hodnoty i ve vnitřních uzlech.

• Neuronové sítě [Iveta Mrazova] - Samoorganizujici site a rozebrat Kohonenovy mapy.

• Umělá inteligence [Iveta Mrazova] - Rozhodovací stromy, ID3 algoritmus.

• Logika a výpočtová složitost [Petr Gregor] - Věta o kompaktnosti. Napsal jsem větu a důkaz, vycházející z věty o úplnosti. Ptal se mě na příklady použití, což jsem moc nevěděl, zmínil jsem akorát barevnost grafů (nekonečný graf je k-obarvitelný <=> každý konečný podgraf je k-obarvitelný). Dozvěděl jsem se, že kompaktnost ještě souvisí s kompaktností topologických prostorů, axiomem výběru atd.

• Složitost [Petr Gregor] - Úplné problémy pre rôzne triedy zložitosti. Popísal som triedy P,NP,PSPACE, #P, rôzne typy prevoditeľnosti (poly time, log space, prevoditeľnosť pre #P), zadefinoval úplnosť pre tieto triedy vymenoval úplné problémy. Nakoniec chcel aj o nejakom probléme dokázať, že je úplným tak som popísal myšlienku dôkazu je QBF je PSPACE-úplný.

• Neuronové sítě [Iveta Mrázová] - Viacvrstevanté neuronové siete a algoritmus spätného šírenia. Klasika, ale zasekol somsa pri odvodzovaní úpravy váh. Našťastie Mrázová bola milá a pomohla mi to všetko správne odvodiť.

• Vyčíslielnost [Petr Kučera] - Rekurzívne a rekurzívne spočetné množiny a ich vlastnosti. Obšírna otázka, neviem čo presne tam chcú. Ja som napísal definície a potom čo mi napadlo - uzavretosť na prienik, zjednotenie a doplnok, Postova vetu, RS množiny ako obory hodnôt, generovanie (cez úsekové funkcie)... Nevedel som čo všetko dokazovať, stihol som Postovu vetu, a potom chcel aspoň niečo z viet o generovaní RSM, tak som dokázal že rekurzívna množina je oborom hodnôt nejakej rastúcej úsekovej funkcie.

• Umelá inteligencia [Ján Hric] - Hry, minimax a α-β prerezávanie. Algoritmy som popísal slovne a ilustroval na obrázku, stačilo to čo má Barták v slajdoch.

• Logika a výpočtová složitost [Petr Kučera] - Predikátová logika, realizácia jazyka, splňovanie a pravdivosť formulí. Definoval som jazyk predikátovej logiky, štruktúru, realizáciu funkčných a predikátových symbolov. Ďalej induktívnu definíciu hodnoty termu v štruktúre pri danom ohodnotení a následne induktívnu definíciu splnenosti formule v štruktúre pri ohodnotení. Na konci ešte platnosť formule v štruktúre a logickú platnosť obecne. Takmer bez pripomienok.

• Složitost [Petr Kučera] - polynomiální hierarchie - napsal jsem TS s orákulem, turingovskou převoditelnost jazyků, relativizované třídy, nakreslil jsem PH + základní vztahy, PH je v PSPACE s důkazem a kolabs PH. Pozor na ten obrázek PH, pokud neumíte (jako já) přesně vysvětlit, co znamená. Stejně tak je potřeba znát víc vztahů, já znal jen ty základní a moc to nestačilo. Dostával jsem otázky, zda lze jazyk turingovsky převést na svůj doplněk, co by se stalo kdyby PH=PSPACE, PH=P a k tomu pak zazněla i otázka, v jakém prostoru se převádí problémy z P a co by se stalo, kdyby se místo v logaritmickém meziprostoru převádělo v polynomiálním prostoru.

• Vyčíslitelnost [Petr Gregor] - algoritmicky nerozhodnutelné problémy - definoval jsem rekurzivní jazyk, algoritmicky rozhodnutelný problém, Halting problém s důkazem, Riceovu větu s důkazem, připsal jsem radši i větu o rekurzi, kterou jsem používal v důkazu Rice. Nastínil jsem postův korespondenční problém a definoval K + pár definic kolem RM a RSM. Zazněla otázka, proč doplněk K nemůže být rekurzivně spočetný a zda znám nějaké další nerozhodnutelné problémy třeba ze života.

• Neprocedurální programování [Jan Hric] - postačující podmínky ukončení výpočtu - popsal jsem stupňové zobrazení, rekurentní klauzuli, rekurentní program, omezený dotaz a že pak program terminuje, popsal jsem úspěšnou SLD-derivaci, Königovo lemma. Zdálo se mi toho málo, tak jsem přidal MM algoritmus a přes něj se dostal k occur-checku a modovanosti. Hrice zajímalo hlavně stupňové zobrazení, jak by se definovalo třeba pro délku seznamu a jestli znám i nějaké lepší.

• Logika a výpočtová složitost [Petr Gregor] - věty o úplnosti - napsal jsem pro VL i PL. Dotaz zazněl snad jen, proč jsou ty věty tak důležité.

• Neuronové sítě [Iveta Mrázová] - Hebbovské učení + Hopfieldův model - začal jsem asociativními paměťmi, popsal Hebbovské učení a Hopfieldův model - důkaz jsem neznal. Dotazy padaly, co se dá dělat, když u Hebbovského učení nejsou vektory ortogonální a jak řešit u Hopfielda uvíznutí v lokálním minimu.

• Průběh zkoušky - Celkově nás bylo 8. Rozdělili si nás do dvou skupin po 4, každá měla svoji komisi (naše: Iveta Mrázová, Jan Hric, Petr Gregor, Petr Kučera) a svoji učebnu (naše: S9). U nás to pak probíhalo tak, že byl rozvrh, kdy vždycky po 45 minutách přišel další zkoušející a mezitím jsme si připravovali příslušnou otázku. Celkově za jedna. Známky celkem: tři jedničky, jedna dvojka.

• Neprocedurální programování [Jan Hric] - Typovaný lambda kalkul, přístupy, odvozovací pravidla - Napsala jsem k čemu je dobré typování, rozebrala přístupy lambda-Curry a lambda-Church a pravidla odvození. Měl pár doplňujících otázek na rozdíly mezi nimi.

• Neuronové sítě [Iveta Mrázová] - Perceptron a jeho učení, důkaz konvergence, přihrádkový algoritmus učení - Popsala, co to je perceptron, algoritmus jeho učení a důkaz konvergence, tam jsem se trochu zasekla při výpočtu toho čitatele. O přihrádkovým algoritmu jsem neměla tušení (jsou to poslední 3 stránky v tom perceptronovým pdfku a ani jsem je nečetla), přes kupu obrázků jsme se k němu nějak dopracovaly.

• Složitost [Petr Gregor] - Pseudopolynomiální algoritmy a silná NP úplnost - Zadefinovala jsem pseudopolynomiální algoritmus, číselný problém a pár definic okolo. Trochu jsme se zasekli, protože mi tam chyběl předpoklad P != NP. Pak jsme rozebrali pseudopolynomiální algoritmus pro součet podmnožiny, v tom se hodně vrtal, aby zjistil, jestli si fakt rozumíme. Potom silně NP úplné problémy, mluvili jsme o TSP a proč zůstává silně NP úplný. Ptal se na problém, který je silně NP úplný a není číselný, pak jenom číselný. Gregor je supr, tohle byla prima část. Jediná známka co vím - lepší 2.

• Vyčíslitelnost [Jan Hric] - Algoritmicky nerozhodnutelné problémy - Napsala jsem definici rozhodovacího problému a ne/rozhodnutelného problému, v bodech potom pár příkladů těch nerozhodnutelných. Halting problem a Riceovu větu s důkazy. Ještě se mě ptal na převoditelnost mezi nerozhodnutelnými problémy, ale pak zkonstatoval, že se to asi neučí a že neva.

• Logika a výpočtová složitost [Petr Kučera] - Věta o korektnosti v PL - Tohle byla asi nevtipnější část zkoušky. Kučera se doslova svalil vedle mě na sedačku a začal si to znuděně číst.:D Popsala ten důkaz s ukázkou, že modus ponens je zachovává platnost. Doplňující otázky na to, co znamená důkaz a realizace jazyka, líbily se mu paralely definic do VL. Bylo hotovo asi za 5 minut.

• Průběh zkoušky - na začátku si nás členové komise obešli a každému zadali otázky ze "svých" oborů. Byli jsme 4 studenti na 5 členů komise, ale zkoušeli mě jen 4 z nich. Zjevně není povinné, aby se na nás vystřídali všichni... Při zadávání témat obvykle prohlásili něco typu "Co říkáte na Gödelovy věty?" nebo "Chcete EM algoritmus?". Když pak odpovíte, že "více se mi líbily věty o rekurzi" a "EM radši ne", tak se usmějou a krize je zažehnána =). Po zadání jsme dostali 20 minut na přípravu, pak Mlček prohlásil, že už bychom se mohli nechat zkoušet. Ale nebylo to tak drsné - když jsem potřeboval ještě dopsat přípravu mezi "zkouškami" na další okruh, tak nikdo nenamítal.

• Datové struktury [neznámý] - B-stromy a jejich varianty. Popsal jsem (a,b)-stromy, operace na nich, pak B-stromy, B+, B*, algoritmus A-sort. Chtěl důkaz hloubky stromu, amortizovaný počet operací rozdělení či spojení uzlů, kdy se A-sort vyplatí.

• Vyčíslitelnost [J. Mlček] - Věty o rekurzi a jejich aplikace. Připravil jsem si pouze znění 4 vět z wiki skript, zbytek jsem dodal ústně. Mlček se ptal na definice ČRF, PRF a univerzální funkce, ale hlavně kvůli tomu, že sám všechno značí jinak... Zeptal se na S-m-n větu, jestli ji už pro tuto látku máme k dispozici, ani znění nechtěl. Popsal jsem myšlenku důkazu VR1 a VR4, pak se ptal na aplikace - k čemu bych ty věty použil. Zmínil jsem Riceovu větu, ekvivalenci programů, existenci programu, co vypíše sám sebe. Chtěl vědět, jestli dokážu použít Riceovu větu k důkazu Halting problému - netušil jsem, nevadilo to. Nakonec jsme diskutovali nad důkazem existence programu, co vypíše sám sebe.

• Umělá inteligence [M. Vomlelová] - Zpětnovazební učení - popsal jsem princip, odlišnosti od ostatních učení, chtěla nějakou rovnici.

• Agenti / evoluční algoritmy [R. Neruda] - Rozdíly mezi GA, ES, EP a GP - z povrchního popisu odlišností se stal důkladný rozbor všech...

• Robotika [R. Neruda] - Plánovací vs reflexivní řízení (a mezistupně).

10.2.2016

• Vycislitelnost[Petr Gregor a Petr Kučera] - Rekurzivne spocetne mnoziny a jejich vlastnosti

Chvíli jsme se dohadovali, co to znamená, že dokážeme efektivně zjistit, že prvek do množiny patří (dokážete to vy nebo já?).

Napsal jsem definice a ukázal pár vět s náznaky důkazů. Celkově to nebylo moc dobré, což Gregor okomentoval slovy, že

jsem se moc nepředvedl a odešel. Čekal jsem, že je konec, ale nebyl...

• Neuronové sítě[Iveta Mrazova] - Samoorganizujici site a rozebrat Kohonenovy mapy.

Klasika. Pozor, ať nepřehodíte operandy odečítání ve vzorci u KM jako já, prý to studenti dělají často.

Jinak jsme si příjemně popovídali o neuronových sítích.

• Datové struktury[Petr Kučera] - B-stromy a jejich varianty

Napsal jsem, jak je definovaný, popsal operace i s příklady a složitostí. Dále jsem uvedl B+ a B*.

Byl jsem tázán na to, jestli musí být klíč uložený až v listech (redundantní nebo neredundantní B stromy).

Poté se ptal na vnitřní a vnější pamět. To jsem moc netušil, ale zachránil mě Fink, který si přisedl a řekl, že se to

v DS nebere. Mám pocit, že se to bere v OZD a to jsem nemel. Chvilku se dohadovali a pak se mě ptali na aplikaci.

Uvedl jsem třeba A-sort a za jakych podminek je vyhodny (kdyz je tam malo inverzi) a intervalový dotazy.

• Agenti a EVA[Martin Pilát] - Věta o schématech

Větu jsem popsal i s důkazem, přisednuvší si Iveta Mrazová a Jan Hric se ptali na doplňující otázky. Třeba na elitismus,

na hypotézu o stavebních blocích, co EVě nejde atd...

• AI [Jan Hric] - Zpetnovazebni uceni

Napsal jsem asi všechno co tam bylo, popsal rozdíly mezi algoritmy, zdůraznil protichůdnost explorace vs exploatace.

Hric se ptal na nějaké zajímavosti, které mě nechal hádat a pak mi je prozradil.

Celkově bych řekl, že ta povinná část mi připomínala takové grilování a volitelná byla o dost příjemnější. Možná to bylo

i otázkami, které mi příliš nesedly. Každopádně při hodnocení byli daleko méně přísní, než bych byl já. Bál jsem se

vyhazovu kvůli vyčíslitelnosti, ale ocenili můj výkon dvojkou. Byli jsme na státnicích 4 a všichni uspěli (za dvě, myslím).

=== 10. 9. 2015 === (Psano v listopadu 2015, nektere veci si pamatuju uz jen strucne a umel jsem je tehdy asi lepe.)

• Vycislitelnost[Antonin Kucera] - Algoritmicky nerozhodnutelne problemy.

Definoval jsem TS, tridy jazyku, halting problem a ukazal proc je algoritmicky nerozhodnutelny.

• Datove struktury[Ondrej Pangrac] - Stromove vyhledavaci struktury.

Jednoducha otazka. Vyjmenoval jsem vse co splnuje vagni zadani otazky (stromy, haldy, trie, splay...). Uvedl jsem pouziti ruznych struktur. Nevedel jsem do jakeho detailu to rozpracovat, po dotazu mi bylo receno abych popsal rotace. Nakreslil jsem nejake obrazky a tim bylo vlastne hotovo.

• Vyrokova a predikatova logika[Vladan Majerech] - Veta o uplnosti predikatove logiky.

Majerech zacal typickym "Zvolte si cislo... aha, trojka, te se preklada na jedenactku." :) No nebyl jsem rad. Nicmene jsem definoval vse potrebne, jako kanonicke struktury, Henkinovy teorie, uplne teorie atd. Uvedl jsem zneni vsech moznych pomocnych vet a naznacil princip dukazu stylem: Mam teorii, vezmu jeji kanonickou strukturu, udelam uplnou Henkinovu teorii, vezmu model a jeho restrikce je to co potrebuju. Na zaklade tech pomocnych vet. Dokazat jsem to neumel, ale to po me nastesti nechtel.

• Agenti[Jan Hric]: Zpetnovazebni uceni.

Popsal jsem aktivni a pasivni, proc a kdy se to ktere pouziva a nejake metody (jmena algoritmu a princip, napsat jsem je neumel) ktere se v tom kterem pripade daji uzit. Detaily jsem neumel, ale vedel jsem ktera bije a dokazal jsem o tom necelou stranku popsat. Chvili se ptal, ale kdyz zjistil ze nic kloudneho ze me uz nevypaci, stacilo mu to.

• Umela inteligence[Marta Vomlelova]: Markovske modely.

Docela podobne otazka te z Agentu, tvarili se, ze to nebylo chtene ale uz se stalo. Popsal jsem jednoduchy markovsky model, markovsky predpoklad a uvedl jednoduchy priklad. Napsal jsem jmena a princip nejakych algoritmu, ale zase bez detailu. Na ty se me chvili ptala, moc jsem nevedel, ale po chvilku nakopavani jsem spravny vzorec napsal. Jejimi slovy: "Prehled mate, detaily neznate."

Celkove 2. Dejte si nejmene mesic poctiveho uceni. Klidne i vice. Zpetne by se hodilo absolvovat Slozitost II, vrele doporucuji. Samostudium nekterych otazek z tohoto predmetu je velice zdlouhave.

11. 6. 2015

• Neuronove site[Iveta Mrazova] - Samoorganizujici site a rozebrat Kohonenovy mapy.

Klasika.

• Umela inteligence[Marta Vomlelová] - Bayesovské sítě.

Tady jsem si nebyl moc jisty, ale nakonec jsem vyplodil: Ruzne vztahy pro pravdepodobnosti v souvislosti s Bayesem. Jak vypada Bayesovska sit. Jeji konstrukce (sestaveni, urceni pravdepodobnostnich tabulek) a jak vypada odvozovani v ni.

• Agenti[Roman Neruda] - Architektury agentů.

Plánovací vs reaktivní. Hybridní architektury. BDI. Prijemne povidani.

• Slozitost[Vladan Majerech]: Polynomiální hiearchie.

• zkuste se zamyslet nad pojmem uplneho problemu v polynomialni hiearchii Definice TS s orakulem. Relativizovane tridy. Zavedeni PH. Dukaz PH je v PSPACE. Povidali jsme si pak o kolabovani hiearchie a jak to prave souvisi s tim, kdybychom meli ten PH-uplny problem. Ukazal hezky dukaz, ze PH je v PSPACE pres alternujci kvatifikatory a QBF.

• Vycislitelnost[Petr Gregor]: Castecne a primitivne rekurzivni funkce.

Vypocetni model. Ekvivalentni s TS (veta+dukaz). Definice primitivnich funkci a operatoru. Definice CRF, ORF, PRF. Veta o hiearchii CRF (+ dukaz).

Odchodil jsem tenhle rok teprve Slozitost I a II, takze tam jsem to tak nejak dobre umel, aniz bych se to musel znova ucit. Stejne tak i Datovky I a II.

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 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 $O(1+c\alpha )$). A pak dolní odhad na $|I|$. 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 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.

3. 6. 2015

Zkoušeli mě ze všeho Ondra Pangrác a Luděk Kučera. Otázka většinou byla 2-3 hesla z toho, co se máme naučit, takže opravdu nebyl problém, že k některému tématu jsme našli nekonečně věcí, ale k jiným spíše po málu.

Složitost Úplné problémy pro různé třídy, Polynomiální hierarchie: Pověděl jsem NP-úplnost, dokázal KACHL (stručně jsem vysvětlil, jak na to, technicky jsem to nedělal a ani to nikdo nechtěl), ukázal #P, P, PSPACE, jenom u P jsem si nevzpoměl na úplný problém. Taktéž jsem nahlédnul, jak na ukázání #P-úplného #SAT-u (přes KACHL, jak jinak) a zmínil, že permanent je #P-complete. Bylo toho docela dost, ale ještě jsem zadefinoval PH, řekl o kolapsu na k-té úrovni, ukázal že pokud by byla nějaká z inkluzí ostrá tak je P != NP, Kučera se ptal, proč by NP(NP) mělo být silnější než NP.

Kombinatorická optimalizace Grafové algoritmy: řekl jsem si, že než dělat zvířetníky a vystavovat se riziku, že se někde seknu u složitosti, tak jsem raději nějaké ukázal. Speciálně pravděpodobnostní Min-Cut (bez důkazu) a Edmondsův květinkový (s úkazem a analýzou). Min-Cut by prý nechtěli slyšet, kdyby měl někdo jiný pravděpodobnostní algoritmy, ale on je nikdo neměl. K Edmondsovi se ptali, jestli existuje lepší algoritmus a jak je rychlý, tak jsem řekl, že ano, že si myslím, něco okolo n log m, ale že ho neznám. Nabídnul jsem ještě 3 Indy, které jsem nesepsal, protože už jsem toho napsal až dost, ale nedošlo na ně.

Pravděpodobnostní metody a algoritmy Kombinatorické počítání, vytvořující funkce, rekurence. Tady jsem byl rád za sloučené otázky -- protože k čistému počítání jsem toho neměl moc nachystáno a jenom jednoduché věci. Takhle jsem zadefinoval vytvořující funkce, včetně exponenciálních, operace nad nimi, n-tý člen posloupnosti z vytvořky, větu o výpočtu vzorce pro n-tý člen pomocí charakteristického polynomu (bez důkazu a násobných kořenů -- ty jsem jenom zmínil, že se to zkomplikuje), souvislost s vytvořkami (formát vytvořky), pak jsem naznačil jak vypočítat n-té Fibonacciho číslo pomocí tohoto tvrzení (ústně), a dokázal Master theorem.

Datovky Stromy, haldy, trie: To byla obsáhlá otázka a protože jsem už mluvil asi hodinu, moc jsme se tomu nevěnovali. Pověděl jsem zvěřinec včetně pár zajímavých věcí (treap, skiplist, van Embde Boas), řekl ekvivalenci RB a 2,4-stromu, prohlásil, že bych něco řekl třeba o Fibonacciho haldách, ale to se obešlo bez větších detailů.

Přišlo mi, že jsem byl zkoušený cca půl hodinky (plus příprava), ale prý se to blížilo spíš hodině, ale celou dobu jsem prakticky mluvil o tom, co jsem měl připraveno. Popsal jsem 5 listů A4 oboustranně a nebyla tam ani půlka toho, co bylo potřeba říct, takže napsat se to prakticky asi nedá. Ty datovky byly krátké, asi proto, že už tak jsem byl zkoušený dost dlouho a asi jsem se tvářil dost suverénně, že to umím (a takyže ano ;-).

Určitě bylo dobré říkat jenom to, čím jsem si jistý -- typicky nevadilo, když jsem něco neřekl (když je to důležité, tak se zeptají), ale očekávám že by vadilo, kdybych tvrdil nějaké bludy. U Grafových algoritmů budoucím generacím hrozí, že se budou ptát na konkrétní algoritmy, takže by bylo asi dobré se naučit pro každý problém nějaké slušné algoritmy na takové úrovni, aby se daly vyložit a říct o nich proč fungují a jak rychlé jsou (tady asi stačí náhled, obzvláště pokud je analýza komplikovaná -- viděl bych to na hrubý odhad dokázat, a dobrý vyslovit).

Na termínu dostali všichni za 1 (a bylo nás pět)

8. 6. 2016

Složitost: NP-úplnost, aproximační algoritmy, aproximační schemata - definice NP, NPÚ, Cook-Levinova věta a myšlenka důkazu (KACHL), další NPÚ problémy, rozdílná aproximovatelnost různých NPÚ problémů, v souvislosti s tím definice AS/PAS/ÚPAS.

Vyčíslitelnost: Nerozhodnutelné problémy - definice rozhodnutelných problémů, halting problemu, K0 a K a důkaz, že nejsou rekurzivní. Riceova věta.

Kombinatorika a teorie grafů: Ramseyova Teorie - formuloval jsem Turánovu větu s myšlenkou důkazu (která prý do RT nepatří), pak několik variant Ramseyových vět, dvě s myšlenkou důkazu. Pak ještě formulace Hales-Jewett a Van der Waerden jako důsledek.

Kombinatorická optimalizace: Teorie mnohostěnů a elipsoidová metoda - dotazy zhruba v rozsahu knih prof. Matouška - Introduction to Discrete Geometry - kapitola o polynomech, Lineární programování a lineární algebra pro informatiky - elipsoidová metoda. Ale věděl jsem toho dost málo, tak třeba by přišly složitější dotazy, kdybych znal odpovědi alespoň na ty snadné.

Všichni dostali dvě otázky obecné a dvě otázky oborové. Zkoušející byli velmi příjemní, doplňující dotazy většinou byly na úplné základy. Proti některým zkušenostem tady na stránce mi přišlo, že mnohem podrobněji byly zkoušené ty oborové otázky než ty obecné (ale měl jsem na každé jinou komisi, tedy to mohlo být tím).

8. 6. 2016

Složitost a Vyčíslitelnost: Algoritmicky nerozhodnutelné problémy - Definície Turingovho stroja, ČRF, rekurzívnych a rek. spočetných množín, K0 a K sú rekurzívne spočetné, ale nie rekurzívne + dôkaz, Riceova veta + dôkaz.

Datové struktury: Hašování, univerzální hašování - Definícia hašovacej funkcie a kolízie, prehľad rôznych typov hašovania, kukaččí hašování + dôkaz o pravdepodobnosti cyklu v grafe, c-univerzálny systém a lemma o strednom počte prvkov v priehradke, 1-univerzálny systém zo skalárneho súčinu

Nelineární programování: Kvadratické programování - Charakterizácia konvexity cez pozitívnu semidefinitnosť, prevod zo set partitioning na maximalizáciu konv. kvadratickej funkcie, aplikácia duality na konv. kvadratický program, charakterizácia optimality pomocou gradientu + dôkaz

Vícekriteriální a celočíselné programování: Unimodularita + dôkaz Hoffman-Kruskalovej vety, prehľad metód (Branch-and-bound, sečné nadroviny, heuristiky), aplikácia na TSP (modelovanie podmienky na hamiltonovskú kružnicu, základná hrebeňová nerovnosť + dôkaz) a problém batohu (cover nerovnosti)

6. 9. 2017

Datové struktury: Hašování, univerzální hašování - rychlý přehled, motivace a definice c-univerzálního systému, střední počet kolizí, konstrukce 1-univerzálního systému podle Mareše, použití na konstrukci perfektní hašovací funkce.

Složitost a Vyčíslitelnost: Savichova věta - definice prostorové konstruovatelnosti, lemma o počtu konfigurací, obecná Savichova věta. Důsledek pro polynomiální prostor.

Složitost a Vyčíslitelnost: Pravděpodobnostní algoritmy - definice pravděpodobnostního TM, definice tříd: RP, co-RP, ZPP, BPP. Amplifikace chyby. Vztahy pravděpodobnostních tříd mezi sebou a s P, NP, PSPACE.

Nelineární programování: Konvexní množiny, konvexní funkce a jejich zobecnění - základní definice, oddělitelnost, různé charakterizace KF a vlastnosti konvexní optimalizace (množina optimálních řešení je konvexní, každé lokální opt je globální), definice kvazikonvexních funkcí a jaké vlastnosti konvexní optimalizace jsou zachovány. Lagrangeova dualita, důkaz silné duality pro konvexní funkce f, g a lineární h se Slaterovou podmínkou.

Algebraické a topologické metody v informatice: Základy obecné topologie - definice pomocí okolí a pomocí otevřených množin, separační axiomy. Příklady prostorů splňujících jednotlivé axiomy. Topologie důležité v informatice (Scott). Definice báze, subbáze, pokrytí, kompaktnosti. Alexanderovo lemma s důkazem. Tichonovova věta, Heine-Borelova věta.

Kategorie v informatice: Kategorie a struktury využívané v informatice - zrecyklována část o částečných uspořádáních z algebraických metod. Definice uspořádání, horní a dolní meze, suprema, infima. Definice polosvazu, svazu, úplného svazu. V úplných svazech jsou infima zadarmo, důkaz. Souvislost s teorií domén: definice usměrněnosti, DCPOs, aproximovatelnost, Bourbakiho věta s důkazem, Kleeneho věta s důkazem, souvislost s denotační sémantikou. Algebraický pohled na svazy, distributivní svazy, filtry (prvofiltry) a ideály (prvoideály), Birkhoffova věta a důkaz.

Zamotal jsem se trochu v amplifikacích chyb u RP a BPP, a v definicích kompaktnosti v euklidovských a metrických prostorech (to se velmi stydím), kde jsem plácl několik hloupostí - prostě stres. Ostatní otázky mě asi zachránily, protože mě nakonec nevyhodili. Protože u státnic chyběl prof. Pultr a kategorie se nikomu očividně zkoušet nechtěly, tak jsem byl doslovně požádán abych se věnoval svazům.

Category:%20Státnice%20Informatika%20Mgr.