Softwarové systémy 17.9.2018

Vše o státnicích úspěšně završujících roky studia na naší alma mater.
Katami
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 3. 2. 2014 13:40
Typ studia: Informatika Ph.D.

Softwarové systémy 17.9.2018

Příspěvek od Katami »

Formát velmi podobný tomu v létě. Nebyly k dispozici (tedy nám ne a na katedře jsem si také nevšiml) zmíněné desky s informacemi o studentech. Bylo nás 10 studentů (3 různé obory) a 13 členů komise (zkoušejících).

Zkoušející mají interní rozvrh, podle kterého na začátku zadají otázky. Více méně v náhodném pořadí dostanete otázky, které si máte připravit na 9:45, 10:30, 11:15, 12:00 a 12:45. První zkoušení začíná v 9:45, pak už je to dost náhodné, podle toho jak máte vy a zkoušející čas. Možná bych jenom poznamenal, že pokud má zkoušející čas, a je takového typu, tak si s vámi bude klidně povídat hodinu :-). Pořadí otázek je skutečně náhodné.

Formát jednotlivého zkoušení je v režii zkoušejícího. Zpravidla se dívá do vaší přípravy a buď jí čte nebo po vás chce, abyste mu o tom povídali. Zkouška je spíše do široka, než do hloubky. Sami si můžete udělat obrázek o tom, kolik je toho třeba říct/napsat z informací zde, nebo v jiných vláknech. Někteří zkoušející již při zadání otázky řekli, na co bychom se měli zaměřit, jiní jen sdělili téma.

1. Datové struktury: Splay stromy (Vladan Majerech)
Řekl jsem motivaci (manipulace s podmnožinou prvků v BST), přístup k řešení (offline - staticky opt. strom ; online - právě splay stromy), ukázal jsem co to je Splay (zig, zig-zig, zig-zag) a kde se to v tom stromě používá. Oznámil jsem, že se dá ukázat, že splay má amortizovaně logaritmickou složitost, vzhledem k velikosti podmnožiny.

~Průběh zkoušky:
Zk: Jaké jsou operace v BST
Já: find, insert, delete
Zk: Tak strukturu s takovým interfacem bych si od vás nekoupil, nemáte tam ještě něco?
Já: ? (pak po dlouhé diskusi obecně o stromech a datových strukturách a směrování ke správné odpovědi)
Já: prvek.next()
Zk: Super, škoda, že se to neinzeruje i na přednášce
...
Zk: Kdybych vás mučil, řeknete mi myšlenku důkazu analýzu složitosti.
Já: Mučit mě nemusíte (a jen slovně jsem naznačil, že uděláme analýzu jednotlivých rotací, pak analýzu i kroků a že se to tam někde teleskopicky odečte)
Zk: Tak nějak
...
Zk: Proč se (v zig-zig stepu) tahle rotace dělá tak divně?
Já: Abych se přiznal, tak přesně nevím, ale existuje na to protipříklad, kde se to rozbije
(Zk se mi snažil vysvětlit proč a pak odešel, spokojen s mým výkonem)

2. Základy složitosti a vyčíslitelnosti - Algoritmicky nerozhodnutelné problémy (Martin Klazar)
Připoměl jsem značení pro zastavení se nad vstupem, zacyklení se, řekl jsem něco o univerzálním TS a jazyku, pak o převoditelnosti s vlastnostmi, pak ukázal co to je HALT a že je částečně rozhodnutelný, pak převod Lu <= HALT a z toho implikaci, že HALT je nerozhodnutelný.

Zkoušející se mě ptal, jestli znám ještě nějaké další nerozhodnutelné problémy, tak jsem mu řekl, že třeba ten Lu, nebo DIAG a pak ukázal, že existují jazyky, které nejsou ani částečně rozhodnutelné, tudíž ani rozhodnutelné. Zajímal se, jestli neznám nějaký příklad z teorie čísel. Nevzpomněl jsem si na Diofantické rovnice (má polynom celočíselné kořeny?).

3. Systémové aspekty počítačů (Pavel Ježek) - Je objektový návrh aplikací vhodný pro high-performance výpočty?
Ukázal jsem, že procházení pole a procházení spojového seznamu je jiná věc a proč (cache, prefetcher), řekl jsem, že pokud máme pole tříd, tak může být výhodnější reprezentace jako třída polí (tedy vlastně layout v paměti transponujeme, kdo chodil na High-Perf computing od Bednárka, tak ví) a naznačil jsem, že se tam může podařit využít vektorové instrukce.

Zkoušejicí se mě ptal co to je ten prefetcher a co to jsou ty vektorové instrukce, pak mi dal příklad

abstract class Entity { abstract void update(); }
class Wolf : Entity { ... }
class Bear : Entity { ... }

a ptal se jestli to je efektivní. Řekl jsem že ne kvůli dispatchi virtuálních funkcí a řekl, že se to dá zlepšit tak, že si první uložíme Vlky a pak medvědy. Zkoušející se pak ptal na nějaké drobnosti a spokojen odešel.

4. Paralelní a distribuované systémy - Kauzalita zpráv (doručování + jak to funguje u překrývajících se skupin; Martin Kruliš)
Popsal jsem k čemu to je a že se to řeší vektorovýma hodinama, popsal jsem co to jsou logické hodiny a jak se používají ty vektorové. Řekl jsem, že u skupin se to řeší vektorem vektorových hodin (maticové hodiny), ale algoritmus jsem nepopisoval.

Zkoušející se dost vrtal v tom co to jsou ty logické hodiny a proč nejdou použít fyzické, pak chtěl detailně vysvětlit ten algoritmus + jednoduchý příklad (dal jsem to, co je na slidech z přednášky k PDS). Ptal se jak se to řeší u těch skupin, řekl jsem že nevím. Pak se ptal co to jsou Lamportovy hodiny a jak se od vektorových liší (chyták, je to to samé). Pak říkal, že je škoda, že jsem nevěděl ty skupiny, ale jinak OK.

5. Moderní koncepty programování - Aspekty (Petr Hnětynka)
Popsal jsem co to jsou ty apsekty, proč se to používá a kde se to používá (logování, cache), ukázal takový pseudo-example z AspectJ. Popsal jsem jak je to implementované (instrumetace/weaving)

Se zkoušejícím jsme se více méně bavili o detailech a dalších možnostech použití (transakce u enterprise systémů jsem nevěděl, ale vymyslel).
Odpovědět

Zpět na „Magisterské SZZ“