Státnice - Informatika - Zkazky / zkušenosti/I2

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Databázové systémy[editovat | editovat zdroj]

16.6.2015[editovat | editovat zdroj]

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 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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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:[editovat | editovat zdroj]

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:[editovat | editovat zdroj]

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:[editovat | editovat zdroj]

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:[editovat | editovat zdroj]

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:[editovat | editovat zdroj]

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:[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

18.9.2017[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Č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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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