16.6.2015

(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

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

(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

(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 :)

(Kučera, ke konci i Majerech) - prolítnul můj důkaz LHALT 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...