Databázové systémy

{{:Státnice_-Informatika-Zkazky/_zkušenosti/I2_db}}

Ostatní

18.9.2017

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

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

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

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

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

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

16.6. 2015

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

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

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

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

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

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

18. 9. 2014

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

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

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

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

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

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

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

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

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

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

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

2. 6. 2014

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

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

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

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

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

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

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

Datové struktury (Hladík): Fibonacciho haldy

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

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

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

Motivace modelování, model driven development (jen tak z rychlíku), šlo více méně o to popsat proces tvorby digramů a kde se tam ta data a procesy berou - inspirace v MSA.

Do jisté míry jsem měl při diskusi pocit, že jde o to dokázat dost dlouho a dost rozumně mluvit (improvizovat) k tématu, ale možná je to tím, že obě předešlé otázky byli z více formální roviny.

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

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

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

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

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

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

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

** Poznámky **

Atmosféra ako to už mnohí spomínajú je príjemná. Od skúšajúceho závisí do akej miery vrtá v tom čo ste povedali resp. to čo tam chce počuť ale stále platí ak máte základ a úkážete aspoň drobnú mieru pochopenia problematiky tak to prejde.

Z toho čo som videl mi príde, že to čo spomínaju kolegovia predo mnou tak je silne prehnané, že musíte vedieť dôkazy a podobne, skôr som sa stretol s tým, že dôkazy vyslovene nechcú. Samozrejme závisí od otázky ak je tam čo hovoriť tak dôkazy nie sú potrebné ale napr. pri takej vete o rekurzi by asi nejaký náznak dôkazu potrebný bol, keďže tam nie je čo povedať. Organizácia skúšania bola veľmi zaujímavá, každý skúšajúci aj skúšaný mali rozpis s časmi, kedy budú skúšaný z ktorých otázok a v podstate sa ten harmonogram aj dodržiaval. Času na prípravu bolo podľa mňa viac než dosť a tak som tam pomerne dlho znudene posedával a čakal kedy sa dostaví skúšajúci.

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

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

• definice RM, RSM vč. definice ORF a ČRF (s drobnou chybou – dal jsem dohromady prvky a operátory nad funkcemi),

• generování (tři věty o oborech hodnot) (Tady se mě ptal, jak fungují ty programy pomocí kterých množiny generuji. Neměl jsem to rozmyšlené, takže to ze mě musel tahat a část říct),

• 1-převoditelnost, 1-úplnost, K je 1-úplná. Ptal se mě, k čemu ta 1-převoditelnost je. Dával mi návodné otázky a potom jsem si končeně vzpomněl, že asi myslí to, že můžu převést jednu množinu na druhou. Jen tak mimochodem se ptal, kolik je RM a kolik RSM.

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

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

• co je BVS (měl jsem tam chybu v podmínce),

• co je vyvážený strom a ústně jsem na jeho dotaz doplnil, že jeho hloubka je $O(\log n)$,

• definici AVL a Č-Č (u Č-Č jsem měl i nějaký odhad hloubky, ale Koubek vypadal, že si ho ani nevšiml),

• základní algoritmy – jen slovně a občas jsem tam měl drobnou chybku (např. jsem předpokládal, že vrchol má při odstraňování jednoho syna, ale on to mohl být i list),

• na příkladu AVL jsem se snažil popsat vyvažování. Neměl jsem to připravené, ale Koubek ty operace stejně přesně nechtěl. Spíš chtěl, abych mu řekl, že při vyvažování se nejen upravuje strom, ale také mění ta hodnota o vyvážení uložená ve vrcholech.

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

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

• že je to na datové modelování (chtěla to zařadit do takové té hierarchie fyzická, logická, ???, to jsem nevěděl, ale moc jí to nechybělo,

• z čeho se může ER-schéma skládat (ptala se mě, co znamenají kardinality, tak jsem jí to řekl, chtěla příklad, dal jsem jí ho, ona se zeptala, jestli mám kardinality na správných stranách, znovu jsem provedl úvahy o tom, jak to měl Skopal na slajdech, řekl jsem jí, že to mám správně a ona řekla, že to každý píše stejně jinak :-D),

• co je to relační model – to jsem neznal formálně, tak jsem to tam napsal slovně a ona to chtěla formalizovat, tak jsem řekl že tabulka je název a n-tice, ona ze mě tahala nějaké pojmy, ale ty jsme nevěděl, pak se mě zeptala, jak se jmenuje ta operace se sloupci, když potřebuji doménu hodnot, vůbec jsem nechápal, co po mně chce a ona po mě chtěla „kartézský součin“ :-).

• Jak se to převádí – entity na tabulky atd. Hlavně ji zajímaly kardinality, kde jsme došli k tomu, že se to dá převést všechno na jednu tabulku a může tam dojít k duplicitám.

• normální formy – kdybych to tam prý nenapsal, tak by se na to neptala, ale když už jsem to tam měl, tak to zkontrolovala a chtěla po mě příklad porušení a jak to opravím. Tak jsem jí ho dal.

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

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

• Co to je a k čemu to je.

• výhody, nevýhody,

• základní algoritmy a jejich vlastnosti

  • počítání referenci

  • zjišťování dostupnosti

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

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

• Co je to model-checking.

• Trochu jsem popsal Kripkeho strukturu.

• Popsal jsem, jak vypadají CTL.

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

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

28.1. 2013

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

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

Hladík (DS) -- Fibonacciho haldy. ::

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

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

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

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

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

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

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

11.9. 2012

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

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

Yaghob (MSS) -- Paralelni programovani a lockless algoritmy ::

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

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

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

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

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

Obdrzalek (OOKS) -- Diamond problem ::

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

Koubkova(DS) -- Haldy ::

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

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

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

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

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

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

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

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

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

11.9.2012

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

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

2. Programovací jazyky a překladače - Bednárek - LR automaty

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

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

4. Architektura počítačů a sítí - Peterka - Topologie sítí, přístupové metody

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

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

Dohromady jsem dostal za 1. Takže spokojenost.

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

Tak hodně zdaru!

11.9.2012

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

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

2. Složitost a vyčíslitelnost - Čepek (příseděl Koubek a Dvořák) - Úplné problémy pro třídu NP, Cook-Levinova věta.

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

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

4. Operační systémy - Hnětynka - Synchronizace

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

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

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

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

Definice- alfa a omega, většina zkoušejích na nich těžce lpí. Je vám na hovno, pokud umíte dokázat větu o 4 barvách, pokud neumíte definovat graf. Typicky se od nich začíná a pokud problém PŘESNĚ nedefinujete, nedostanete se k ničemu dalšímů, odejdete s nepořízenou a nikoho nebude zajímat, že zbytek otázky umíte. Osobní zkušenost (minule definice sekvenčního protokolu pro distribuovanou komunikaci a dneska málem NP-úplnost) + dneska kolega dopadle stejně (něco s pseudopolynomiálními algoritmy) a pár dalších z nás mělo namále.

Důkazy - většinou stačí hlavní myšlenka, krom těch zásadních a snadných (Halting problém apod.).
Dobré zdroje na učení:

    wiki.matfyz.cz - jako přehled, chybí detaily a dost neudržované
    S0cketčiny zápisky (viewtopic.php?f=419&t=6620 - aktuální umístění se občas mění) - jsou obří, ale je tam skoro všechno ze Systémových architektur, hezky popsáno

    Poznámky od Vládi Bedecsa - (viewtopic.php?f=419&t=6667) - spíše pro softwarové inženýrství (obsahuje Architekturu počítačů a síti), pěkne sesumírované
    Kučerovy poznámky (http://ktiml.mff.cuni.cz/~kucerap/NTIN0 ... znamky.pdf) - bible složistosti a vyčíslitelnosti, občas možná moc ukecané, ale jinak super

    Proslulé Peterkovo kino (http://www.earchiv.cz/i_prednasky.php3) - je tam skoro všechno o sítích, super jako přehled, občas to chce dohledat detaily jinde (IPSec, IPv6, certifikáty,...)
    Přednáška na MIT o univerzálním a perfektním hašování (http://videolectures.net/mit6046jf05_leiserson_lec08/) - odkaz šlohnut z wiki, super na pochopení, ale dost jiné, než co přednáší Koubek. Na druhou stranu, těch přednášek tam je hromada i na jiná témata, stačí hledat.

    A.S.Tanenebaum - Modern Operating Systems, 3rd edition (http://www.amazon.com/Modern-Operating- ... 0136006639) - na Amazonu za lidových $116, v knihovně gratis (nevím které vydání)...no, a kdo hledá, ten najde. Naprosto zásádní dílo, co se OSů týče. Extrémně ukecané, ale i extrémně čtivé. Nevynechá snad žádné téma v OSech (vč. obskurností jako virtuální stroje) a pokrývá i nemalou část z Architektur počítačů a síti. Více jak 1000 stran není málo, ale pro potřeby státnic se dá zredukovat cca na polovinu. Pan Vánoční Stromeček prostě umí psát... :) 

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

11.9.2012

Dnes jsem absolvoval statnice z pocitacove grafiky: Otazky:

1)Binarne vyvazene stromy: Rekl jsem definici AVL, RB, BB(alpha), dukaz hloubky AVL a nakonec par operaci nad AVL stromy.

AVL jsem si vybral dobrovolne, mohl jsem rikat vic i o RB. Bohuzel nevim zkousejici :( Byla to nejaka postarsi hodna pani :) Na nic moc se neptala a byla spokejena

2)NP-Uplne problemy

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

A ted grafika, tam me prekvapili zkousejici: Wilkie, Skopal (!!!! ten co uci normalne databaze)

3)Monte-Carlo methods Zkousel me Wilkie, takze to probihalo v anglictine :) Byl celkem v pohode, jen me zarazili nektere otazky na quasi monte-carlo.

4)De Casteljaův a de Boorův algoritmus

To hlavne zajimalo Skopala, ale povidal jsem v anglictine, aby tomu rozumel i Wilkie. Skopal byl uplne v pohode, v zadnych detailech se nerypal.

5)Standardy MPEG a JPEG

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

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

6.2.2012

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

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

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

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

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

Grafika

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

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

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

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

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

6.2.2012

Ja sem dostal nasledujici otazky

1. Algoritmicky nerozhodnutelne problemy

Zacal sem Church-Turingovou tezi a pojem algoritmus vztahl k TS. Pak sem zadefinoval Rekurzivne spocetne a rekurzivni jazyky. Halting problem, Diagonalni jazyk, Univerzalni jazyk, Postova veta. Pak sem presel od TS k CRF tady sem jako priklad uvedl K a K0, definoval CRF a ORF + intuitivni srovnani s TS U vetsiny veci sem mel i dukazy ( vycislitelnosti sem se bal nejvic z okruhu takze sem to mel celkem nadrceny ). Pak se dvorak ptal jak zjistim ze nejakekj problem je nerozhodnutelny ( aniz by clovek musel furt vymyslet specialni dukazy ) to sem chvili vahal ale pak sem si vzpomel na prevoditelnost Rekurzivnich a rekurzivne spocetnych mnozin pomoci prevodni fce ktera musi byt ORF coz se ukazalo jako spravna odpoved.

Posledni sada otazek uz smerovala k tomu co se bude dit kdyz budu mit TS s orakulem, jestli potom budou vsechny problemy budou rozhodnutelne...tady sem nevedel, odpovidal sem hodne diplomaticky ( spravna odpoved je TS s 1 orakulem umi resit nejaky problemy, TS s 2 orakulama umi resit jeste vic problemu atd...ale nikdy nelze pokryt vsechny jazyky ) Jeste dodam ze tohle nakonec Dvorak okomentoval slovy ze je to spis takova zajimavost, nic zasadniho pro statnice.

2. B-stromy Napsal sem definici, dukaz logaritmicke vysky ( hrde sem to nazval Veta o logaritmicke vysce Bstromy coz dvorak s usmevem okomentoval ze je to spis takove trivialni pozorovanicko :D )

Pak sem popsal insert a delete. Pak se ptal nato jestli se da insert udelat v jednom pruchodu ( tzn ne ze prvek zatridim a pak vstoupam vzhuru a provadim stepeni preplnenych uzlu...spravna odpoved je delat dopredne stepeni ( kdyz jdu dolu tak plne uzly preventivne rozstepim abych tam mel misto cimz amortizovane zlepsuju slozitost ) Potom A-sort, Redundantni B-stromy, B*-stromy ( tohle vsechno jen v rychlosti...proste chtel vedet ze vim jaka je tam myslenka )

3. Metody odstranovani sumu (Digitalni zpracovani obrazu)

Tohle zkousel Pelikan, Zara jen sedel vedela pozoroval. Popsal sem kratce modely sumu ( Gamma, Exp, Gauss, Impulzni )

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

4. Interkativita ve VRML Tady to prevzal Zara ( bohuzel, Pelikan je imhho o dost mirnejsi, Zara v tom celkem rejpe )

Senzory, Manipulatory, EventIn, EventOut, Route To, Interpolatory. Pak se ptal na strukturu uzlu Collision (chtel vedet jaky atributy tam jsou a jak se pouzivaji...tady sem zacinal tapat protoze do takovych detailu sem to neumel.

Posledni otazka jak ve vrml implementovat teleportaci avatara kdyz se stiskne napriklad tlacitko ...to sem navrhl par moznosti, zadna se mu prilis nelibila ( respektiva zadna by pry nebyla realizovatelna ve VRML ) Spravna odpoved byl udajne uzel Anchor.

Tim to nastesti skoncilo ( mam pocit ze cim dyl by se ptal tim horsi celkovej dojem bych zanechal :D )

5. Komprese PNG a GIF Nejhorsi otazku sem si nechal na konec...tuhle sem absolutne nemel pripravenou, navic ji zkousel Zara

Snazil sem se co nejdyl mluvit o obecnych metodach komprese obrazu ( RLE, Huffman, LZ77, LZW, Aritmeticke kodovani, Transformace obrazu ) ...to me ale Zara brzo zarazil ze to moc nesouvisi s tim na co se me ptaji at zacnu byt konretnejsi

Tak sem otocil papir a tam sem mel par strohych poznamek o PNG a GIF formatech Kdyz sem to zacal komentovat tak me Zara prerusil at je spis vzajemne porovnam kdyz o nich mluvim.

Co konkretne ho zajimalo: oba bezeztratove, LZ77 vs LZW, ze oba pouzivaji progresivni metodu zobrazeni, Proc muze mit PNG lepsi kompresni pomer nez GIF kdyz GIF pouziva modernejsi LZW oproti LZ77 ( odpoved ze LZ77 muze byt lepsi nez LZW na nekterych vstupech protoze je to uplne neco jinyho se mu moc nelibila...spravna odpoved je podle Zary ze tam je lepsi prediktor)

No casto sem tady tipoval, hodne sem toho nevedel, parkrat me Zara poucil jak ze to vlastne je...celkem bida, ale mel sem pocit ze k vyhazovu sem mel jeste furt nejakou rezervu

12. a 13. 9. 2011

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

1. Zlozitost a vycislitelnost -- Dr. Kryl

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

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

a nasledna cast bude asi pre ostatnych menej uzitocna

3. Obecna lingv -- FGD -- Dr. Kubon

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

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

5. Strojovy preklad -- Dr. Zeman

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

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

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

12. a 13. 9. 2011

Koubek (slozitost a vycislitelnost) - Cook-Levinova veta ::

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

Majerech (DS) - binarni stromy, vyvazovani ::

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

Kofron (OCS) - model checking ::

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

Obdrzalek (OSY) - sprava pameti ::

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

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

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

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

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

Koubek (DS) - reseni kolizi v hashovani ::

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

Yaghob (prekladace) - LL analyza ::

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

Bures (OCS) - prototypy a klony ::

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

Kofron (ANSS) - informacni bezpecnost ::

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

2. 2. 2011

Obecne: Je toho daleko vic, nez se na prvni pohled zda. Ucil jsem se mesic (prvni 3 tydny tak 4-5hodin denne, posledni tyden i 12hod denne) a nemel jsem pocit, ze uz to lepsi byt nemuze :-)

Celkove nas bylo tusim 24, z toho 7 si to bohuzel bude muset zopakovat. Byli jsme rozdeleni do tri skupin. Kazdy dostal behem prvnich cca 10min vsechny otazky a mel dane poradi, ve kterem je ma vypracovavat a take inicialy zkousejicich, ktere uz potkal pri zadani otazek, clovek tedy tusil na co se ma tesit :-) Zacinalo se neco po devate a z mistnosti jsem odchazel kolem pul druhe, a to jsem celou dobu bud psal odpoved, nebo diskutoval se zkousejicim. Ke konci toho ma uz clovek fakt dost.

Otazky:

1. Distribuovane systemy: Jmeno zkousejici bohuzel nevim, videl jsem ho snad prvne [asi pan Konfron]:-) Dal mi: distribuovane vylouceni, volba koordinatora, konsenzus a detekce glob. stavu.

Toto jsem nastesti docela umel, takze jsem popsal 3A4 nez prisel. Otazka byla u konsenzu kdo je to tedy ten general (koordinator) a jak mam zarucene, ze konzistentni rez bude "dobry" glob. stav. neco jsem rekl, s cimz byl spokojen a dal me netrapil. Znamka: 1

2. Architektura siti a pocitacu

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

Znamka: 1-

3. OSy Bulej, synchronizacni primitiva:

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

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

4. Vycislitelnost/Slozitost

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

Znamka: 1

5. Datovky Kopecky, Haldy a trie

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

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

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

2. 2. 2011

1. Programovaci jazyky a prekladace: LL-analyza (Bednarek)

Napisal som o co ide, popisal lavu rekurziu a lavu faktorizaciu, zadefinoval FIRST a FOLLOW a potom obe metody na implementaciu z Yaghobovych slidov: rekurzivni sestup a nerekurzivni analyza s predikci.

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

3. Slozitost a vycislitelnost: NP-uplnost (meno neviem, inicialy ML)

Zacal som definiciou Turingovho stoja a postupne som definoval vsetko az po NP-uplnost, dokazal kachlikovani, prave ked som pisal prevod KACHL->SAT tak prisiel skusajuci, pozrel sa na to vsetko a povedal ze to staci.

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

5. Datove struktury: Hasovani (meno neviem, inicialy PK)

Na 2 A4 som spravil prehlad (strucny popis + pripadny obrazok) vsetkych metod co som vedel vratane externych hasovani, univerzalneho a perfektneho hasovani a dostal som par lahkych doplnujucich otazok.

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

2. 2. 2011

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

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

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

2. Datovky - Triedenia na vonkajsej a vnutornej pamati (Kopecky + Mares)

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

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

4. ANSS - XML, XML schema, RDF (Bednarek + Tuma)

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

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

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

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

2. 2. 2011

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

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

A ted vlastni otazky:

APS (nejaky mlady zaskok za nemocneho Peterku) - TCP/IP

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

DS (Tuma) - RPC

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

OS (Bulej) - Virtualni pamet, strankovani

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

Datovky (P. Kucera) - Trie

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

Vycislitelnost (Loebl) - Ekvivalence ruznych definic algoritmicky vycislitelnych funkci

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

26. 5. 2010

Surynek - ČRF ::

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

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

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

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

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

Bulej - virtualni stroje ::

:: Obecny prehled, shadow PT, virtualizace diskoveho zarizeni.

Hnětynka - Middleware ::

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

Peterka - detaily 802.11 ::

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

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

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

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

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

Yaghob - Mezikód. ::

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

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

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

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

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

Zavoral - algoritmy virtualni synchronie ::

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

Koubkova - haldy ::

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

Slozitost - pseudopolynomialni algoritmy ::

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

9. 2. 2010

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

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

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

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

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

9. 2. 2010

Bulej - Virtuální stroj (Osy) ::

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

Peterka - Emaily (SMTP, POP) ::

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

Löebl (AVL, CC stromy) ::

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

Zavoral (Distribuovaný konsenzus) ::

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

9. 2. 2010

Tak pridam i svuj postreh. Ja mel tyhle otazky

pametova hierarchie(OSY) - zkousel Kofron, byl pomerne v pohode, kdyz clovek vysypal dostatek znalosti, tak do toho ani moc nestoural, za 1 volaci konvence, aktivacni zaznam atd (Prekladace) - zkousel Zemlicka a to co sem vedel celkem presel a stroural do veci co sem az tolik nevedel (aktivacni zaznam)..nakonec 2-3

Komponentove systemy (OOKS) - zkousel nedo mladsi z DSRG jmeno nevim, ukazal sem tak obecny prehled, rekl o COM, DBUS, naznacil CORBu, EJB a potom neco vic o SOFA...nejzaludnejsi asi byla otazka kdy jsou komponentove systemy lepsi nez objektove...celkove se moc nezajimal o COM a DBUS u kterejch sem vedel nejvic a chtel spis ty vic advanced systemy..znamka 2-3 CRF(slozistost/vycislitelnost) - napsal sem v lidske reci vsechny zakladni funkce a operatory, co je odvozeni, popsal co je PRF, ORF, CRF a napsal inkluze a dokazal pres Ackermana inkluzi mezi PRF a ORF...dotaz znel na mnoziny, tak sem otocil co je rekurzivni a rekurzivne spocetna...celkem v Pohode zkouska, zkousel Fiala znamka 1-2

Binarni stromy - zkousel Kratochvil..napsal sem co jsou binarni stromy, jak muzou zdegenerovat, jak vypada idealne vyvazeny binarni strom, popsat CC-stromy a AVL stromy, otazky byli ohledne slozitosti, jestli muzou rotace eskalovat a slozitost insert/delete...znamka 1

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

9. 2. 2010

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

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

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

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

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

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

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

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

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

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

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

9.9.2009

Čepek - Haldy (okruh Datové struktury) ::

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

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

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

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

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

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

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

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

:: Co je to zpráva, jak vypadá, že se ztrácí, co s tím :: RPC - co je IDL, jestli to jde i bez toho, co se generuje (stub, skeleton (přilinkování) a headry (includovani) pro klienta a server), transparentnost - globalni promenne, pointery, objekty v RPC (jsou na serveru, klient má proxy, kde se vezme? naming služba. Kde běží? Jak se tam vezmou reference na objekty?) :: Threading model serveru. Podle čeho poznám kolik vláken má mít Thread pool? (podle workloadu - 1) processor-intensive = cca tolik vláken kolik procesorů 2) hodně s diskem a čekání = trochu víc), jak se liší použití RPC a messagingu (synchronnost, one-to-many u messagingu), JMS, může si každý naimplementovat svojí name service?

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

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

Matoušek - NP-úplnost ::

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

Peterka - Přístupové metody ::

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

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

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

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

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

28.5.2008

Zavoral - distribuovaný konsenzus ::

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

Yaghob - podpora multiprocesoru v OS ::

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

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

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

Zemlicka - trideni ve vnitrni pameti ::

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

Jakysi mily teoretik - savitchova veta ::

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

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

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

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

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

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

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

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

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

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

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

18.9.2008

Hnětynka - distribuované objekty ::

:: Napsal jsem krátký obecný kec, CORBA IDL, mapování do jazyků, pár problémů s nimi, POA, znínil pár jejich policy, stručně popsal Naming Service, zmínil Trading Service, v bodech popsal Java RMI. Hnětynka si to přečetl a pak se ptal na nějaké další "vychytávky": * dynamic invocation * zda se objekt vždy úspěšně zaserializuje * jak funguje Naming Service, kde se vezme reference na něj * zda se v RMI generují stuby a skeletony, (a nějaké další) :: Z těch doplnujících otázek jsem věděl (či uhodl) tak každou třetí, známka: 2 - 3 (asi)

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

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