Mgr. SS 30.5.2012

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

Mgr. SS 30.5.2012

Příspěvek od _flavius »

Dneska to vypadalo docela kruté, asi půlku vyhodili. Já jsem byl z těch šťastnějších, dostal jsem tohle:

Obdržálek: Memory management, čili segmentace, stránkování etc... Myslím, že to docela umím, ale dusil mě na detailech, jako že prvních x bitů virtuální adresy není index do VT, ale je to *číslo stránky*, které se pak náááhodou použije jako index do VT, a ve VT není fyzická adresa rámce, ale číslo fyzického rámce, které se náááhodou použije po nějakém shiftu jako fyzická adresa... Ale nakonec v pohodě.

Král: NP, NP-úplnost, příklady... Trochu jsem se zamotal do toho, jestli je třeba, aby se NTS zastavil po polynomiálním počtu kroků (v první chvíli jsem myslel, že ne a že když to bude třeba, tak že NTS = DTS, ale to je blbost - třeba to sice není, ale pokud tak tu definici dáme, tak se nic nezmění). Byl hodný.

Žemlička: Haldy. Popsal jsem binární (s tím, že je tom jenom jednoduchý případ d-regulární), binomiální, a Fibonacciho, u Fibonacciho jsem si nebyl jistý, jak se počítá amortizovaná složitost, protože mi vycházelo, že by mohla být konstantní, ale Žemličkovi se to nechtělo moc řešit, tak se mě zeptal, kdy bych kterou haldu použil a jaké mají prostorové náročnosti a byl spokojený.

Bulej: Synchronizační primitiva, spinlock, producent-konzument se semafory. Pohodka.

Hnětynka: Distribuované FS. Popsal jsem NFS, Sambu (tu se mu nechtělo ani číst :-)) a AFS, nejdříve se doptával na idempotenci NFS a jestli se něco dělá u open (jenom se ověří, že soubor existuje), pak se chtěl doptávat na CODA či co, o tom jsem ani nepředstíral, že něco vím - byl z toho trochu smutný, ale nedělal z toho problém.
Xenik

Re: Mgr. SS 30.5.2012

Příspěvek od Xenik »

U nás dopadli všichni dobře, 3 databázisti (každý jeden předmět změněný) jsme byli a byl tam i jeden z distr systémů myslím. Každopádně moje otázky byly:

Umělá inteligence - A* algoritmus
Datovky - Hashování, řešení kolizí, srovnání metod
Složitost & Vyčíslitelnost - Pseudopolynomiální algoritmy
Databáze 1. okruh - Relační úplnost
Databáze 2. okruh - Implementace operací relační algebry (JOIN)
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Mgr. SS 30.5.2012

Příspěvek od Osiris »

Já jsem měl všechny tři výběrové okruhy z databází (+ ty dva společné). Dostal jsem následující otázky:

1) Algoritmicky nerozhodnutelné problémy
Napsal jsem Halting problém + ten jednoduchý důkaz. Dále jsem napsal Riceovu větu a jak souvisí s halting problémem. Nakonec jsem napsal Postův korespondenční problém. To zkoušejícímu stačilo a nebyly žádné další otázky.

2) Třídění ve vnitřní a vnější paměti
Napsal jsem dva algoritmy třídění ve vnitřní paměti - QuickSort a MergeSort. U obou jsem dokázal časovou složitost ( u QuickSortu v průměrném případě). Dále jsem popsal externí mergesort + jak se vyrábějí běhy pomocí dvojité haldy. Úplně nakonec jsem popsal a dokázal dolní odhad časové složitosti třídění pomocí porovnávání. Zkoušející se zeptal jenom na třídění bez porovnávání - řekl jsem CountSort se zmínkou o složitosti a to mu stačilo.

3) Věta o tranzitivním uzávěru relace
Napsal jsem definici tranzitivního uzávěru, znění věty a důkaz podle slidů prof. Pokorného. Až na drobnou chybu v definici tranzitivního úzávěru, kterou jsem opravil, to stačilo.

4) Booleovský a vektorový model
Slovy jsem popsal oba modely. U Booleovského jsem popsal, jak se indexuje, jak se vybírají termy a jak vypadají dotazy. Zmínil jsem se o složitosti počítání relevance. Dále jsem popsal vektorový model, jak vypadají dotazy apod. Zmínil jsem se, jak se počítá TF a ITF. Zkoušející se jen zeptal na pár otázek a byl spokojen.

5) R-stromy
Napsal jsem, k čemu jsou dobré, definici a štěpení uzlů dle Guttmana a Greeneové. Dále jsem se zmínil o některých variantách R stromů. Zkoušející se pak jen zeptali na pár otázek.

Z ústní jsem měl 1, z diplomky 3 \Rightarrow celková známka 2. Řekl bych, že nejde o těžkou zkoušku, ale je potřeba se dobře připravit a hlavně netápat v jednoduchostech. Učil jsem se přes šest týdnů a domnívám se, že je to až moc. Přeji hodně štěstí těm, které to ještě čeká!
Osiris
Odpovědět

Zpět na „Magisterské SZZ“