Státnice - Informatika - Zkazky / zkušenosti

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. 2*1, 2*2, 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)

Databázové systémy

16.6.2015

Rtrees (Hoksza) - guttman, greene - chtěl nakreslit nějaký příklad rstromu na papír a souvislost s B-Stromy, R+ krátce, R*: split, reinsert - ty už moc nezkoumal

Standardy SQL (Loloč) - cca 1*A4 velkým písmem, moc se už neptal

Relační kalkuly (Skopal, ke konci i prof.Pokorný) - napsal jsem všechno co vím, měl jsem chybu v příkladu DRK - jenom se tomu zasmál

Vše (!) o hašování (Majerech, MJ) - popsal jsem asi 4 papiry - pořád jsme vtipkovali a ani jsme to neprošli celý, prof. Pokorný je už ode mě musel odehnat jinak bysme tam kecali ještě dneska :), skončili jsme někde před univerzálním/perfektním - MJovi jsem pochválil že ve své nové učebnici na ADS, Univerzální hashování vysvetluje na "MIT" konstrukci :)

Algoritmicky nerozhodnutelné problémy, halting problem (Kučera, ke konci i Majerech) - prolítnul můj důkaz L_HALT a chtěl dokázat problem: "ekvivalence 2 TS" je RSJ nebo RJ? jsem se s tím v životě nesetkal, tak jsem jenom něco málo odvodil z definice a vlastností m-převoditelnosti, ale asi to na vyhazov nebylo

celkem za 2, ale měl jsem štěstí na zkoušející - u většiny z nich jsem byl na konzultaci během učení na státnice, tak mi věřili že jsem se to fakt učil :)

1. NP úplné problémy, Cook-Levinová věta (Majerech) - nadefinovala jsem: trida NP pres cert., polynom. prevoditelnost a jeji vlastnosti, NP-tezkost, NP-uplnost. Cook - Levinovu vetu jsem dokazala pres kachlikovani. Zminila jsem dalsi NP-uplne problemy (bez dukazu)

2. Univerzalni hasovani (Mareš) - co to je a na co je dobre, myslenka UH, konstrukce 1-univerzalniho systemu s dukazem proc je univerzalni (podle wiki http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_Ha%C5%A1ov%C3%A1n%C3%AD_I2#Univerz.C3.A1ln.C3.AD_hashov.C3.A1n.C3.AD_.286.C3.97.F0.9F.8E.93.29)

3. Relacni algebry (Skopal) - dala jsem na papir co je RA a jake ma operace, jakou ma RA minimalnou mnozinu operaci, poradi vyplneni, co je relacne uplny jazyk, ekvivalentni dotaz. Pak jsem musela napsat nekolik dotazu podle zadani.

4. R-stromy a jejich vlastnosti (Pokorný) - defenice R-stromu, nakres (pekny priklad je tady http://gis.vsb.cz/GIS_Ostrava/GIS_Ova_2000/Sbornik/Pokorny/Referat.htm), vyhledavani v R-stromech, stepeni (guttman, greene) jsem popsala na prikladech (viz. http://wiki.matfyz.cz/wiki/Implementace_datab%C3%A1zov%C3%BDch_syst%C3%A9m%C5%AF/RTree)

5. Huffmanovo kodovani (Holubová) - treba bylo zakodovat a dekodovat nejaky text pomoci statiskeho a dynamickeho huff. kodovani. Vysvetlit v cem je rozdil ( pri statickem kodovani k dekodovani potrebujeme tabulku s kodami). Jednoznacnost dekodovani zarucuje prefixovost - jednotliva kodova slova nejsou prefixem zadneho jineho slova. (dobre vysvetleni dynamickeho huffmana je tady http://www.person.vsb.cz/archivcd/FEI/PD/Animace%20SWF/06_Adaptivni_Huffman.swf)

6. 2. 2015 (db)

Složitost a vycíslitelnost - Aproximacní algoritmy

Definice, chtel pomerovou i relativni chybu. Ukazal jsem algoritmus pro BIN PACKING, ktery je nejhure 2x horsi nez optimalni algoritmus. Pak definice aproximacniho schematu, polynomialniho apr. sch. i uplnepolynomialniho apr. schematu. Byl jsem dotazan, zda znam nejake schema (Batoh podle poznmek pana Kucery) a jake schema to je (uplne polynomialni nebo jen polynomialni).

Datové struktury (Kopecky) - Vyvazovani binarnich vyhledavacich stromu

AVL + CC stromy. Dokazal jsem logaritmickou vysku CC stromu (ani dukaz AVL neni moc tezky). Popsal jsem vyvazovani a trochu zavahal u tezsiho prikladu vyvazeni CC stromu.

Formální základy databázové technologie (Knap) - Relacni kalkuly a algebry

Kalkuly jsou zalozene na predikatove logice 1. radu, mohou obsahovat nebezpecna pravidla atd. Algebra muze byt pozitivni (bez mnozinoveho rozdilu), nema nebezpecna pravidla. Pak jsem byl dotazan na to, jak se v relacni algebre zapise prunik - pomoci sjednoceni a selekce.

Databázové modely a jazyky (Pokorny) - Stratifikovany Datalog s negaci

Popsal jsem co je stratifikace. Program je stratifikovatelny, kdyz neexistuje v zavislostnim grafu cyklus s negativni hranou. Kdyz je program stratifikovatelny, tak ma MPB (minimalni pevny bod). Vyhodnoceni - pravidla se rozdeli do vrstev a postupne se od prvni vrstvy program vyhodnocuje algoritmem pro Datalog bez negace, tj. naivnim ci semi-naivnim pristupem.

Implementace databázových systému (Holubova) - Huffmanovo kódování (statické, dynamické)

Hned na zacatku mi bylo receno, ze se mam zamerit na dynamicke H. kodovani. Mel jsem cokoliv zakodovat a dekodovat.

18. 9. 2014 (db)

Společná část:

1) NP-úplné problémy Definoval jsem nedeterministický Turingův stroj, třídu NTIME, NP-úplnost a dokázal převod obecného NTS počítajícího nějaký NP problém na KACHL (Cook-Levinova věta). Na závěr jsem zmínil, že ještě existují další NP-úplné problémy např. SAT, Batoh, Obchodní cestující atd. Žádné další převody jsem nespecifikoval. Tato odpověď byla přijata bez jediné otázky.

2) B-stromy a jejich varianty Popsal jsem definice, co splňují, operace, vyváženosti a jaké jsou varianty ((ne)redundantní, B+, B*). Pak chtěl pan Kopecký vědět, k čemu jsou dobré (zmínil jsem indexování) a dlouho se ptal na různé detaily (např. jak zabránit zamykání celého B-stromu při insertu pokud se ke stromu přistupuje paralelně - lze provádět dopředný split již naplněného uzlu, jaká varianta stromu je nejlepší pro indexování, které atributy v DB jsou vhodné pro indexování - záleží např. na doméně, atd.)

Databázová část:

1) Relační kalkuly Popsal jsem NRK, DRK, jak se v nich dotazuje (na příkladu), dále jsem zmínil doménově závislé dotazy, neomezené, problémy a jak je řešit a bezpečné formule (eliminace všeobecného kvantifikátoru, omezení volných proměnných atd.). To stačilo.

2) Objektové rozšíření relačního modelu dat K této otázce jsem toho upřímně zase tak moc nevěděl. Jen jsem napsal, že lze definovat vlastní typy, třídy, metody, že existují pole a reference (REF) a že je to implementováno v SQL. Pak jsem s panem Pokorným vedl diskusi, kde se vyptával na různé věci, např. chtěl vědět, jestli může existovat třída sama o sobě (ne - musí být vždy uložená v tabulce), chtěl slyšel o ID v třídách, jak jsou uložené v tabulkách, kde se definují metody (ve třídách), apod. Nějak jsem to s jeho pomocí vyplodil a celkově byl myslím spokojený.

3) Zotavení po chybě systému Zmínil jsem ukládání operací v transakcích do logu (žurnál), dále jak a kdy se ukládá log na disk, jak probíhá samotné zotavení (UNDO, REDO - kdy co) a ještě jsem popsal politiky zápisu nových dat do DB (okamžitý/odkládaný zápis). Zkoušel mě pan Říha, který byl velice příjemný, ale chtěl vědět ještě více informací (jak se udržuje identifikace transakcí v logu, kdy se ukládají savepointy, ...) a já jsem se do toho trochu zamotal a některé věci popletl, ale nakonec taky v pohodě.

Celkově jsem dostal z ústní za 2. Z mého pohledu to mohlo být tak mezi 1 - 2, ale jednotlivé známky se člověk v průběhu nedozví. Byl jsem hotový asi jako první z celé státnicové skupiny přibližně za 2 hodiny. Zkoušející byli hodně příjemní, snažili se pomáhat a když člověk znal alespoň základy, tak se nikoho nesnažili potopit. Samozřejmě záleží na konkrétní komisi, co jsem slyšel (a i zažil), tak někteří zkoušející toho chtějí mnohem více a někomu stačí pouze klíčové principy.

18. 9. 2014

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

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

Datové struktury - Vyvazovani binarnich vyhledavacich stromu

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

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

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

SELECT *

FROM table1, table2

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

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

30.5.2012

U nás dopadli všichni dobře, 3 databázisti (každý jeden předmět změněný) jsme byli a byl tam i jeden z distr systémů myslím. Každopádně moje otázky byly:

Umělá inteligence - A* algoritmus Datovky - Hashování, řešení kolizí, srovnání metod Složitost & Vyčíslitelnost - Pseudopolynomiální algoritmy Databáze 1. okruh - Relační úplnost Databáze 2. okruh - Implementace operací relační algebry (JOIN)

30.5.2012

Já jsem měl všechny tři výběrové okruhy z databází (+ ty dva společné). Dostal jsem následující otázky:

1) Algoritmicky nerozhodnutelné problémy Napsal jsem Halting problém + ten jednoduchý důkaz. Dále jsem napsal Riceovu větu a jak souvisí s halting problémem. Nakonec jsem napsal Postův korespondenční problém. To zkoušejícímu stačilo a nebyly žádné další otázky.

2) Třídění ve vnitřní a vnější paměti Napsal jsem dva algoritmy třídění ve vnitřní paměti - QuickSort a MergeSort. U obou jsem dokázal časovou složitost ( u QuickSortu v průměrném případě). Dále jsem popsal externí mergesort + jak se vyrábějí běhy pomocí dvojité haldy. Úplně nakonec jsem popsal a dokázal dolní odhad časové složitosti třídění pomocí porovnávání. Zkoušející se zeptal jenom na třídění bez porovnávání - řekl jsem CountSort se zmínkou o složitosti a to mu stačilo.

3) Věta o tranzitivním uzávěru relace Napsal jsem definici tranzitivního uzávěru, znění věty a důkaz podle slidů prof. Pokorného. Až na drobnou chybu v definici tranzitivního úzávěru, kterou jsem opravil, to stačilo.

4) Booleovský a vektorový model Slovy jsem popsal oba modely. U Booleovského jsem popsal, jak se indexuje, jak se vybírají termy a jak vypadají dotazy. Zmínil jsem se o složitosti počítání relevance. Dále jsem popsal vektorový model, jak vypadají dotazy apod. Zmínil jsem se, jak se počítá TF a ITF. Zkoušející se jen zeptal na pár otázek a byl spokojen.

5) R-stromy Napsal jsem, k čemu jsou dobré, definici a štěpení uzlů dle Guttmana a Greeneové. Dále jsem se zmínil o některých variantách R stromů. Zkoušející se pak jen zeptali na pár otázek.

Z ústní jsem měl 1, z diplomky 3 celková známka 2. Řekl bych, že nejde o těžkou zkoušku, ale je potřeba se dobře připravit a hlavně netápat v jednoduchostech. Učil jsem se přes šest týdnů a domnívám se, že je to až moc. Přeji hodně štěstí těm, které to ještě čeká!

13. 9. 2011

take se pridam, mel jsem Operacni systemy, Databazove modely a jazyky, Architektura pocitacu a siti

Prvni byly DATOVKY - postarsi pan, ktereho jsem nikdy predetim nevidel. A hned po ranu...bum prask...univerzalni a perfektni hasovani, abychom se nenudili. Tady mi hodne pomohla prednaska z MIT http://videolectures.net/mit6046jf05_leiserson_lec08/ a to, ze neznal koubkovy definice a konstrukce. No, neco jsem tam tvoril, obcas vypadal zmatene, obcas ze to tak nejak zna taky...nakonec vypadal spokojene

Dalsi DMJ - take postarsi pan, ktereho jsem vubec neznal - SQL standardy- pohoda, rikam si. Nejak jsem to tam vypsal, co se ktery rok udalo. Projizdel to a pak se zarazil u rekurzivniho SQL - to byla zasadni chyba, ze jsem zminil! Hned se v tom zacal hrabat a padala slova jako Minimalni pevny bod, Tranzitivni uzaver a jine sproste vyrazy. Docela jsem si zaplaval, ptz hledat Min PB v SQL vyrazech neni zrovna moje kazdodenni hobby. Neco jsem tam nakonec vzdy vymyslel, zkousejici byl hodny a trpelivy. Nakonec se tvaril v pohode. Ne horsi nez 2, vypadal spokojene

OSY - Bulej - File systemy. Na OSy velky pozor, jsou daleko zradnejsi nez se zdaji byt a wiki.matfyz ne vzdy staci jen na projiti. Proto jsem se na ne pripravil zdaleka nejlepe (procetl Tannenbauma i kusy Silberschatze). Pro Buleje bylo nejdulezitejsi ukazat pri nejake ceste co se presne deje s diskem, odkud/ jak se dozvi co dal a tak.. Vsechno jsem umel i zdarne odpovidal, ale presto dokazal vykoulet par tak detailnich dokazu, ktere jsem fakt netusil a jsem si jisty, ze treba ve zminenych knihach, skriptech nebo na prednasce se do takovych podrobnosti nikdo nedostal. 1/2

APS - Peterka - certifikaty. Prekvapilo me, ze se chce bavit 20min jen o certifikatech. Nejak ze siroka jsem to popsal i PGP a plno veci okolo. Vsechno dulezite jsem vedel - pak par detailnejsi veci, ktere jsem netusil (i pravni zalezitosti). Potom: "To jste se s panem Benesem neucili?". "Ja jsem pana Benese uz asi 6 let nevidel, ale jsem si jisty, ze takhle do podrobnosti urcite ne":) Tak prehodil na IPsec - par dotazu a konec. Asi za 1. Pohodicka

Vycislitelnost - Majerech - CRF + RM + RSM - tady jsem kliku, ze jsem si vylosoval zrovna toto, ptz jinak bych tam mohl u Majerecha sedet doted.:) Vypsal jsem vsechny ty definice, nejdulezitejsi vety (Postovu jsem si dovolil i dokazat, coz je u me velmi nezvykle) a ruzna tvrzeni okolo, na ktere jsem si vzpomnel. Ptal se na usekovou fci a generovani bodu - to jsem tapal a radsi hned rekl, ze nevim (jak toto muze byt nekdy osvobozujici:) a zlehka nejake uzaverove vlastnosti. 1-

13. 9. 2011

Chtěl bych se podělit o specifika mých zkoušejících, abyste věděli, jak odpovídat, abyste si co nejlépe rozuměli.

Pokorný: Formální základy DB technologie

Otázka: Datalog s negací

Způsob zkoušení: Profesor si přípravu nepřečte pořádně, na škodu studentovi. Očekával jsem, že je hodný, nevyžaduje moc (např. kdybych si vytáhl větu o tr. uzávěru, nechtěl by důkaz), tak jsem se ani neobhajoval; nijak jsem se nechtěl hádat u státnic. Měl jsem popsané asi dvě stránky. Jednou z prvních otázek bylo: "A jak vypadá ten Datalog?" Zas a znovu, jako se stalo jiným, i já jsem spletl termíny term/proměnná/predikát. To, že má člověk praxi v prologu/datalogu, ještě nestačí k tomu, aby správně vysvětlil syntaxi. Dá se říct, že v Datalogu P(x) :- A(x), B(x) je něco jako A(x) & B(x) => P(x) v logice 1. řádu.

Doporučuji psát obecně, ne hned příklady. Profesor si dá záležet na detailech (např. u stratifikace se jednotlivé vrstvy píší jako P1, P2, ..., Pn, tedy čárky místo sjednocení, protože sjednocení by znamenalo, že nám nezáleží na pořadí). Ale kvůli takovým detailům zas nevyhazuje.

Bulej: Operační systémy

Otázka: Synchronizace (řeknete mi proč a jak, na závěr implementujete např. problém producera/consumenta se semaforama).

Způsob zkoušení: Známku mi zkoušející řekl (nabízel) již během zkoušení, i se zdůvodněním: "Umíte to, ale musel jsem to z vás tahat, na jedničku bych čekal, že to vyložíte sám." Začalo to tím, že jsem přípravu stihl asi jen do třetiny a celý zbytek jsem odpovídal již interaktivně. Chtěl jsem povídat o tom, co ho zajímá, právě proto jsem ho nechal se ptát... Z toho plyne, že je lepší předvést své znalosti sám. A také, jak rozdílně může vidět zkoušený a zkoušející tu samou situaci ("atomickou instrukci jsem z vás tahal", přitom bych to v přípravě měl, kdybych v ní pokračoval; ale to nevadí). Proto bylo od něj velmi korektní, že to zdůvodnění řekl. Byl ochoten se o známce bavit; já jsem (dvojku) bral.

Odpověď: Povídal jsem podle obsahu v Tannenbaumovi: Modern Operating Systems (i v knihovně MFF). Pro někoho je tato knížka příliš redundantní, pro mě ideální.

Peterka: Architektura počítačů a sítí

Otázka: Síťové technologie (Ethernet, Wi-Fi), hlavně Wi-Fi.

Způsob zkoušení: Neřekl známku, tak nevím, jak to vnímal. Já jsem toho uměl málo, hodně mi toho vysvětlil.

Odpověď: Když jsou dvě věci v otázce, je dobré je porovnat. Tedy přístupová metoda CSMA/CD u Ethernetu a CSMA/CA u většiny Wi-Fi, to stojí za to vysvětlit a porovnat.

Majerech: Datové struktury

Otázka: Haldy

Co a jak zkouší: Dobrý je přehled o haldách obecně (co od nich nejlepšího můžu očekávat, jakou asymptotickou/amortizovanou složitost). Logaritmus tam vždy u nějaké operace vždy bude. d-reg. haldy prý nesnáší, ale v klidu je zkoušel. Odráží se totiž od toho, co máte napsané. Řekl, že nemám zmiňovat leftist haldy, když nevím, jak vypadají, že by se na to neptal.

Moje poznámka k Majerechovi: Na něj jsem se těšil, na cvičeních (kdysi dávno) byla vidět jeho brilantní inteligence a rychlost myšlení. Páni, dostat takové vysvětlení Fibonacciho hald, jako jsem dostal u státnic, kvůli tomu by se oplatilo jít na konzultaci. Věřím, že by byl ochoten to vysvětlit (když byl teď ochoten).

Kučera (mladší): Složitost a vyčíslitelnost

Otázka: Algoritmicky nerozhodnutelné problémy

Způsob zkoušení: Zdá se, že mu jde o témata, které mají praktický dopad (např. halting problem). Ptal se, jestli znám ještě další nerozhodnutelný problém. Dostali jsme se i k Riceově větě, ale bránil mi ji dokazovat, protože to nebylo v otázce. Známku mi neříkal.

S Majerechem zkoušeli někoho společně. Uklidňovali ho, že mu chtějí pomoct.

9. 2. 2010 (db)

Upresním celkovú štatistiku: 28 ľudí celkovo, 9 štátnicami neprešlo. Odhadujem, že 3ja z toho ale nemali dopísanú diplomku.

Ja som mal okruh databázy: komisia: Pokorný, Holan, Kopecký, Říha.

Otázky:

ČRF(Holan) - K splneniu stačila napísať detfinícia, operátory, funkcie. Ukázať neostré inklúzie medzi ČRF, ORF, PRF. Vysvetliť prečo sa zavádza abstrakcia ČRF, ďalej som spomenul ekvalenciu TS - ČRF, ostatné RAM, Post, ... len ústne. Prešli sme prípravu na papieri, asi jediná otázka bola na Godelovo číslo v dôkaze o uni. funkcii pre PRF a Holan povedal, že mu to stačí.

R-Stromy(Pokorný) - Zadefinovať, k čomu slúžia, nákres, štiepenie Gutmann, Green. Rozhovor pokračoval k MOO, MOK - aproximáciám, aké sú výhody jednotlivých prístupov - náročnosť uloženia vs. schopnosť aproximácie. Žiadne detaily, stačilo rozumieť. R+ stromy som len popísal kritériá výberu osi a distribúcie, vravel som, že to kludne na papier dopíšem, ale Pokorný to zjavne nevyžadoval.

Doménový kalkul (Říha) - Na papier som napísal väčšinu informácii z Pokorného skrípt, definícia, bezpečné výrazy, 1-2 príklady, použitie - to som našiel na inej diskusii - a to Říhu potešilo, že som tam mal. Bohužiaľ otázky Říhu smerovali k logike, ktorú som si už nepamätal a neopakoval. Takže najprv som z dvoch možností skúšal uhádnuť správnu, ale trafil stále špatne. Naviac som sa do toho začínal zamotávať a akosi som už nedokázal racionálne premýšľať. Červenal som sa i za ušami, ale nakoniec to Říha zhodnotil tak, že všetko podstatné bolo na papieri a tie otázky boli nad požadovaný rámec a prepustil ma. Odporúčam ujasniť si základy a spoľahlivo vedieť, čo znamená PRL 1.řádu, 2.řádu, čo je term, funkč. symbol, formula, pred. symbol, voľná premenná atp. Po tomto skúšaní som značne znervóznel a spomínanie na ďalšie učivo bolo o dosť ťažšie.

Bin. vyvažovacie stromy (Kopecký) - stromy som zadefinoval (BS, AVL, CC), popísal member, insert, delete - obrázky, jednotlivé prípady, rotácie ČČ som nerozpisoval - napriek tomu, že som sa to učil, nervy hrali a nebol som to schopný dať na papier. Takže som popísal slovne, koľko akých prípadov nastane. Porovnal som medzi sebou ČČ a AVL stromy, povedal dôvod, prečo sa zavádzajú. Napísal som podstatné z dôkazu o výške oboch. Kopecký vyzeral spokojne a do technických detailov nevŕtal. Ďalšie otázky smerovali k optimálnym vyhľ. stromom - popísal som slovne konštrukciu - dynam. programovanie, spomenul možné zlepšenie zložitosti z kubickej na kvadratickú. Rozložiteľnosť úlohy. Pýtal sa na stromy s príslušnou amort. zložitosťou, či nejaké poznám. Odpovedal som, že poznám Splay stromy - popísal som, k čomu sú dobré, ako fungujú zhruba - Splay a prvok hore. Prečo to má v praxi dobré vlastnosti. To mu stačilo, povedal, že otázka o Splay tr. bola nad rámec, že len skúšal, kam siahajú znalosti.

Sémantika datalogu pomocou NPB (Pokorný) - Posledná otázka, čas už tlačil - Pokorný musel za 45 min. odísť, tak sme sa dali do rozpracovanej otázky. V podstate príjemný rozhovor, na papieri som mal to, čo som si pamätal zo skrípt, akurát mi to veľmi nedávalo dokopy zmysel Skúšajúci bol ale vynikajúci, pýtal sa návodne, prípadne to doplnil. Nič detailné, ani nevyžadoval formalizmy. Ja som zodpovedal čo je to min. pevný bod, ako sa vyhodnocuje, ako sa vyhodnocujú datalog. programy, ako vyzerá EDB, IDB.

Prekvapila ma celková známka 1, myslel som si, že u Říhu som tak na 3- i tá posledná odpoveď bola trochu bez súvislostí. Učil som sa 5 týždňov pred termínom celé dni - dovolenka z práce, naviac čítanie v autobuse cestou do práce asi 3 mesiace pred termínom, cca dva týždne po odovzdaní diplomky tak na 50%. Na druhú stranu treba povedať, že som mal 5 rokov prerušené štúdium - rozhodoval som sa, či školu vôbec dokončím - a vyčísliteľnosť som videl prvýkrát až v príprave. Ak si toho veľa z prednášok nepamätáte, myslím, že týždeň na okruh stačí.

Skúšanie: Skúšobná komisia bola výborná - otázkami zisťovali, či tomu rozumiem, žiadne zbytočné detaily, alebo bazírovanie na jednej veci. Keď som nevedel niečo zadefinovať presne, bol som vyzvaný, nech to zadefinujem slovne a vysvetlím. Nástup bol o deviatej, ja som končil po jednej, čo bol typický čas. Skúša sa 1 vs 1, tj. nekomisionálne. Ak vás však idú vyhodiť, prizve si skúšajúci kolegu a typicky zopakujete otázku znova. Na termíne bol študent, ktorý vyletel na 3. termíne, takže sa istá úroveň znalostí požaduje. Moji skúšajúci sa skôr snažili, aby sme skúšku absolvovali úspešne. No nenechajte sa mýliť, tretinu učiva prečítať nestačí.

Rady: Pri príprave pomáha teamová spolupráca: prečítať si to individuálne a potom sa dať s niekým dohromady a prejsť si učivo znova. Stravili sme v labe 6 dní x 8 hodin a pomohlo to nehorázne. Jednak som zistil, čomu nerozumiem - pri vysvetľovaní druhým - kde mi chýbajú súvislosti. Kolega zase doplnil poznámky, príklady, ktoré si pamätal. Rozlúštili sme spolu rýchlo algoritmy atp. Dávali sme si úlohy, do dalšieho dňa jeden zistil to, druhý ono - potom sme vymenili info. Čím skôr začnete, tým lepšie - pred termínom stúpa nervozita. Množstvo látky je náročné na zapamätanie, nemyslím, že má cenu učiť sa niečo bez pochopenia. Ja by som to zabudol.

9. 2. 2010 (db)

Alg. nerozhodnutelné problémy

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

Mlýnková - Relačí algebra + kalkuly + SQL

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

Mlýnková - XQuery a XSLT

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

Kopecký - Vnitřní a vnější třidění (Datové struktury)

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

Richta - Distribuované transakce

Stačilo jen základy. Centralizovaný/decentralizovaný přístup. Dvoufázový potvrzovací protokol.

9.9.2009 (db)

Zdravím, tak bych tu chtěl napsat pro ty co to nemají ještě za sebou, jak je to letos u státnic. Vzhledem k tomu, že loni tu popsal situaci jediný člověk a to z databází, můžu porovnat, že se moc nezměnilo. Zkoušející jsou relativně mírní, přišlo mi, že se snaží do ničeho raději nevrtat, aby nevrtali špatně Nicméně to má za následek, že pokud nenapíšete všechno co víte (nebo si třeba jen myslíte), moc se vás dál na nic nikdo nevyptává, odkýve to a tím s Vámi obvykle končí - tedy piště všechno co Vás k tomu napadne, zdá se mi, že je to potřeba.

Jak to u státnic vypadá - na začátku se všichni sejdou a následně jsou přiděleni některým ze zkoušejících a rozesázeni po větší části Malá Strany Pak dostanete otázky (myslím, že je nějaké pravidlo, že by jeden zkoušející neměl dát víc jak dvě jednomu studentovi). No a pak píšete co víte, průběžně můžete jednotlivé otázky nechat zkontrolovat příslušnému zkoušejícímu (což je celkem dobré, nestane se nakonec, že zbytečně dlouho čekáte až opět od někud přijde). Mně trvalo napsání a zkontrolování 3 hodiny, ke každé otázce jsem napsal 1 až 2 A4. Většinou se pohyboval čas myslím ke 4 hodinám. Začátek byl v devět, vyhodnocení ve tři (den předtím myslím ve dvě). Výsledky byly v náš den vesměs pozitivní, asi z 20 lidí byly myslím jen 2-3 čtyřky, nejvíc bylo dvojek a jedničky a trojky tak půl na půl. Z doslechu to den předtím dopadlo o dost hůře (jak, to nevím).

Otázky: Přišlo mi, že nejsou rozděleny rovnoměrně mezi všechny, které se člověk učil, spíše jsou pokládány takové ty "normální" Moje otázky:

Relační algebra a její použití - popsal jsem základní operace, odvozené operace, relační úplnost, základ k tomu, jak se díky ní optimalizuje v SQL a Datalogu (ten jsem spíš jen zmínil).

Zotavení a žurnály - popsla jsem dva typy způsobů jak to provádět (visí to někde, snad na wiki), proč se to stane a co se musí zajistit. K tomu po mě chtěl zkoušející popsat v základu co je to transakce.

Binární vyhledávací stromy - popsal jsem co je to binární strom, co je to BVS, jak se tam dělají jednotlivé operace, proč se zavádějí vyvažované stromy, definice k AVL a R-B, jaký je tam rozdíl v hloubce, jak se dělají vyvažovací operace. Jen lechce si zkoušející šťournul do vyvažovacích operací R-B (že je při delete potřeba 2xčerný vrchol a ještě nějaké detaily, nic do hloubky). Pak se ptal ještě na Splay stromy, ale o tom jsem nic nevěděl, nechal to tedy být s tím, že se to dnes asi už neučí.

Huffmanovo kódování - stručně jsem popsal a nakreslil příklad k statické verzi, popsal jsem jak funguje dynamická, jak se mění strom atd.

Věty o rekurzi, Riceova věta - Napsal jsem základní větu, generování pevných bod a větu o rekurzi v závislosti na parametrech (vše samozřejmě s těmi jednoduchými důkazy). Napsal jsem Riceovu větu a její důkaz plynoucí ze základní věty o rekurzi. Ptal se mě odkud plynou důkazy, odpovědel jsem, že z Kleeneho věty a s.m.n. Pak se ještě ptal na trochu jinou verzi "Věty o programu co vypíše sám sebe", tam jsem trochu tápal, ale intuitivně jsem věděl (tu větu jsem znal, bohužel jsem ji neuvedl).

Učil jsem se 4 týdny v průměru 7 hodin a přišlo mi, že víc bych se stejně už nenaučil, takže myslím, že je to taková horní hranice. Co se určitě hodí na učení jsou skrypta na OZD (kódování, organizace souborů, hašování a další), slajdy dotazovací jazyky (Datalog, optimalizace a vyhodocení dotazů, signatury, RA, NRK, DRK) - také jsou k tomu skripta, ale ty jsem neměl. Slajdy Složitost, Koubkovy skripta, DIS slajdy, Skopalovy slajdy, výcucky na které je odkazováno na wiki a zde ve foru - oboje doporučuju, není tam všechno, ale občas je tam ujasnění, co vlastně v dané otázce je, popř. i věci, které jinde nejsou. Strojilova skripta a Lenčiny zápisky z vyčíslitelnosti. Mysím, že velká část všeho se dá najít i na matfyz wiki, doporučuju kombinovat více zdrojů, člověk to rychleji a hlavně správně pochopí. Některé části jsem tam také rozšířil a i ostatní se připojili, takže tam lze už vážně dost najít. Třeba především vyčíslitelnost jsem si díky tomu dost ujasnil.

Statnice - databaze:

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

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

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

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

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

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

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

Statnice - databaze 2:

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

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

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

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

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

Celkovo som mal zo ustnej casti za 2.

Statnice - databaze 3:

Moje priprava 5 tydnu (po 9ti letech na mff clovek nechce nechat nic nahode...).

Na otazky i zkousejici jsem mel asi hodne stesti:

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

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

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

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

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

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

Statnice - databaze 4:

1.) Amortizovana zlozitost (Fiala)

2.) Nerozhodnutelne problemy (Mlcek - Halting a Riceova s dokazom, ostatne len nazov)

3.) DRK (Riha -kde sa vyuziva prakticky - QBE, Oracle - dake formulare ci co)

4.) xPath (Pokorny)

5.) vektorovy a boolovsky model (Kopecky - princip, tvar dotazu a odpovede, implementacia)

Statnice - databaze 5:

Jako nejčastější tazatel tady na diskusi z tohohle státnicovýho termínu přihodim taky svoje dojmy ze státnic. Měl jsem stejnou komisi jako matys (viz předchozí příspěvek, tím čtvrtým zkoušejícím byl tuším prof. Loebl). Musím konstatovat, že hodnější komisi by člověk asi pohledal - trochu se vymykal jen doc. Skopal, ale myslím, že to bylo ku prospěchu věci a člověku to dodalo lepší pocit, že to neudělal jenom díky štěstí na komisi a otázky (viz moje otázky níže).

Ještě bych se chtěl u doc. Skopala chvilku zastavit, jak již zde bylo několikrát zmíněno, je často těžké pochopit co od vás chce slyšet a obvykle se nakonec jedná o triviality, ale i když jsem byl připraven na to, že chce slyšet jednoduché (základní) věci, nedokázal jsem je vysypat z rukávu - problém není v tom, že by to člověk nevymyslel, ale v tom, že to musíte vymyslet okamžitě - představoval jsem si státnice tak, že zkoušejícímu ukážu co jsem vymyslel, on řekne, co mám ještě doladit a dovymyslet a až to budu mít, tak si s nim o tom zase pokecám. Minimálně u doc. Skopala to tak není, vše co chce slyšet, chce slyšet hned - neověřuje pouze jestli tomu rozumíte, ale i jak jste sběhlí v uplatnění dané problematiky v praxi.

moje otázky:

povinné: dolní odhady pro uspořádání přehled hašování (řešení kolizí)

databáze: bezpečné výrazy indexace dokumentů komprese (obecně + komprese čísel)

Důležitý je se při učení zaměřit na pochopení k čemu která věc slouží a jak zrhuba je použitá v praxi - příklady přímo od zkoušky:

bezpečné výrazy - problémem u relačních kalkulů jsou nekonečné domény, takže je potřeba výrazy nějak omezit (aktuální doménou), kromě toho je dobré znát (resp. umět pohotově vymyslet) výrazy, na kterých jsou ty problémy relačních kalkulů vidět

indexace dokumentů - mám invertovaný soubor, index obsahuje jednotlivé termy, které pak mají seznam dokumentů, ve kterých se vyskytují - co ze mě doc. Skopal doloval bylo říct, že tyhle dokumenty jsou v tom seznamu setřízené, aby bylo urychlené vyhodnocování (problém byl v tom, že obrázek, kterej jsem k tomu nakreslil nebyl úplně jednoznačnej a každej jsme ho pochopili jinak, takže jsem za vůbec nechápal, co po mě chce, ale moh jsem si za to sám

Hezky na to pak navázal doktor Kopecký, kterému jsem ukázal kódování čísel, ale opět jsem neměl moc jasnou představu, kde je to využíváno - nicméně po lehkým naťuknutí jsem rovnou použil předchozí pohovor o indexaci dokumentů a správně řekl, že se to používá v tom invertovaném souboru pro kódování seznam těch dokumentů, kde se term vyskytuje. Pak jsem byl ještě poučen, že jak je ten seznam setřízen, tak se nekódují konkrétní čísla, ale přírustek od předchozího indexu.

Tohle jsou informace, které jsou vůbec tím nejužitečnějším, co si z těch státnic (a MFF) můžeme odnést, bohužel se mi zdá, že jsou to věci, které jsou krásné ve své jednoduchosti a jsou snadno pochopitelné a tedy jim přirozeně na přednáškách a zkouškách není třeba věnovat tolik prostoru jako složitým důkazům, které v životě nikdy neuplatníme.

Na závěr bych chtěl poděkovat všem přispěvatelům této diskuse a všem, kteří propůjčili své výpisky pro blaho ostatních matfyzáků, který si to mnohdy ani nezasloužili (jako třeba já:)

Každopádně jako dík, tady je odkaz na poznámky ke státnicím http://marthin.wz.cz/statnice.zip - vycházel jsem z Majklových výcucků a trochu je rozpracoval - možná je někdo využijete, jestli jo, tak se nestyďte je doplnit a předat je dál.

Statnice - databaze 6:

S odstupom dna prispievam na mff.modry.cz aj ja svojimi otazkami.

Vseobecna

1.Aproximacne algoritmy (nepoznal som cloveka - Loebl?)

Pripravil som si 2 a4 s definiciami AA, pom. rel. chyba, AS, PAS, UPAS. Nakoniec som dal priklad vrch.pokrytie s dokazom ze pom.chyba je 2. Skusajuci to asi za 5s preletel ocami a spytal sa ci viem zlozitejsi algortimus, na co som odpovedal ze nie a on ze ok a koniec.

Odhad:2

2. AVL stromy (Koubkova)

Toto bolo velmi v poho. Napisal som zopar definicii, ukazal rotacie a zlozitosti operacii. Potom mi dala priklad ktory sme spolu spravili a koniec.

Odhad: 1-2

3.Izolacie transakcii (Skopal)

Ak uz je spominane nizsie, p.Skopal skusa velmi zahadnym sposobom ked polozi otazku a vy netusite co chce pocut. Po 15 minutach ked uz ste spotili aj kravatu zisite ze sa pyta na uplnu trivialitu, ktoru ovladate ale bohuzial za tych 15 minut ste nezistili ze sa pyta prave na to. Toto bolo najtazsia cast mozno aj preto ze pri uceni som to preskakoval s tym ze je to lahke a potom som sa tazko z hlavy vymyslal definicie.

Odhad: 3

4. Relacne kalkuly (Skopal)

Toto uz islo lepsie. Chcel odo mna pocut ako by som naivne implmementoval relacny kalkul v nej, programovacom jazyku - odpoved: dosadzujem prvky z domeny a skusam kedy bude podmienka true. Este chcel rozirenie kalkulu o agreg. operacie - ako by som implemetoval trebars AVG - odpoved: mam predikat AVGZAM(x) a hadam priemerny plat a ten predikat mi niekedy povie true.

Odhad: 2

5. Vekt. a boolsky model (Kopecky)

Zrejme oblubena otazka pana Kopeckeho. Uz som bol unaveny ale dal som boolsky model vcelku obstojne a pri vektorovom iba zaklad. Pan Kopecky ale skusa prijemnym sposobom a ak ste to nikedy vedeli tak to z vas dostane seriou lahkych otazok. Nepotrpi si na formalizmoch - staci mu to porozpravat po lopate a vediet princip :)

Odhad: 2

Celkovo: 2

Take veci, ze je to fajn na to aby si clovek utriedil veci co sa naucil pre mna neplatili. Pocas studia som nerobil Vycisllitenost, Datovky a ani slozitost takze som sa ucil nove veci a bolo toho nekonecne vela. Mal som vo vsetkom strasny gulas, vsetko sa mi miesalo dokopy. Ucil som sa velmi dlho uz od decembra. Dolezite je povedat ku kazdej teme aspon par viet a tusit o com dana teme vobec je. To su moje postrehy. Drzim palce zvysku.

9. 2008

Pozadie: Na kamarátovo odporúčanie som si zapísal všetky 3 voliteľné otázky z plánu Databázové systémy. Výhodu to má tú, že sa veľa podotázok prekrýva. Až na zanedbateľne málo podotázok, je DB2 podmnožinou zjednotenia DB1 a DB3 a DB3 je podmnožinou zjednotenia DB2 a dátoviek. Inak povedané: dátovky + DB1 + DB2 + DB3 sú dokopy asi tak ťažké, ako 2,5 otázok.

Príprava: Učil som sa asi 5 týždňov, od odovzdania diplomky, v priemere 3 hodiny denne. Vzhľadom k záverečnej známke 2 to s rezervou stačilo. Na koleji som mal známeho, ktorý teoretickú časť vedel pomerne dobre a dosť nám so všetkým pomáhal. Učil som sa z wiki, 3 skrípt od Pokorného (neodporúčam, sú zbytočne podrobné) a nie-mnou-upravených Majklových poznámok, ktoré som našiel niekde na modrom (v jednom z príspevkov). Najlepšie sa mi učilo z Majklových poznámok. Upozorňujem, že som v NMgr prváku absolvoval povinné predmety vyčísliteľnosť 1, zložitosť 1 a dátovky 1. Ak ich niekto nerobil, tak sa bude musieť učiť možno trochu viac.

Priebeh: Každú otázku zadával iný profesor. U nás to bola podľa mňa pohodová päťka: Pokorný (šéf), Koubková, Galamboš, Richta a Mlček. Ešte sa tam potuloval Majerech a Kopecký, ale tí sa mi vyhli. Môj postup bol taký, že som začal vypracovávať a odpovedať na otázky od najťažšej po najľahšiu. Každá otázka zabrala v priemere 1,5 strany. Stačilo by aj menej písania, pretože som nakoniec povedal všetko aj ústne. Známku mi zatiaľ nikto nepovedal, povedali vždy len "OK, to mi stačí". Hotový som bol asi po 2,5 hodinách.

Otázky:

Pokorný: Vektorový model - chápal som to len intuitívne (vôbec som nevedel žiadne vzorce ITF a podobne), čo mu trochu vadilo, nakoniec to pochopil a netrápil ma

Koubková: Triedenie vo vonkajšej pamäti - no comment

Galamboš: Huffmanovo kódovanie - toto som vedel, takže sa v tom moc nevŕtal

Mlček: Vety o rekurzii - pre mňa najťažšia otázka, našťastie som si fotograficky zapamätal dôkaz Riceovej vety a niektoré vety o rekurzii, takže ma nevyhodil

Richta: SQL + vyhodnocovanie a optimalizácia dotazov - Richta bol super, dokonca mu nevadilo, že som zabudol popísať optimalizáciu, stačilo len 3 vetami vysvetliť, o čo ide

Vyhodnotenie: Najdôležitejší moment štátnic. Dovtedy totiž nikto z nás netušil, ako sú profesori nároční. Pán Mlček ma mohol za tie vety o rekurzii vyhodiť, ale nemusel. Nakoniec sa ukázalo, že náročnosť nebola príliš veľká, pretože sme mali všetci (z koleje) dvojky. U nás (databáz) dokonca nikoho nevyhodili a trojka bola len jedna. Stretol som 1 chlapíka, ktorého vyhodili, lebo si nevedel spomenúť na znenie Godelovej vety.

Veľa šťastia ďalším generáciám...

Ostatní

18.9.2017

Analýza, návrh a management SW systémů: Životní cyklus SW systémů (Nečaský) - popsal jsem co je vlastně sw systém (softwarové i ne-sw položky, a jaké jsou..) a pak jednotlivé fáze. Nakonec se ptal jestli je lepší některé fáze nějak cyklit (aka spirála nebo nějaké agilní metodiky) nebo ne (waterfall). Řekl jsem že cyklit a povídal o agilních metodikách (scrum, kanban). Waterfall se může prý hodit líp na obrovské projekty které se skládají z menších (od subdodavatelů), kde by byl overhead na integraci jednotlivých částí zbytečně vysoký.

Složitost a vyčíslitelnost: ČRF (Hladík) - na začátku jsem uvedl, že ČRF nás zajímaj proto, že je to výpočetní model ekvivalentní TS. Hned následovala otázka, proč potřebujeme ČRF, když máme jako model TS. Řekl jsem, že ČRF přináší jiný přístup, takový "algebraičtější" aparát, můžeme je snadno skládat atp.. např důkaz věty o rekurzi diagonalizací si neumím představit přes TS... no, nějak mu tahle odpověď stačila. Pak jsem zadefinoval PRF a ČRF (měl jsem drobnou chybu v definici minimalizace, ale měl jsem tam tu ukázku ekvivalentního while cyklu, to stačilo). Řek jsem, že jdou ČRF očíslovat a že existuje i univerzální funkce. Pak se ptal na definiční obory a obory hodnot ORF/ČRF, jestli to jsou rekurzvní nebo RS možiny. Myslim že je dobrý mít tohle dobře nastudováno, asi by u tohoto tématu u státnic moc neodpustili...

Vývoj SW systémů: Vývojové prostředí (Zavoral) - tady si zkoušející vzpomněl, že jsem psal "nějakou zajímavou diplmku u kolegy", takže mi otázku upřesnil na "specifika vývojového prostředí pro paralelní jazyky." Nejdřív jsem zajásal, ale při přípravě jsem zjistil, že o tom vlastně nic moc nevím. Nakonec jsem to tak nějak zkušeně okecal :)

Datové struktury: Třídění ve vnitřní a vnější paměti (P. Kučera) Řekl jsem něco obecně k třídění (dělení dle stable, in-place... a pak že záleží na tom, jestli předpokládáme porovnávací model, protože na čísla se dá použít třeba radix sort...) Uvedl jsem "naivní algoritmy", zeptal se proč je třeba dobrej bubble sort (O(n) best-case na setříděnou posloupnost...), pak merge-sort s analýzou přes master theorem. Víc se začal ptát u quick sortu - řekl jsem že pivot jde brát různě (náhodný, medián ze tří, atd...) a dost se ptal na rozdíly těchto přístupů, worst, best a average. Nevěděl jsem uplně všechno, ale spíš zkoumal, jak moc tomu rozumím do hloubky. U třídění ve vnější paměti se víc zajímal o případ, kdy máme tolik běhů, že je pak nemůžeme slít všechy najednou. Pak ho taky zajímalo, jaký je nejmenší počet souborů potřebných k setřídění jakkoli velkého vstupu (prý 4). Nakonec byl spokojený a já jsem se i něco naučil.

Formální základy DB technologií: Datalog, 3. sémantiky... (Pokorný) Styl zkoušení prof. Pokorného jsem znal ze zkoušek, docela si potrpí na přesných definicích. Měl jsem docela podrobně rozepsáno co je to datalog (IDB, EDB, IO), k čemu to je, co to umí (rekurze, tranzitivní uzávěr) a co to neumí (bez negace to neumí rozdíl...). Pak na mě trochu uhodil a chtěl abych přesně řekl co jsou to ty Hornovy klauzule, termy, formule, atomické formule... Ale nakonec byl spokojený. Na 3 sémantiky a jejich ekvivalence asi nevyšel čas, což mi vůbec nevadilo.

Ráno nás rozsadili do lavic v S4 a hned nás všichni zkoušející obešli a zadali nám otázky. Myslim že jsem měl docela štěstí jak na zkoušející, tak na otázky, takže jsem si pak už docela věřil. Nakonec celkově za jedna, jednotlivé známky neznám. Učil jsem se na to cca měsíc (posledních 14 dní hodně intenzivně) a rozhodně jsem neměl pocit, že jsem to uměl všechno na výbornou... Určitě jsem při učení ocenil osnovu (díky jejím autorům!).

16.6. 2015

Distribuované systémy: RPC a objekty v distribuovaném prostředí (popsány obecné principy, příklady konkrétních technologií (CORBA, RMI, web services), pak jsme distutovali různé technické detaily).

Operační systémy: Virtuální paměť (v podstatě otázka z okruhů Správa paměti, stránkování, ..., IMO jednoduchá otázka, žádné záludnosti se nekonaly).

Objektové a komponentové systémy: Dědičnost a subtyping (popsán význam, implementační detaily a trochu jsem se zamotal do kovariancí, se vstupem zkoušejícího jsme se dobrali konsenzu).

Složitost a vyčíslitelnost: Algoritmicky nerozhodnutelné problémy (definice, co to je, pak konkrétně halting problém a důkaz jeho nerozhodnutelnosti, diskuze o dalších nerozhodnutelných problémech).

Datové struktury: Třídění ve vnější a vnitřní paměti (rozebrány metody třízení ve vnější paměti, pak ve vnitřní pomocí porovnávání a nakonec zmínka o třízení typu bucketsort).

S lehkou přípravou jsem začal asi měsíc před zkouškami, intenzivně jsem se učil poslední dva týdny. Pokud člověk na něčem nezaškobrtne (k čemuž přispívá ta příprava, ale i štěstí na otázky), tak jde zkouška jako po másle. (Před státnicemi jsem si ve slabších chvílích z některých zdejších zápisků myslel, že zkoušku snad ani není možné složit napoprvé. To je samozřejmě omyl.)

18. 9. 2014

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

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

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

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

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

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

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

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

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

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

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

2. 6. 2014

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

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

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

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

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

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

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

Datové struktury (Hladík): Fibonacciho haldy

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

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

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

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

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

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

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

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

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

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

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

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

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

Složitost a vyčíslitelnost (mladý Kučera): RM, RSM a jejich vlastnosti – Napsal jsem:

• definice RM, RSM vč. definice ORF a ČRF (s drobnou chybou – dal jsem dohromady prvky a operátory nad funkcemi),
• generování (tři věty o oborech hodnot) (Tady se mě ptal, jak fungují ty programy pomocí kterých množiny generuji. Neměl jsem to rozmyšlené, takže to ze mě musel tahat a část říct),
• 1-převoditelnost, 1-úplnost, K je 1-úplná. Ptal se mě, k čemu ta 1-převoditelnost je. Dával mi návodné otázky a potom jsem si končeně vzpomněl, že asi myslí to, že můžu převést jednu množinu na druhou. Jen tak mimochodem se ptal, kolik je RM a kolik RSM.

Všechno jsem psal bez důkazu a nechyběly mu. Nakonec mi řekl, že to mám tak za 1− a jestli chci čistou 1, tak ať mu formálně dokážu, že K je 1-úplná. Řekl jsem mu, že o 1 mi až tak nejde.

DS (Koubek): Vyvážené binární vyhledávací stromy – Napsal jsem:

• co je BVS (měl jsem tam chybu v podmínce),
• co je vyvážený strom a ústně jsem na jeho dotaz doplnil, že jeho hloubka je $ O(\log n) $,
• definici AVL a Č-Č (u Č-Č jsem měl i nějaký odhad hloubky, ale Koubek vypadal, že si ho ani nevšiml),
• základní algoritmy – jen slovně a občas jsem tam měl drobnou chybku (např. jsem předpokládal, že vrchol má při odstraňování jednoho syna, ale on to mohl být i list),
• na příkladu AVL jsem se snažil popsat vyvažování. Neměl jsem to připravené, ale Koubek ty operace stejně přesně nechtěl. Spíš chtěl, abych mu řekl, že při vyvažování se nejen upravuje strom, ale také mění ta hodnota o vyvážení uložená ve vrcholech.

Celkově mě překvapilo, že byl Koubek docela hodný (čekal jsem to horší podle předchozích zápisů). Když odcházel vypadal spokojeně. Koubek občas chytne za slovo, když člověk řekne něco co není pravda. Je třeba se nenechat zaskočit (což je samozřejmě těžké) a popřemýšlet nad tím, co se mu nelíbí.

Analýza a návrh SW (Mlýnková, nyní Holubová): ER-schémata – Napsal jsem:

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

Řekla, že je spokojená a odešla.

Objektové a komponentové systémy (Bureš): Garbage collection (původně zadával Kofroň, ale potom si otázky prohodili) – Napsal jsem:

• Co to je a k čemu to je.
• výhody, nevýhody,
• základní algoritmy a jejich vlastnosti
  • počítání referenci
  • zjišťování dostupnosti

U toho zjišťování dostupnosti chtěl ještě nějaké dělení, ale to jsem vůbec nevěděl, protože jsem ani nevěděl, ve kterém předmětu se to učí a studoval jsem to z internetu. Celkově za 3.

Modely a verifikace programů (Kofroň): LTL, CTL, jak se pomocí nich verifikuje, model-checking obecně – Napsal jsem:

• Co je to model-checking.
• Trochu jsem popsal Kripkeho strukturu.
• Popsal jsem, jak vypadají CTL.

Pak přišel Kofroň, že už začneme (byl jsem v místnosti už poslední). Říkal, že je to OK a ptal se na to, jak probíhá model-checking pomocí CTL, tak jsem mu to řekl ± správně. Potom se zeptal, jak se tedy kontroluje LTL. To mě zaskočilo a vůbec jsem nevěděl. Tak mi to řekl a řekl že to mám za 2.

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

28.1. 2013

Loebl (SV) -- Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce.

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

Hladík (DS) -- Fibonacciho haldy.

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

Bulej (OOKS) -- Dědičnost, subtyping, variance signatur.

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

Bednárek (ANSS) -- XML, XML Schema.

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

Hnětynka (DS) -- RPC - obecně + nějaká imlementace.

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

11.9. 2012

Mlynkova (ANSS) -- E-R modely a prevod na relacni modely

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

Yaghob (MSS) -- Paralelni programovani a lockless algoritmy

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

Kucera P. (SV) -- Pseudopolynamialni algoritmy a silna NP uplnost

Definice obojiho, jedna veticka o tom, ze silne NP-uplne nemaji pseudopol. alg., strucne napsany pseudopol. problem pro batoh, veta o tom, ze pokud bychom nasli pro silne NP-uplny problem pseudopolynamialni alg., muselo by platit, ze P=NP. Nic dalsiho nebylo potreba vedet.

Majerech (DS) -- Reseni kolizi v hashovani a univerzalni hashovani

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

Obdrzalek (OOKS) -- Diamond problem

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

Koubkova(DS) -- Haldy

Regularni haldy -- co jsou, k cemu jsou, Min/Max heap, Insert, ExtractMin, Delete, pouziti, implementace v poli, Binomiální haldy, Fibbonaciho haldy, nasledne diskuse

A.Kucera - tusim (SV) -- Nerozhodnutelné problémy

Halting problem - jak se dokazuje, Postuv problem, rozhodnuti zdali dana funkce vycisluje dany program

Wilkie + Skopal + kdosi (Analýza a zpracování obrazu, počítačové vidění a robotika) -- Detekce hranic objektu

Segmentace - Thresholding, deformovatelne modely, watershed, grafove algoritmy, shlukova analyza, Detekce hran - 1.,2. derivace - filtry ktere se pouzivaji, jak se pouzivaji, DoG, vysoke frekvence...

Wilkie + Skopal + kdosi (2D počítačová grafika, komprese obrazu a videa) -- Rozptylovani a pultonvani

vicemene to co je v Pelikanovych slidech - Rozptylovani - iterativni, pravidelne, priklady matic, souvisle, otaceni slozek; Pultonovani - Maticove, Nahodne, Distribuce chyby, Floyd-Steinberg

Wilkie + Skopal + kdosi (Realistická syntéza obrazu, virtuální realita) -- Prime metody pri visualizaci objemovych dat

Pelikanovy slidy - co jsou objemova data, hodnoty/souradnice, 3D-DDA, Raycasting, Splatting, vice ve slidech (vic nemam v zapiskach, ale vedla se diskuse o spouste veci)

11.9.2012

Pozdě, ale přece přidám "svůj příběh".

1. Operační systémy - Hnětynka - Architektura OS, mikrojádro. Popsal jsem jednotlivé komponenty OS pro monolitický OS a pro mikrojádro. Měl jsem pospat, co všechno se vyskytuje v mikrojádru a jaké jsou rozdíly mezi mikrojádrem a monolitickým. Pár slov na závěr o hybridním jádru. Řekl jsem zhruba to, co k té otázce má s0cketka

2. Programovací jazyky a překladače - Bednárek - LR automaty Jedna z nejsložitějších otázek z celých překladačů. Když jsem na tu otázku narazil při učení (minulý týden ve středu), tak jsem si myslel, že se to snad (překladače) nestihnu naučit. Naštěstí je "peklo" jen tahle otázka. Otázku jsem uměl do té míry, že jsem přesně chápal, jak to funguje, jak pracuje LR AUTOMAT, FIRST, FOLLOW, Rozšířená gramatika, Uzávěr, GOTO, kanonická kolekce. Co se týče toho, jak se ta tabulka action/goto konstruuje, tak to jsem detaily neznal, jen zhruba... ale to nijak moc nevadilo. Pak byla otázka na "druhy" LR (LR(0), SLR, LALR, LR), ale tam stačil výčet. Plus drobnosti, jakým způsobem se změní ty operátory při přidání výhledu.

3. Datové struktury - Čepek - Univerzální hašování Definice (c)-univerzálního systému, potom jsem ukázal konstrukci 1-univerzálního podle MIT (na který jsem se koukal den předtím). Za deset minut bylo hotovo

4. Architektura počítačů a sítí - Peterka - Topologie sítí, přístupové metody K topologii jsem nakreslil těch několik základních ze s0cketky a více jsme se tím nezaobírali. U přístupových metod jsem pospal deterministické/nedeterministické, centralizované/distribuované. Měl jsem si připravit jednu konkrétní přístupovou metodu (vybral jsem si Ethernet), sepsal jsem jich několik, ale Ethernet do většího detailu (CSMA/CD, 1-persistentnost, nedeterminismus, kolizní doména, "ethernet bez CSMA/CD - 100Vg ANY LAN). Bavili jsme se ještě o Token ringu, kabelových sítích a některých detailech. Pospala jsem rozpad linkové na MAC a LCC, doplňující otázka byla, kde přesně leží MAC a proč (hned nad fyzickou, LCC je nad ní). Povídali jsme si i o některých detailech, které jsem nevěděl, ale vůbec to nevadilo. Tady musím "varovat" před tím, že v s0cketce chybí relativně dost věcí, které se týkají sítí. Pro doplnění jsou jasnou volbou Peterkovi slidy

5. Složitost a vyčíslitelnost - Dvořák - Hladové algoritmy Popsal jsem intuitivně o co jde (oiptimalizační hladové algoritmy), popsal jsem, jak to funguje a popsal jsem Krustalův hladový algoritmus. Bavili jsme se o jeho složitosti (kde jsem neznal způsob, jak to je "ideální"), potom o jeho korektnosti (to jsem taky detaily neznal - nikdy jsem to úplně 100% nepochopil a když jsem se na to koukal do Kapitol z diskrétní matematiky před šesti týdny znova, tak jsem to také úplně nepochopil). Nicméně mi se mě pan Dvořák snažil trochu popostrčit, ale kde nic není, ani smrt nebere. Ukončili jsme to s tím, že to hlavní jsem věděl a že to není fatální.

Dohromady jsem dostal za 1. Takže spokojenost.

Na závěr ještě pár poznatků ke státnicím pro budoucí generace. Důležité je umět definice, neznalost nějaké definice je smrtící (někdo neuměl definici silné NP-úplnosti a byl vyhozen). Většina zkoušejících má tendenci spíše pomáhat a směrovat tok myšlenek správným směrem. Důležité je mít přehled, protože dost věcí se opakuje v různých otázkách, takže si tím člověk může i dost pomoct. Určitě to je mírnější, než na zkouškách z daných předmětů, ale člověk zkrátka musí vědět, o čem je řeč... Dobré zdroje na učení pospal kolega nade mnou, tak se nebudu opakovat. Ta přednáška na univerzální hašování z MIT ušetří několik hodin času. Na zkoušku z datovek ušetří klidně několik dní času :)

Tak hodně zdaru!

11.9.2012

Přidám průběh státnic ze softwarových systémů, byl to můj celkově druhý pokus.

1) Architektura počítačů a sítí - Peterka - Von Neumannova architektura a její alternativy, multiprocesory. Trochu mě tahle otázka překvapila, nepatří zrovna mezi ty "praktické". Popsal jsem tedy Von Neumannovu architekturu, harvardskou (+ srovnání), jak funguje pipeline a co to je out of order execution - více mě k tématu nenapadlo. Peterka přišel a zeptal se, jaké národnosti byl Von Neumann (Maďar), pročetl co tam mám, začal ze mě tahat další architektury. Po chvíli mi napsal na papír SISD, SIMD, MISD, MIMD, já mu k tomu něco řekl a pak spokojeně odešel.

2) Složitost a vyčíslitelnost - Čepek (příseděl Koubek a Dvořák) - Úplné problémy pro třídu NP, Cook-Levinova věta. Člověk by řekl, že jednoduchá otázka, ale kurevsky mi zatopila, neb jsem nebyl schopen dát do kupy přesnou definici NP a převoditelnosti pomocí TS (a Čepek 5 minut před tím jednoho kolegu vyhodil, neb neznal definici). Naštěstí mě několikrát nakopli a tak jsme nakonec došli k tomu, co to teda je NP-úplný problém. C-L větu + důkaz převodem na kachlíkování jsem uměl, což Čepka evidetně potěšilo, takže nakonec v pohodě.

3) Datové struktury - Koubek (příseděl Dvořák) - Trie Taktéž lehce neočekáváné, naštěstí ne příliš těžké. Koubek ke me přiběhl lehce před oficiálním termínem, takže jsem ještě neměl hotový papír o komprimaci trie. Odříkal jsem mu základní definice, vlastnosti, ukázal vše na nakreslesném příkladu. Koubek, dobře si vědom mé schopnosti přesně definovat cokoliv, nelpěl příliš na detailech. Chtěl doplnit delete a pak jsme se vrhli na komprimaci, která trochu vázla, neb jsem ji neměl připravenou, ale nakonec jsme se dobrali výsledku. Dvořák přišel se záludným dotazem, co by se změnilo, kdyby to nebyl prefixový, ale sufixový strom. Otevřeně jsem přiznal, že nemám tušení a oba pak se slovy, že to nebylo v otázce, odkáčeli směr tabule.

4) Operační systémy - Hnětynka - Synchronizace Asi jedna z nejpohodovějších otázek. Popsal jsem kritickou sekci, kde jsem opět měl blbě definici (může v ní být n procesů, ne jen jeden :) ) a pak všechna primitiva, co mě napadla - maskování interuptů, Petersonovo řešení, semafory (detailněji vč. implementace pomocí instrukcí TSL a XCHG), mutex, monitor a condition variables, k bariérámn jsem se nedostal. Hnětynka byl tuze spokojen, jen pak chtěl vědět, jak bych implemtoval mutex pomocí semaforu, což jsem asi po 5 minutách vymyslel (nápověda - jsou potřeba 2 semafory :) ).

5) Vestavěné systémy a systémy reálného času - Kofroň (příseděl Hnětynka) - Plánování v RT systémech - Rate monotonic, Deadlline monotonic, EDF Na přípravu jsem měl asi 2 hodiny času, neb Kofroň dusil nejdříve kolegu nade mnou a následně vedle mě. Popsal jsem, co je RT systém, čím se liší od normálního systému, RM + DM, EDF (vč. podmínek, kdy je množina úloh plánovatelná a response time analysis), srovnání RM a EDF a pak jsem nakonec ještě zmínil nějaké aperiodické plánování. Mluvil jsem celou dobu skoro sám, na konci Kofroň prohlásil, že k tomu není co dodat a šel na oběd.

Nakonec za 1, dílčí známky mi nikdo nesdělil. V místnosti nás bylo 8, 2 vyhodili.

Pár postřehů pro příští generace:

   Definice- alfa a omega, většina zkoušejích na nich těžce lpí. Je vám na hovno, pokud umíte dokázat větu o 4 barvách, pokud neumíte definovat graf. Typicky se od nich začíná a pokud problém PŘESNĚ nedefinujete, nedostanete se k ničemu dalšímů, odejdete s nepořízenou a nikoho nebude zajímat, že zbytek otázky umíte. Osobní zkušenost (minule definice sekvenčního protokolu pro distribuovanou komunikaci a dneska málem NP-úplnost) + dneska kolega dopadle stejně (něco s pseudopolynomiálními algoritmy) a pár dalších z nás mělo namále.
   Důkazy - většinou stačí hlavní myšlenka, krom těch zásadních a snadných (Halting problém apod.).
   Dobré zdroje na učení:
       wiki.matfyz.cz - jako přehled, chybí detaily a dost neudržované
       S0cketčiny zápisky (viewtopic.php?f=419&t=6620 - aktuální umístění se občas mění) - jsou obří, ale je tam skoro všechno ze Systémových architektur, hezky popsáno
       Poznámky od Vládi Bedecsa - (viewtopic.php?f=419&t=6667) - spíše pro softwarové inženýrství (obsahuje Architekturu počítačů a síti), pěkne sesumírované
       Kučerovy poznámky (http://ktiml.mff.cuni.cz/~kucerap/NTIN0 ... znamky.pdf) - bible složistosti a vyčíslitelnosti, občas možná moc ukecané, ale jinak super
       Proslulé Peterkovo kino (http://www.earchiv.cz/i_prednasky.php3) - je tam skoro všechno o sítích, super jako přehled, občas to chce dohledat detaily jinde (IPSec, IPv6, certifikáty,...)
       Přednáška na MIT o univerzálním a perfektním hašování (http://videolectures.net/mit6046jf05_leiserson_lec08/) - odkaz šlohnut z wiki, super na pochopení, ale dost jiné, než co přednáší Koubek. Na druhou stranu, těch přednášek tam je hromada i na jiná témata, stačí hledat.
       A.S.Tanenebaum - Modern Operating Systems, 3rd edition (http://www.amazon.com/Modern-Operating- ... 0136006639) - na Amazonu za lidových $116, v knihovně gratis (nevím které vydání)...no, a kdo hledá, ten najde. Naprosto zásádní dílo, co se OSů týče. Extrémně ukecané, ale i extrémně čtivé. Nevynechá snad žádné téma v OSech (vč. obskurností jako virtuální stroje) a pokrývá i nemalou část z Architektur počítačů a síti. Více jak 1000 stran není málo, ale pro potřeby státnic se dá zredukovat cca na polovinu. Pan Vánoční Stromeček prostě umí psát... :) 

Hodně štěstí všem ostatním :)

11.9.2012

Dnes jsem absolvoval statnice z pocitacove grafiky: Otazky: 1)Binarne vyvazene stromy: Rekl jsem definici AVL, RB, BB(alpha), dukaz hloubky AVL a nakonec par operaci nad AVL stromy. AVL jsem si vybral dobrovolne, mohl jsem rikat vic i o RB. Bohuzel nevim zkousejici :( Byla to nejaka postarsi hodna pani :) Na nic moc se neptala a byla spokejena

2)NP-Uplne problemy Definoval jsem jazyk, problem, NP, prevody, NP-uplnost a strucne predvedl dukaz cook levina. Zkousejiciho opet neznam, ptal se jen na to jake dalsi NP-uplne problemy, jinak byl spokojen.

A ted grafika, tam me prekvapili zkousejici: Wilkie, Skopal (!!!! ten co uci normalne databaze) 3)Monte-Carlo methods Zkousel me Wilkie, takze to probihalo v anglictine :) Byl celkem v pohode, jen me zarazili nektere otazky na quasi monte-carlo.

4)De Casteljaův a de Boorův algoritmus To hlavne zajimalo Skopala, ale povidal jsem v anglictine, aby tomu rozumel i Wilkie. Skopal byl uplne v pohode, v zadnych detailech se nerypal.

5)Standardy MPEG a JPEG Opet stejne jako u predchozi otazky me zkousel Skopal, v podstate jsem mu to odvypravel a on spokojene souhlasil :D

Tot vse, celkove 1 :) Preji vsem hodne stesti! (Btw udelali to vsichni 4 z grafiky)

6.2.2012

Na počítačovou grafiku jsme byli jen tři studenti a naše komise byla: Josef Pelikán, Jiří Žára a Tomáš Dvořák. První dva zkoušeli ty odborný předměty, T.Dvořák zkoušel datovky a základy složitosti a vyčíslitelnosti. Na začátku nám rozdali všech pět témat, dali nám 45 minut na přípravu a pak se u nás střídali a zkoušeli.

Datovky a složitost Dostal jsem 1) dynamické programování a 2) univerzální hashování. Mí dva kolegové dostali myslim NP úplnost, B-stromy, Fibonacciho haldy a asi něco s ČRF.

Ke každýmu tématu jsem si připravil cca stránku informací, když mě pak T. Dvořák zkoušel, tak seděl u mě, procházeli jsme to a šťoural se v tom.

1) U dynamickýho programování jsem nějak sesmolil princip fungování a napsal jsem tam jeden konkrétní algoritmus (z grafiky - matchování vrcholů dvou mnohoúhelníků), na kterym jsem ukazoval, jak to funguje. To bylo OK, ale tahal ze mě pořád nějakej obecnej princip, jak to funguje. V rámci toho jsem ještě za pochodu vymýšlel algoritmus na batoh (to se mi vůbec nedělalo dobře, když vedle mě seděl a čekal na výsledek). Na konec jsme se teda asi dobrali toho, co chtěl slyšet - že se řešení konstruuje z menších podúloh stylem zdola nahoru (narozdíl od rozděl&panuj, kde to je v zásadě shora dolů).

2) K tomu univ. hashování jsem napsal definici, definici c-univerzálního systému, konstrukci systému s důkazem c-univerzality (podle skript Koubka) a bez důkazu složitost operací. Tohle se mu sice líbilo, ale pak začal víc rozebírat tu složitost počtu operací a tam jsem už nic moc kloudnýho do kupy nedal. Nechtěl to dokázat, ale nějak interpretovat, a to se mi nedařilo. Zasekl jsem se u definice očekávané délky řetězce a snažil jsem se tu diskuzi stočit jinam, protože tady o tom jsem věděl kulový. :) Nakonec jsme to nechali být a ještě mě taky dostal otázkou, kdy se vybírá ten náhodnej index hashovací funkce. Já jsem si myslel, že se vybírá pro každý prvek nová, ale není to tak, protože bych pak nevěděl, kterou funkci jsem pro každej prvek použil. Prý se teda volí index jednou předtím, než přijdou data a pokud se ukáže, že vybraná funkce není dobrá, tak se potom může vybrat nová a tabulka celá přehashovat.

Grafika Dostal jsem 3) Dekonvoluce - inverzní a Wienerův filtr, 4) Rozptylování, palety, 5) Radiozita.

3) Napsal jsem to podle materiálů k DZO s Flusserem, definice problému dekonvoluce, jak to vypadá ve Fourierovském spektru, ty filtry a pak taky formulace problému ve variačním počtu pomocí minimalizace funkcionálu. Byli spokojený, tady myslím neměli ani žádný otázky.

4) Popsal jsem náhodný rozptylování, pak pomocí půltónovacích matic a metody distribuce chyby. To bylo OK. Pak přišly palety, tak jsem řekl proč se vůbec používají, že jsou nějaký pevný (5-6-5, 3-3-2 apod.) a pak jsem se vrhnul na konstrukci palety pro daný obrázek. To jsem tak nějak nastínil, jak na to, ale Žára se tady v tom začal hrabat do detailu. Jak přesně fungujou ty algoritmy, s jakou složitostí apod. No, nakonec jsem to po mírném postrkování nějak dal dokupy, akorát mě teda dostal na otázce: Který z těch půltónovacích algoritmů lze použít pro barevný obrázek s paletou? Tipnul jsem ty matice, ale je to distribuce chyby.

5) Vyšel jsem od zobrazovací rovnice a odvodil jsem z ní tu soustavu rovnic pro radiozity plošek. Pak pár vět o tom, jak se dá řešit (je diagonálně dominantní -> lze iteračně, takže Jacobi, SOR apod.). Taky jsem řekl, které odrazy to simuluje a že to není úplný řešení ZR. Ptali se, jak ty spočítaný výsledky nakonec zobrazím. Tak jsem říkal buď ray-tracingem nebo rasterizací těch plošek. Ray-tracingem jsem je malinko zaskočil, ale operativně jsem dovysvětlil, že tím tu radiozitu vylepším, že zvládne i lesklé odrazy před difůzníma, takže OK. Pak se ptali na stínování těch plošek, jak se to vlastně dělá - ze soustavy vypadnou radiozity ploch, z těch musím spočítat hodnoty na vrcholech (nějak zprůměrovat okolní plošky) a z těch se pak počítají ty výsledný hodnoty interpolací na povrchu plošek. Poslední dotaz mířil na progresivní radiozitu, ale o té jsem moc nevěděl (hlavní, co chtěli slyšet, a neslyšeli :) , bylo, že jedna iterace odpovídá jednomu odrazu světla a počtem iterací snadno omezit délku výpočtu a je to hodně rychlé).

Celkově to bylo docela v pohodě, T.Dvořák je hodný, sem tam pomůže, rozhodně se nesnaží trápit nebo se v něčem extrémně šťourat. J. Pelikán je taky v pohodě, moc se na nic neptá. J.Žára se ptá celkem dost, chvilkama mi přišel nepříjemný, ale rozhodně pořád v mezích korektnosti.

6.2.2012

Ja sem dostal nasledujici otazky 1) Algoritmicky nerozhodnutelne problemy Zacal sem Church-Turingovou tezi a pojem algoritmus vztahl k TS. Pak sem zadefinoval Rekurzivne spocetne a rekurzivni jazyky. Halting problem, Diagonalni jazyk, Univerzalni jazyk, Postova veta. Pak sem presel od TS k CRF tady sem jako priklad uvedl K a K0, definoval CRF a ORF + intuitivni srovnani s TS U vetsiny veci sem mel i dukazy ( vycislitelnosti sem se bal nejvic z okruhu takze sem to mel celkem nadrceny ). Pak se dvorak ptal jak zjistim ze nejakekj problem je nerozhodnutelny ( aniz by clovek musel furt vymyslet specialni dukazy ) to sem chvili vahal ale pak sem si vzpomel na prevoditelnost Rekurzivnich a rekurzivne spocetnych mnozin pomoci prevodni fce ktera musi byt ORF coz se ukazalo jako spravna odpoved. Posledni sada otazek uz smerovala k tomu co se bude dit kdyz budu mit TS s orakulem, jestli potom budou vsechny problemy budou rozhodnutelne...tady sem nevedel, odpovidal sem hodne diplomaticky ( spravna odpoved je TS s 1 orakulem umi resit nejaky problemy, TS s 2 orakulama umi resit jeste vic problemu atd...ale nikdy nelze pokryt vsechny jazyky ) Jeste dodam ze tohle nakonec Dvorak okomentoval slovy ze je to spis takova zajimavost, nic zasadniho pro statnice.

2) B-stromy Napsal sem definici, dukaz logaritmicke vysky ( hrde sem to nazval Veta o logaritmicke vysce Bstromy coz dvorak s usmevem okomentoval ze je to spis takove trivialni pozorovanicko :D ) Pak sem popsal insert a delete. Pak se ptal nato jestli se da insert udelat v jednom pruchodu ( tzn ne ze prvek zatridim a pak vstoupam vzhuru a provadim stepeni preplnenych uzlu...spravna odpoved je delat dopredne stepeni ( kdyz jdu dolu tak plne uzly preventivne rozstepim abych tam mel misto cimz amortizovane zlepsuju slozitost ) Potom A-sort, Redundantni B-stromy, B*-stromy ( tohle vsechno jen v rychlosti...proste chtel vedet ze vim jaka je tam myslenka )

3) Metody odstranovani sumu (Digitalni zpracovani obrazu) Tohle zkousel Pelikan, Zara jen sedel vedela pozoroval. Popsal sem kratce modely sumu ( Gamma, Exp, Gauss, Impulzni ) Nasledoval konvolucni fitr, frekvencni low pass filtr (+vztah mezi nimi : tedy konvolucni teorem + FFT ), medianovy filtr, filtrace pomoci waveletu, anizotropni filtr ( viz flusserovi slidy ...detekce hran a pak rozmazani mimo tyto hrany. Pelikan se tvaril spokojene nakonec se zeptal jestli vim jak funguje odstranovani sumu pomoci rotacniho okenka ...to sem vubec netusil co to ma byt, tak dodal ze to pry uci Hlavac na svoji prednasce ale ze je to jen takovy detail a tim to skoncilo.

4) Interkativita ve VRML Tady to prevzal Zara ( bohuzel, Pelikan je imhho o dost mirnejsi, Zara v tom celkem rejpe ) Senzory, Manipulatory, EventIn, EventOut, Route To, Interpolatory. Pak se ptal na strukturu uzlu Collision (chtel vedet jaky atributy tam jsou a jak se pouzivaji...tady sem zacinal tapat protoze do takovych detailu sem to neumel. Posledni otazka jak ve vrml implementovat teleportaci avatara kdyz se stiskne napriklad tlacitko ...to sem navrhl par moznosti, zadna se mu prilis nelibila ( respektiva zadna by pry nebyla realizovatelna ve VRML ) Spravna odpoved byl udajne uzel Anchor. Tim to nastesti skoncilo ( mam pocit ze cim dyl by se ptal tim horsi celkovej dojem bych zanechal :D )

5) Komprese PNG a GIF Nejhorsi otazku sem si nechal na konec...tuhle sem absolutne nemel pripravenou, navic ji zkousel Zara Snazil sem se co nejdyl mluvit o obecnych metodach komprese obrazu ( RLE, Huffman, LZ77, LZW, Aritmeticke kodovani, Transformace obrazu ) ...to me ale Zara brzo zarazil ze to moc nesouvisi s tim na co se me ptaji at zacnu byt konretnejsi Tak sem otocil papir a tam sem mel par strohych poznamek o PNG a GIF formatech Kdyz sem to zacal komentovat tak me Zara prerusil at je spis vzajemne porovnam kdyz o nich mluvim.

Co konkretne ho zajimalo: oba bezeztratove, LZ77 vs LZW, ze oba pouzivaji progresivni metodu zobrazeni, Proc muze mit PNG lepsi kompresni pomer nez GIF kdyz GIF pouziva modernejsi LZW oproti LZ77 ( odpoved ze LZ77 muze byt lepsi nez LZW na nekterych vstupech protoze je to uplne neco jinyho se mu moc nelibila...spravna odpoved je podle Zary ze tam je lepsi prediktor) No casto sem tady tipoval, hodne sem toho nevedel, parkrat me Zara poucil jak ze to vlastne je...celkem bida, ale mel sem pocit ze k vyhazovu sem mel jeste furt nejakou rezervu

12. a 13. 9. 2011

Iba v skratke, Mat Lingvistika, mozno to niekomu na nieco bude :)

1. Zlozitost a vycislitelnost -- Dr. Kryl RS a RSM mnoziny, prevoditelnosti - pri zadani spominal aj simple a kreativne, ale nastastie sme sa az tam nedostali, to som sa uz neucil. Definicia zakladnych fcii, operatorov, definicia RS RSM mnozin, potom ze to je ekvivalentne s generovanim pomocou oborov hodnot, tie vety o vztahu rng a RSM, vzdy sa opytal aj na myslienku dokazu. Postova veta (tam sa mu viac pacila odpoved 'pustime dva programy a cakame, ktory skor zastane' nez ten predikat, ktoreho potom selektor je char fciou), potom som zadefinoval 1- a m-prevoditelnost, 1-uplnost, dokazal, ze K je 1-uplna, napisal halting problem a Kryl odchadzal spokojny.

2. Datovky -- hashovanie a trie.. Dr. Zeman Nastastie taka prehladova otazka, kedze som ju odpovedal ako poslednu, tvoril som to pocas odpovedania, rozpisal som druhy hashovania, potom zmienil univerzalne (principy ~ ku kazdej S vyberieme nejaku fciu z H, H c-univerzalna, napisal som funkciu h_ab(x), a ze je c-univerzalna), perfektne hashovanie, opat som zacal ako to principialne funguje a v polovici som bol zastaveny a ze mam este o triach porozpravat, tak som opat vysvetlil princip, dalej ako sa to potom komprimuje (v style, potom vznechame tie uzly, kde nedochadza k plodnemu vetveniu, potom to mozeme zapisat do tabulky, tu do dvoch poli, etc), spokojnost

a nasledna cast bude asi pre ostatnych menej uzitocna

3. Obecna lingv -- FGD -- Dr. Kubon Tiez som rovno odpovedal, iba som si rozkreslil roviny, popisal vztahy, co na ktorej rovine je, potom som hovoril o valencii slovies, podst mien a ked som chcel prejst k aktualnemu cleneniu, tak mi bolo povedane, ze to viem a ze uz netreba

4. Rozhodovacie stromy -- Dr. Holub Stop kriterium 'nemame ziadne atributy' v ID3 algoritme bolo vyhlasene za nespravne :) Potom sme sa dost tocili okolo toho, ako vyzera funkcia c(x) = y, ked mam postaveny rozhodovaci strom. To som celkom nevedel, ako zapisat, tak som ju napisal ako pseudokod pomocou if-then-else podmienok, stale neviem celkom, ako to malo vyzerat nejak analyticky(?). Potom sme sa bavili o vybere atributu (netreba to zabudnut nasobit pravdepodobnostou tych dat vybranych podla daneho atributu), potom crossvalidacia a ako si urcim konfidencne a intervaly a co vlastne tieto intervaly znamenaju.

5. Strojovy preklad -- Dr. Zeman Strucne som spomenul historiu, opisal trojuholnik prekladu, spomenul pravidlove metody, opisal fungovanie statistickeho prekladu (noisy model, jazykovy model, prekladovy model, zopar obrazkov, ako sa frazy na seba mapuju), potom o trenovani vah pri feature functions, ale len obrazok pri MERT a jeho opis stacil, potom o evaluacii a jej problemoch, BLEU a par prikladov z ceskych prekladovych systemov.

Celkovo boli vsetci mili a nik sa nesnazil cloveka nejak dobehnut a pod, takze je len potrebne sa ucit alebo vediet a mat prehlad :)

Na zaver velka vdaka vsetkym, ktori sa podielali na pripravach materialov, boli velmi napomocne.

12. a 13. 9. 2011

Koubek (slozitost a vycislitelnost) - Cook-Levinova veta

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

Majerech (DS) - binarni stromy, vyvazovani

AVL, RB, hlavne definice a invarianty a hloubky, operace a rotace vlastne ani nechtel. Spocital se mnou minimalni pocet vrcholu pro danou hloubku u obou stromu a prestoze mi to moc neslo, tak byl nakonec spokojenej.

Kofron (OCS) - model checking

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

Obdrzalek (OSY) - sprava pameti

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

Yaghob (prekladace) - generovani kodu, alokace registru, scheduling

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

Kucera (slozitost a vycislitelnost) - NP-uplnost, Cook-Levinova veta

definice NP, prevoditelnost, NPC, prevod na kachlikovani a na SAT

Koubek (DS) - reseni kolizi v hashovani

napsat vsechny algoritmy a porovnat je z hlediska pametove a casove narocnosti, prumerna delka retezcu, jak to ovlivni cachovani

Yaghob (prekladace) - LL analyza

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

Bures (OCS) - prototypy a klony

co je to prototyp, klon, jake jsou zpusoby klonovani, jak se resi dedicnost, vyhody oproti class-based, priklad v Selfu

Kofron (ANSS) - informacni bezpecnost

autentizace, autorizace, kryptografie (symetricke, asymetricke sifry - na cem jsou zalozene, kdy se pouzivaji), bezpecnosti utoky, hashovaci funkce

2. 2. 2011

Obecne: Je toho daleko vic, nez se na prvni pohled zda. Ucil jsem se mesic (prvni 3 tydny tak 4-5hodin denne, posledni tyden i 12hod denne) a nemel jsem pocit, ze uz to lepsi byt nemuze :-) Celkove nas bylo tusim 24, z toho 7 si to bohuzel bude muset zopakovat. Byli jsme rozdeleni do tri skupin. Kazdy dostal behem prvnich cca 10min vsechny otazky a mel dane poradi, ve kterem je ma vypracovavat a take inicialy zkousejicich, ktere uz potkal pri zadani otazek, clovek tedy tusil na co se ma tesit :-) Zacinalo se neco po devate a z mistnosti jsem odchazel kolem pul druhe, a to jsem celou dobu bud psal odpoved, nebo diskutoval se zkousejicim. Ke konci toho ma uz clovek fakt dost.

Otazky:

1. Distribuovane systemy: Jmeno zkousejici bohuzel nevim, videl jsem ho snad prvne [asi pan Konfron]:-) Dal mi: distribuovane vylouceni, volba koordinatora, konsenzus a detekce glob. stavu. Toto jsem nastesti docela umel, takze jsem popsal 3A4 nez prisel. Otazka byla u konsenzu kdo je to tedy ten general (koordinator) a jak mam zarucene, ze konzistentni rez bude "dobry" glob. stav. neco jsem rekl, s cimz byl spokojen a dal me netrapil. Znamka: 1

2. Architektura siti a pocitacu Tady nam hned nazacatku bylo sdeleno, ze pan Peterka je bohuzel nemocny, takze zkouset nebude. Ja jsem dostal pana Obdrzalek, virtualni pamet. K cemu to je, vyhody nevyhody a tak. Popsal jsem zase 3A4 od 2-urovneveho po 0 urovnove, segmentace, segmentace + strankovani, inverzni, zacal jsem psat algoritmy vypadku stranky, kdyz prisel. Nechal si to ode me vypravet. V jednu chvili jsem rekl neco jako "no a pak ten uzivatelsky prostor bude 4GB velky, z cehoz bude treba 3GB pristupne, protoze ve zbytku je kernel a tak", nacoz se dost zamracil, ze proc zrovna 3GB, ze svet neni jen PC, Windows a Linux, ze virtualni pamet tu byla uz pred 50 lety....tak jsem rekl, ze jsem to chtel uvest jako priklad, nicmenne ho to zcela evidentne nastvalo :-) Mel pomerne dost doplnujicich otazek, typu "a jake dalsi vyhody to muze mit" (virt. prostor muze byt nejenom vetsi, ale i mensi - zpetna kompatibilita programu, respektive jistota, ze kazdy ma maximalne X), dale jak velke jsou strankovaci tabulky v ruznych pripadech, kde to chtel odvodit obecne (coz jsem nejak vypotil), dale proc nemuze mit clovek 3kB stranky, jak jinak by se dalo segmentace resit (neco jako bully algoritmus, pry to bylo na mainframech, dale jake to ma vyhody a nevyhody...). Otazek bylo hodne, nakonec jsem jich vetsinu snad dal dobre, u nekterych musel ovsem naznacovat pomerne dost. Na tuto otazku jsem se pomerne zameroval, myslel jsem, ze tomu fakt rozumim, znal jsem i priklady procesoru, kde to jak je. A stejne bylo par otazek, kteryma me zaskocil...Dal bych si na toto pozor. Znamka: 1-

3. OSy Bulej, synchronizacni primitiva: Jedna z jednodussich otazek, popsal jsem co to je, kdy je to potreba, co je to race, kriticka sekce. Jake jsou jednotliva primitiva, jak se implementuje aktivni zamek, mutex pomoci aktivnih ocekani (bez fronty, s frontou bych to tam potil asi docela dlouho). Pan Bulej byl prijemny, prisel ale brzo, takze jsem nestihl implementovat producer/consumer pomoci meho zvoleneho primitiva (semafory), to tedy po me chtel "on-the-fly". Trochu sem se v tom zamotal a navic on asi nepochopil mou implementaci skladu pomoci promenne "int count", takze jsme si chvili nerozumeli, ale nakonec jsem to ze sebe spravne vypotil. Dalsi otazky byly na TSL na multiprocesoru (barriera, cache ping pong), rozdil mezi monitor a cond. var [pry to wait/wakeOne/wakeAll maji stejne, tak v cem se lisi a to, ze jedno je v prog. jazyce byla jen cast spravne odpovedi - neco jsem tam rikal, nakonec si asi namatchoval, co chtel slyset, ale priznam se, ze uplne chytry jsem z toho nebyl]. Pak me jiz nechal byt s tim, ze jsem to celkem umel, ale za ten semafor musi dat 1-, coz me prijemne prekvapilo. Znamka: 1-

Kolega vedle dostal tusim DMA a malem ho na nej vyhodili, chteli po nem pomerne dost detailu, kdo kdy a jak obsluhuje sbernici, co kdo kdy prenasi, jak si to signalizuji...na tuto otazku bacha.

4. Vycislitelnost/Slozitost Majerech, Algoritimicky vycislitelne funkce, definice, vlastnosti. Pana Majerecha jsem se bal, ale nakonec byl opravdu hodny! Zdalo se mi, ze poznal, ze tomu clovek rozumi, par otazek a dal se jiz na nic neptal. Napsal jsem definice pres funkce/operatory, pres TS, dale pak mnoziny/predikaty/jazyky. Inkluze + co za funkce jsou, aby to nebylo ostre [bez definovani], par otazek na overeni, ze tomu rozumim a vse ok. Zadne detaily ci Velmi prijemne zkouseni. Behem zkouseni si k nam prisedl i Martin Mares, ktereho to evidentne bavilo a dokonce mi i jednou napovedel :-) Znamka: 1

5. Datovky Kopecky, Haldy a trie priznam se, ze me celkem zaskocilo, ze jsem nedostal jen jeden/dva typy hald, respektive ze k tomu byly i trie. Pan Kopecky se zeptal, za jak dlouho to asi bude trvat, nacez jsem odpovedel, ze pokud mam napsat vse, co vim tak asi hodinu a pul :-) Navrhl jsem zkouseni "on-the-fly", protoze toto jsem celkem umel, ale pan Kopecky chtel byt korektni a nechal mi tedy asi 20min na pripravu, to jsem stale psal a tak tedy vzhledem k pokrocile dobe prikyvnul, ze mu to mam povykladat to co mam na papire + treba neco kolem. Probrali jsme tedy d-regularni haldy, binomialni, tam jsme to cele ani nedodelali, zacal jsem fibinacciho a tam bylo prohlaseno, ze to umim a ze to staci. Coz jsem byl rad, protoze trie jsem umel uz mene :-) Znamka: 1

Toz tak. Celkove byly zkousejici hodni, jedine snad pan Obdrzalek byl takovy dost narocny. Nepochopil jsem, ze to chce uplne obecne a me vety typu "stranky jsou typicky 4kB" se mu moc nelibily. Jeho otazky mi taky prisly pomerne detailni ve srovnani s ostatnimi zkousejicimi. Ale dalo se na ne prijit a trochu jsem to cekal, coz bylo moje stesti.

Zaroven chcu podekovat kolegum, s kterymi jsem si to v labu opakoval a to predevsim ty z nich, s kterymi jsme tam byli cely den. Clovek si udelal ve vsem jasno, ikdyz vycislistelnost, slozitost a vpodstate i datovky jsme delali celej den (10 hod). Potom jsem mel ale fakt pocit, ze uz tomu rozumim.

2. 2. 2011

1. Programovaci jazyky a prekladace: LL-analyza (Bednarek) Napisal som o co ide, popisal lavu rekurziu a lavu faktorizaciu, zadefinoval FIRST a FOLLOW a potom obe metody na implementaciu z Yaghobovych slidov: rekurzivni sestup a nerekurzivni analyza s predikci.

2. Modely a verifikace programu: CTL, LTL, CTL* (Kofron) Popisal som vlastnosti jednotlivych logik, potom sme sa chvilu hrali s vyznamom formuli CTL a LTL (GF vs. AG EF).

3. Slozitost a vycislitelnost: NP-uplnost (meno neviem, inicialy ML) Zacal som definiciou Turingovho stoja a postupne som definoval vsetko az po NP-uplnost, dokazal kachlikovani, prave ked som pisal prevod KACHL->SAT tak prisiel skusajuci, pozrel sa na to vsetko a povedal ze to staci.

4. Analyza a navrch softwarovych systemu: Agilni programovani (Obdrzalek) Tu som nevedel v podstate nic, moja odpoved sa zakladala na tom co som si odvodil z vyznamu slova 'agilni'. Po par neuspesnych pokusoch naviest ma na spravnu cestu to Obdrzalek vzdal a skonstatoval, ze to je tak na 3 minus minus.

5. Datove struktury: Hasovani (meno neviem, inicialy PK) Na 2 A4 som spravil prehlad (strucny popis + pripadny obrazok) vsetkych metod co som vedel vratane externych hasovani, univerzalneho a perfektneho hasovani a dostal som par lahkych doplnujucich otazok.

Celkovo boli vsetci skusajuci dost v pohode, hlavne Obrdzalek ma mohol kludne vyhodit. Predpokladam, ze by to spravil nebyt dobrych vysledkov zo zvysnych otazok (pravdepodobne vsetky za 1). Celkovo som teda dostal za 2 zo statnic, 1 z obhajoby -> 2 celkovo.

2. 2. 2011

Ahojte, osobne sa mi tiez velmi hodili taketo postrehy, preto pridavam aj tie svoje. Upozornujem, ze som tejto skusky ucastnil uz druhy krat, pretoze ma pan Zavoral dostal na tom, ze som nepopisal implementacie konzistencnych modelov pre DSM. Hlavny problem je v tom, ze otazka je zverejnena velmi obecne a kazdy si ju moze na mieste "spodrobnit" po svojom. Preto sa zamyslajte uz pri uceni, ako dane veci aplikovat, alebo ako implementovat (hlavne v distribuovanych systemoch!).

Ja som mal hlavny okruh Architektura a principy softwarových systémů (OAKS + ANSS) a volitelny Architektura a principy systémového prostředí (DS).

1) OAKS - Triedy a metody (Hnetynka+Bures) Otazka pomerne jednoducha, zadefinoval som vsetko, co vlastne kazdodenne pouzivam. Je potrebne vediet rozdiely medzi subtyping, subclassing, inheritance, co je object layout, ako vyzeraju tabulky virtualnych metod, rozdiel medzi templates v C++ a generics, ako su generics v Jave implementovane (type erasure), diamond inheritance v C++, ... Vedel som v principe vsetko, ale moja odpoved vraj podla pana hnetynku bola niekedy taka hmlista. Bolo to celkom v pohode a dostal som asi nieco medzi 1 a 2.

2) Datovky - Triedenia na vonkajsej a vnutornej pamati (Kopecky + Mares) Popisal som vsetky zname mergesorty, haldy a ich variacie na vonk. pamati a klasika quick-, merge-, heap-, insertion-, bubble-, ... -sorty na vnutornej pamati. Pre vsetky som ukazal ich casovu zlozitost. Otazky sa tykali ich porovnania v roznych pripadoch rozdelenia dat, pamatovej zlozitosti, atd. Bolo to celkom prijemne a vysledna znamka asi 1.

3) Zlozitost a vycislitelnost - Rekurzivne a rekurzivne spocetne mnoziny (Surynek) Napisal som vsetko, na co som si spomenul: rozne ekvivalencie, definicie, ... Pan Surynek si to ani neprecital a povedal, nech mu riadok po riadku prerozpravam ja. Po par slovach ma zastavil a ujistil sa, ci tomu aj rozumiem: co je to charakteristicka fcia, co je to predikat, co je to usekova fcia, ako K0 suvisi s halting problemom, povedzte priklad rekurzivne spocetnej mnoziny, ... Este chcel ukazat dokazy rekurzivnosti o doplnkoch, co je identicke s TS a bola to rychlovka za 1 bez problemov.

4) ANSS - XML, XML schema, RDF (Bednarek + Tuma) Tu to bolo zaujimave, pan Bednarek nechcel vediet nic o zobacikoch, ani marketingove zvasty o tom, preco je XML cool, ale aby som mu popisal pohlad softwaroveho architekta na XML, ako by som navrhoval aplikacie postavene na XML a pod. Dost ma to zaskocilo. Nicmenej som popisal aspon v kratkosti, co je XML, XSD, DTD, DOM, SAX, xPath, xQuery, XSL(T), aplikacie kde sa vyuziva (napr. SOAP). Ze vyjadruje syntax a nie semantiku (tu sa divne zatvaril). Proste som z praxe popisal, kde ho bezne vyuzivam. Potom prisla otazka na rozdiel oproti relacnym databazam. Mal som prist na dve vyhody XML. Prvu som trafil: rekurzia, druhu nie: odolnost voci zmenam. Ak niekto prida element, vasa aplikacia moze nadalej fungovat. Mal som sice kopec pochybnosti o tejto vyhode, ale uz som bol unaveny a sam som to dalej nenatahoval. To uz pan Bednarek povedal, ze je to ok a ze nieco medzi 1 a 2. Musim povedat, ze Bednarek je velmi korektny skusajuci.

5) Distr. systemy - RPC (SOAP, .NET remoting, CORBA, RMI) (Bures + Bulej) Mal som kazdu technologiu popisat a potom jednu si vybrat, napisat v nej konkretny kod a podrobne vysvetlit. Jednoduchy ale spravny kod som napisal v RMI, Bures sa ma vsak pytal na podrobnosti v CORBA-e. Co je to IOR, Object ID, servant, POA, politika, AOM, ako to cele funguje, preco to funguje. Videl, ze tomu rozumiem a po par minutach povedal OK a za 1.

Celkovo za 1 a musim povedat, ze otazky som mal fajn, ale aj napriek tomu sa pytali veci dost do hlbky. Nemal som pocit, ze beru ohlad na to, ze som tam druhy krat. Poznam zial pripady, ked v ten den par ludi vyhodili az druhy krat:( Pred tymto terminom som bol dost nervozny, predtym som z ustnej skusky nikdy nevyletel:D Celu noc som nespal, bol som totalne unaveny, ale snazil som sa mysliet pozitivne a to asi pomohlo...

Inak zamyslenie na zaver. Myslim, ze nasa statnica je zbytocne narocna, otazky zadane totalne povrchne a na mieste otazky do takej hlbky, ktoru mi studium na MFF zial neposkytlo. Polovicu mojej pripravy som venoval studovanim knih (Cardelli, Tannenbaum, wiki, ...). Chore je to v tom, ze neviete, kto vas moze skusat. Ten skusajuci potom vedomostami moze realne pokryvat 1/3 okruhu a drvi vas na tom. Ak by sa otazky tahali, komisie by sa mohli kludne zverejnit. Teraz sa totiz asi boja, ze poznat komisiu znamena vediet dopredu, co dostanete. Je to viac nez smiesne... Zavisi to ale asi pripad od pripadu. Alebo keby aspon tie toazky boli podrobnejsie zadefinovane.

2. 2. 2011

pro ty, kteri si tohle ctou a statnice je prave ceka mam jedinou radu: Don't panic! ;]

Jo a taky se ucte (pokud jeste mate cas a co), bez toho to asi vazne nejde, pokud nemate extremni stesti (udajne je optimalni tomu venovat alespon tak mesic - jeden clovek se ucil dva a vyletel, ja osobne se ucil nejakych 10 dni, realne spis tyden a prosel jsem...je to individualni).

A ted vlastni otazky:

APS (nejaky mlady zaskok za nemocneho Peterku) - TCP/IP Totalni pohoda, trochu se v tom sice postoural, ale nic zaludneho. Stacilo obecne popsat vrstvy, porovnat ramcove s ISO/OSI, napsat ke kazde vrstve par protokolu, popsat IPv4 vcetne adres, problem nedostaku adres - NATovani a IPv6 a podrobneji co vsechno za novinky to ten IPv6 prinasi. Je dulezite znat podrobneji nejake konkretni protokoly. Mne trochu dostal, kdyz jsme zahloubali do DHCP (ale chytil se ho proto, ze jsem ho tam napsal jako priklad) a jake zpravy se posilaji, jak a jake IP adresy jsou v tom packetu, kdyz DHCP je aplikacni protokol (a nejake tam byt musi), ale nove pripojivsi se stroj je logicky nezna. 1-2 (stydim se, bo site jsou moje hobby)

DS (Tuma) - RPC Klasika...stoural se v tom hodne, hlavne jak to realne vypada, co presne si o tech ditribuovanych objektech predava za informace, jak se adresuji apod. Docela do hloubky (na muj vkus - metoda v sobe vola objekt z jednoho serveru a pozdejc v podmetode z jineho serveru, co se teda preda za adresu, komu, jak...), na druhou stranu nic co by melo cloveka podrazit. Kdyz se nad tim clovek zamysli, vyplodi to (i kdyz u mne s komentarem ze to ze mne leze jak...ani nemuze rict z ceho:). Zrejme jsem mel stesti, ze jsem nerekl zadnou kravinu a kdyz jsem si jeste nebyl jist, ze vidim, kam mne smeruje, nechal jsem ho do mne kopat vesele dal (to komentoval slovy, ze je sice pekne, ze mi to vyklada on, ale on, ze to umi, a ze by to melo byt spis opacne a vykladat bych mel ja:). 2-

OS (Bulej) - Virtualni pamet, strankovani Chtel hlavne popsat a nakreslit princip strankovani, jednourovnove a viceurovnove, metodiky vymeny stranky (LFU, LRU, NRU...) a proc jsou vubec potreba (protoze idealni stav vyhozeni vzdy te, co bude volana nejpozdejc nejde dosahnout). Pak se do toho pustil a rozebral me znacne schematicke nakresy az na kost - chtel vedet jake atributy jsou ve strankovacich tabulkach u kazdeho zaznamu, proc tam jsou, ktere tam byt musi (nutne jestli je platna nebo ne a nejake bitiky pro vyhazovaci metody, treba Acessed,Dirty, pak se hodi treba cached bit a mozna dalsi rozsireni). Drobatko jsem si zaplaval, ale vse jsem nejak dovodil a nikde nehodil zadny extremni kiks, tak mi jeste dal prakticky priklad na strankovani a kdyz jsme ho (znacne spolecnymi silami) dotahli, tak mu to stacilo. 1-2

Datovky (P. Kucera) - Trie Vedel jsem jen uplny zaklad jak to vypada a k cemu se to pouziva, celkove jsem popsal tak 1/2 stranky s kratkym prikladem. Cekal jsem, ze tohle mozna neprojde, ale Kucera jen rekl, ze to jsou jen ty trivialni veci, ze ty hezke, netrivialni se tykaji komprimace struktury, ale ze vim co to je, ze priklad, co jsem napsal se mu libi (bo nahodou jsem ho nacmaral tak, ze se na nem nedalo dobre ukazat, jak super je ta komprimace, co jsem neumel:) a pustil mne. 3

Vycislitelnost (Loebl) - Ekvivalence ruznych definic algoritmicky vycislitelnych funkci Moc jsem nevedel, co presne u tehle otazky bude chtit videt (jasne, Churchova teze, kterou jsem mimochodem nezformuloval tak uplne ciste spravne, ale dal?:) a tak jsem tam naflakal vsechno - CRF, ORF, PRF, RM, RSM, RSP, ORP, jazyky, DTS, NTS - CRF jsem odvodil ze zakladnich funkci pomoci operatoru, ukazal jsem inkluzi s ORF a PRF, naznacil jsem, jak si odpovidaji CRF a NTS a RSM, ORF a DTS a RM. Loebl byl velmi prijemny, prosel si to, chvili dumal nad tim, co se mnou (asi to nebylo uplne ono co chtel videt), rekl, ze tomu zjevne asi rozumim, ale, ze mu chybi nejake prakticke priklady a konkretni formalni prevody mezi vyjadrenimi a pak mi rekl, at mu tedy napisu jeste neco o UTS, pokud o nem neco vim. Nacrtnul jsem tu ctyrpaskovou konstrukci a kodovani UTS, ani jsem to nedopsal a rekl, ze staci. 1-2

26. 5. 2010

Surynek - ČRF

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

Kopecký - BVS a jejich vyvažování

BVS, AVL stromy, RB stromy, rotace. Vytvoření statického stromu pomocí dynamického programování. Mluvili jsme také o splay stromech.

Bureš - Synchronizace procesů, synchronizační primitiva.

Popis primitiv, TSL. Synchronizační problémy, detailní implementace producent/konzument pomocí zadefinovaných primitiv.

Bulej - virtualni stroje

Obecny prehled, shadow PT, virtualizace diskoveho zarizeni.

Hnětynka - Middleware

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

Peterka - detaily 802.11

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

Hladík - Úplné problémy pro třídu NP + Cook Levinova věta.

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

nějaký teoretik - B-stromy + jejich varianty.

Def., operace, složitosti bez žádných větších důkazů.

Yaghob - Mezikód.

Formy, reprezentace, optimalizace + k čemu to je vůbec dobré.

Hnětynka - Objekty a třídy v Javě. (obj + komp. systémy)

Co to je, proč se zavádí, vlastnosti, implementace VMT, object layout, dědičnost, jak je to v C++ s vícenásobnou dědičnoustí, rozdíly C++ templates a Java generics. Příklady.

Nečaský - Značkovací jazyky + XML (analýza + návrh soft. systémů)

jak to vypadá, značkovací jazyk jiný než z rodiny XML (př. TeX), XML, XML Schema, DTD, Schematron (jaký je rozdíl oproti DTD a XML Schema), XPath, XQuery, XSLT - malé příklady v každém z jazyků.

Zavoral - algoritmy virtualni synchronie

Definice virtualni synchronie, formalni definice pohledu, drobne detaily TRANS, TRANSIS, ISIS

Koubkova - haldy

d-regularni, binomialni, leftist, fibbonaci. Ukazat pridavani / odebirani prvku v d-regularni a binomialni.

Slozitost - pseudopolynomialni algoritmy

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

9. 2. 2010

Peterka - Topologie siti, pristupove metody - vedet o co jde, orientovat se a umet odpovidat na dotazy

Kratochvil - Rozdel a panuj - vedet o co jde, priklad

Zavoral - Distribuovana synchronizace, konkretne vzajemne vylouceni - co se resi za problem, algoritmy Lamportuv, Ricard-Agrawala, Maekawa, umet odpovidat na dotazy

Tuma - Filesystemy - obecne vedet problemy a principy jejich reseni, detaily k jednomu FS

Fiala - Silna NP uplnost - definice a premysleni nad timto tematem, vztah k aproximacnim algoritmum

9. 2. 2010

Bulej - Virtuální stroj (Osy)

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

Peterka - Emaily (SMTP, POP)

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

Löebl (AVL, CC stromy)

Bez problému, definice, rotace, nic moc do hloubky.

Zavoral (Distribuovaný konsenzus)

Generálové a důstojníci, dvě armády.

9. 2. 2010

Tak pridam i svuj postreh. Ja mel tyhle otazky pametova hierarchie(OSY) - zkousel Kofron, byl pomerne v pohode, kdyz clovek vysypal dostatek znalosti, tak do toho ani moc nestoural, za 1 volaci konvence, aktivacni zaznam atd (Prekladace) - zkousel Zemlicka a to co sem vedel celkem presel a stroural do veci co sem az tolik nevedel (aktivacni zaznam)..nakonec 2-3 Komponentove systemy (OOKS) - zkousel nedo mladsi z DSRG jmeno nevim, ukazal sem tak obecny prehled, rekl o COM, DBUS, naznacil CORBu, EJB a potom neco vic o SOFA...nejzaludnejsi asi byla otazka kdy jsou komponentove systemy lepsi nez objektove...celkove se moc nezajimal o COM a DBUS u kterejch sem vedel nejvic a chtel spis ty vic advanced systemy..znamka 2-3 CRF(slozistost/vycislitelnost) - napsal sem v lidske reci vsechny zakladni funkce a operatory, co je odvozeni, popsal co je PRF, ORF, CRF a napsal inkluze a dokazal pres Ackermana inkluzi mezi PRF a ORF...dotaz znel na mnoziny, tak sem otocil co je rekurzivni a rekurzivne spocetna...celkem v Pohode zkouska, zkousel Fiala znamka 1-2 Binarni stromy - zkousel Kratochvil..napsal sem co jsou binarni stromy, jak muzou zdegenerovat, jak vypada idealne vyvazeny binarni strom, popsat CC-stromy a AVL stromy, otazky byli ohledne slozitosti, jestli muzou rotace eskalovat a slozitost insert/delete...znamka 1

Tot vse, hodne stesti ted co to jeste ceka. Jinak doba uceni - venoval sem tomu Vanoce + 2 tydny, kdy sem se denne(7dni/tydne) ucil s prestavkami cistyho casu 7 hodin (typicka sem zacal v 9 rano a skoncil v 9 vecer, coz dava prehled o mnozstvi a delce prestavek :)

9. 2. 2010

Kým na to zabudnem, pridám aj svoje postrehy do pléna:

moji skúšajúci: Fiala (DS), Tůma (OSY), Peterka (APS), Pelikán (DZO), Kratochvíl (V/S)

na začiatok treba povedať, že aj ja som mal s uvedenými výborné "skúsenosti" - poväčšine sa žiadalo skôr pochopenie problematiky a prehľad, než detaily (aj keď to asi záleží, ako som čítal vyššie, od skúšajúceho) - naopak odborné/profilujúce predmety asi nie je dobré podceniť...... hodnotenie bolo takisto veľmi adekvátne, v mojom prípade myslím že aj nad očakávania dobré miestami :))

tentokrát boli štátnice vraj trochu inak ako zvyčajne (aspoň v našej skupine) - bol dopredu daný rozvrh, v akom poradí má kto odpovedať ktorú otázku. Myslím, že to bolo užitočné a celkom aj funkčné - človek nemusel čakať 2 hodiny na každého profesora...

DS: haldy a fibonacciho haldy... asi na 3/4 stranu som si rozpísal d-reg., bionom. a lazy. binom haldy (čo to je, aké sú tam operácie, ako približne fungujú, aká je cca. (amortizovaná) O() :)), na fibonacciho mi ostalo pár riadkov na konci... väčšinu odpovede som strávil zbežnými komentármi k haldám, takže po pár minútach som asi vyčerpal trpezlivosť a pri fibonacciho sme len prediskutovali, aké majú výhody (decrease/increase key, delete, O(1) atď...) a bolo hotovo...

OSY: štandardná, správa pamäti - stránkovanie, algoritmy... (segmentáciu nechcel, tentokrát).. doc. Tůma si ku mne sadol, keď som z tej otázky asi tak 2 riadky, ale tak súhlasil som s on-the-fly skúšaním.. Takže miesto toho, aby som si to pripravil, tak to bolo trochu viac interaktívne - a samozrejme chcel vedieť pár (bežných) vecí do detailov (popis TLB (+ako je to s úplnou/n-way asociativitou a hw obmedzeniami), n-úrovňových+inverzných stránkovacích tabuliek (+že tie odkazy sú adresy fyzických stránok, aké sú tam užitočné atribúty atď.), postup prekladu adresy+získania dáta z RAM), nejaké tie algoritmy na výmenu stránok, otázka padla aj na to, či sa tam akože fakt pri každom prístupe na stránku zapisuje A/D flag, pýtal sa čo sa dá robiť s trashing programom (to som moc nevedel, snáď to niekde bude - ja som tipol pridanie ram :)))), zamknutie stránok, obmedzenie working setu... asi chcel niečo dalšie..)... Po asi 15 minútach rozhovoru (a celkom očakávateľných otázok) sa opýtal či stačí 2, tak som neprotestoval radšej... Bodaj by som, keď som v strese najprv povedal, že v stránkovacích tabuľkách sa ukladajú čísla virtuálnych stránok :)))

APS: aktívne sieťové prvky, switche, routre. Mal som tam prípravu asi na stranu - čo sú to bridge, switche, routre... Myslím že toto konkrétne som vedel asi najhoršie, nakoniec ale bolo hodnotenie veľmi príjemné, tiež za 2... "Špeci" otázky: aký je max. počet repeatrov na ethernet sieti (a či to je na celom segmente, alebo inak (=medzi 2 počítačmi)), prečo to je tak (jam signál), ako sa rieši jam na rýchlejších sieťach; aký je rozdiel medzi switchom a bridgeom (switch je optimalizovaný na prepájanie, bridge na filtráciu? tuším... :) ), čo je to layer 4 switch, IP gateway... k routerom sme sa nakoniec už nedostali, mal som tam akurát spomenuté nejaké základy + "routovacie protokoly"

DZO: inverzné a pseudoinverzné filtrovanie - toto som mal ako úvod v diplomke :)) spomenul som čo je to dekonvolúcia, aké sú tam problémy pri použití inv. filtra (šum), ako funguje wienerov filter, ako sa približne hľadajú tvary rozmazania pomocou parametrických metód (a prečo to väčšinou nefunguje :)) ), mal som ešte naznačné odšumovanie - k tomu sme sa ale nedostali... po 5 minútach hotovo :)

VS: RM a RSM a súvislosť s ČRF... stihol som to tesne pred obedom, zadefinoval som operácie, ČRF, spomenul PRF<ORF<ČRF (+ackermanku, "nekončiacu fciu"), RM/RSM, RP/RSP, že sa črf dajú očíslovať (+kleeneho veta), čo je W_e, K, napísal dôkaz že "K je RS, not R; neg(K) nie je RS".. v tú chvíľu ma skúšajúci zastavil, takže sme sa vlastne k RSM množinám už ani nedostali :) mal som tam ešte niečo o selektore, 1-prevoditelnosti/úplnosti, postovu vetu, úsekové fcie... každopádne myslím že človek si tu s pochopením základov vystačí a kým nie je na teoretickej informatike, tak fakt netreba zo seba ťahať podrobné dôkazy napr. Kleeneho vety... :)

Celkovo mgr. štátnice boli nakoniec pre mna snáď príjemnejšie ako bc...

Good luck všetkým nasledujúcim generáciám :-) Btw, bude ešte nejaká oslava? :-D Či až v júli/červenci? :)

9.9.2009

Čepek - Haldy (okruh Datové struktury)

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

Majerech - Aproximační algoritmy a schémata (okruh Složitost a vyčíslitelnost)

Definice AA, poměrová a relativní chyba, AS, PAS, ÚPAS, ÚPAS pro SP (pozor na písmena v popisu PROŘEŽ (1-d)z < y < z), AA pro TSP

Peterka - Přenosové služby - spojovanost/nespojovanost, spolehlivost/nespolehlivost, pohled dle TCP/IP a RM ISO/OSI (okruh Architektura počítačů a sítí)

Definice, rozdíl mezi nespolehlivostí a best-effort (nespolehlivost - příjemce nežádá nápravu při chybném přenosu, best-effort může být i spolehlivá, je to spíš věc odesilatele), navíc ještě tag switching (např. MPLS) a jestli ATM je přepojování paketů nebo okruhů (paketů, ale dokáže v CBR simulovat virtuální okruh)

Obdržálek - Správa paměti (okruh Operační systémy)

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

Tůma - Komunikace, zprávy, RPC (okruh Distribuované systémy)

Co je to zpráva, jak vypadá, že se ztrácí, co s tím

RPC - co je IDL, jestli to jde i bez toho, co se generuje (stub, skeleton (přilinkování) a headry (includovani) pro klienta a server), transparentnost - globalni promenne, pointery, objekty v RPC (jsou na serveru, klient má proxy, kde se vezme? naming služba. Kde běží? Jak se tam vezmou reference na objekty?)

Threading model serveru. Podle čeho poznám kolik vláken má mít Thread pool? (podle workloadu - 1) processor-intensive = cca tolik vláken kolik procesorů 2) hodně s diskem a čekání = trochu víc), jak se liší použití RPC a messagingu (synchronnost, one-to-many u messagingu), JMS, může si každý naimplementovat svojí name service?

Surynek - Binární stromy a vyvažování

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

Matoušek - NP-úplnost

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

Peterka - Přístupové metody

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

Bureš - Souborové a adresářové služby, souborové systémy

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

Hnětynka - Komunikace, zasílání zpráv, RPC

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

28.5.2008

Zavoral - distribuovaný konsenzus

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

Yaghob - podpora multiprocesoru v OS

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

Obdržálek - virtuální pamět

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

Zemlicka - trideni ve vnitrni pameti

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

Jakysi mily teoretik - savitchova veta

Napsal jsem vetu, myslenku dukazu (sestrojime turingac, simulujeme vsechny vetve, recyklujeme + pamatujeme stavy...) v pohode stacilo, zeptal se me jeste na par otazek a o.k.

Trpělivý teoretik - Pseudopolynomiální algoritmy a aproximační schémata

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

Spěchající teoretik - Stromové vyhledávací struktury

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

Adámek - Komunikace a synchronizace procesů, uváznutí

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

Adámek - Middleware (CORBA, DCOM, EJB)

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

Peterka - Přenosové služby (spojované/nespojované)

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

18.9.2008

Hnětynka - distribuované objekty

Napsal jsem krátký obecný kec, CORBA IDL, mapování do jazyků, pár problémů s nimi, POA, znínil pár jejich policy, stručně popsal Naming Service, zmínil Trading Service, v bodech popsal Java RMI. Hnětynka si to přečetl a pak se ptal na nějaké další "vychytávky":

• dynamic invocation
• zda se objekt vždy úspěšně zaserializuje
• jak funguje Naming Service, kde se vezme reference na něj
• zda se v RMI generují stuby a skeletony, (a nějaké další)

Z těch doplnujících otázek jsem věděl (či uhodl) tak každou třetí, známka: 2 - 3 (asi)

Tůma - podpora pro OOP v překladači

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

I4 (Diskrétní modely a algoritmy)

2. 9. 2013

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

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

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

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

2. 9. 2013 (jiný student)

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

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

2. 9. 2013 (jiny student, jiny nez jiny student)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.