Statnice 11.9.2012

Vše o státnicích úspěšně završujících roky studia na naší alma mater.
Martas

Statnice 11.9.2012

Příspěvek od Martas »

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)
Kajinek
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 20. 12. 2007 22:24
Typ studia: Informatika Mgr.

Re: Statnice 11.9.2012

Příspěvek od Kajinek »

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 (http://forum.matfyz.info/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 - (http://forum.matfyz.info/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 :)
Naposledy upravil(a) Kajinek dne 13. 9. 2012 23:52, celkem upraveno 3 x.
jkt
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 14:02
Typ studia: Informatika Mgr.

Re: Statnice 11.9.2012

Příspěvek od jkt »

Otazky jsem popsal na http://wiki.matfyz.cz/index.php?title=S ... 11.9._2012. Par dojmu -- nedokazu rikat, ze by vysledna znamka vypovidala o znalostech konrektniho ex-studenta (rikam to z pozice cloveka, co dostal jednicku, nejde o urazenou hrdost), je to silne randomizovany proces. Bylo by jiste mozne, aby student musel kreslit rotace v AVL/RB stromech, ale to bych asi opravdu bezchybne neodvodil. Byly otazky, na kterych bych letel. A tak.
Jochanan
Matfyz(ák|ačka) level II
Příspěvky: 85
Registrován: 12. 5. 2007 15:58
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Statnice 11.9.2012

Příspěvek od Jochanan »

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!
qwertie
Matfyz(ák|ačka) level III
Příspěvky: 103
Registrován: 4. 6. 2005 15:49
Typ studia: Informatika Bc.
Bydliště: Vyšehrad

Re: Statnice 11.9.2012

Příspěvek od qwertie »

Otazky jsou na http://wiki.matfyz.cz/index.php?title=S ... 11.9._2012. Soubor s grafickymi vytahy se pokusim zverejnit tez..
Odpovědět

Zpět na „Magisterské SZZ“