Průběh magisterských státnic 18. září 2017

Napsal jsem blog post zde: https://hudecekpetr.cz/cs/magisterske-s ... a-matfyzu/

Samotné otázky, které jsem měl, byly:

Datové struktury: Splay stromy. (bez upřesnění)
Definoval jsem je, ukázal jsem, jak fungují operace insert, find a delete a rotace zig, zig-zig a zig-zag. Nastínil jsem, že důkaz jde přes potenciálovou metodu, a za potenciál bereme logaritmus velikosti podstromu v uzlech, ale důkaz samotný jsem neznal a i ideu bych měl problémy dát dohromady. Řekl jsem, že splay strom je užitečný pro situaci, kdy se vyhledává malá podmnožina prvků. Řekl jsem časovou složitost, amortizovanou a nejhorší, ale nedokazoval ji. Zkoušející se ptal na definici amortizované složitosti.

Složitost a vyčíslitelnost: Algoritmicky nerozhodnutelné problémy. (bez upřesnění)
Definoval jsem rozhodnutelný a rozpoznatelný problém/jazyk/množinu, kódování Turingových strojů. Řekl jsem bez důkazu Postovu větu a Riceovu větu a prohlásil, že diagonalizační jazyk, univerzální jazyk a jazyk halting problému jsou nerozhodnutelné a tyto jazyky definoval. Provedl jsem úplný důkaz nerozhodnutelnosti diagonalizačního jazyka. Zkoušející se ptal na nerozhodnutelné problémy nesouvisející s Turingovými stroji (neznal jsem) a na příklad rozpoznatelného jazyka, který není rozhodnutelný (řekl jsem halting problém).

Databáze: Rekurze v SQL. (bez upřesnění)
Řekl jsem, že SQL rekurzi časem dostalo i do standardu, že bez ní nelze řešit některé úlohy jako je tranzitivní uzávěr, a dal jsem příklady dotazů, kde se rekurze hodí. Ukázal jsem, jak lze syntakticky rekurzi provést na dvou příkladech zapsaných v SQL pomocí Common Table Expressions, a jak bude vyhodnocena. Zkoušející se ptal, co se stane, když bude rekurze nekonečná (databázový systém ji po konfigurovatelném počtu iterací zastaví), a v čem je Datalog silnější než SQL rekurze (nevěděl jsem; odpověď je, že v Datalogu je možné rekurzí naplňovat více tabulek současně).

Analýza a architektury software: Servisně orientované architektury. (zkoušející upřesnil, že chce praktickou a principielní definici, že chce vlastnosti SOA systémů a jejich výhody, a technologie užitečné pro SOA).
Řekl jsem k tomu hodně věcí. Zkoušející měl otázky, které jsem měl problémy odpovědět.

Rozšířené programování: Generické programování. (zkoušející upřesnil, že chce vědět, co to je a k čemu to je, a výhody a nevýhody přístupů k generice v různých, alespoň dvou, programovacích jazycích)
Dal jsem nějakou jakž takž definici, řekl jsem, k čemu je výhodné a jak se většinou používá (kolekce, kontejnery). Popsal jsem rozdíly mezi C++ (compile-time šablony), Javou (type erasure) a C# (runtime konstrukce typů) a nějaké výhody a nevýhody každého. Zkoušející se ptal na zásadní rozdíly mezi C++ a ostatními dvěma jazyky a na to, jak funguje kovariance a kontravariance.

Dodám dnešní skóre 7 prošlo, 2 ne, Většina ano jedničky, pár dvojek.

V Databázové skupince zkoušeli Pokorný, Kopecký a Kruliš. Zejména poslední jmenovaný mě velice příjemně překvapil (neznala jsem ho z žádného předmětu), jeho otázky na vytažení znalostí o kterých zkoušený netuší že je má, mi dávaly smysl, dobře vedly a měla jsem z nich dojem, že pomáhaly.

Nerozhodnutelné problémy
B stromy
Datalog s negací a stratifikace
Bool a Vektor model
Indexace relačních dat, R stromy

DB odborné okruhy jsou slušně nahozené na matfyz wiki (díky, PetrBlack),není to úplně vše pokrývající ale pro rychlé vpravení se do tématu je to super začátek.

Pozorování z dneška-
Pozor na věčně zásekovou věc, kdy zkoušející chce slyšet něco jednoduchého a student má dojem, že "to přece vlastně řekl" nebo "je to zřejmé" - ale neřekl to tak úplně.
Nerozhodnutelné problémy - otázka "a znáte nějakjé další" je standard.
Zajímají je (základní) praktické aplikace - kde se to vyskytuje, k čemu, na co by se to hodilo.
Ilustrovat dynamické programování Fibonacciho posloupností (jak je na státnicové wiki) nestačí. Vyberte si cokoliv, kde ta dynamika opravdu něco dělá.

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!).