Softwarove systemy 2.7.2020

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

Softwarove systemy 2.7.2020

Příspěvek od kolko »

Tentokrat bol trochu iny format: na zaciatku kazdy (bolo nas 7 na termine) dostal vsetkych 5 otazok naraz. Skusajuci si jeden po druhom behom prvych 5 minut prisadli a kazdy zadal jednu az dve otazky podla dopredu pripraveneho priradenia skusajuci-otazka-skusany. Kazdy skusajuci mal vytlacenu karolinku s poziadavkami, spytal sa na zameranie a potom si vybral temu z poziadaviek.

Nasledne sme mali 2 hodiny na vypracovanie odpovedi vsetkych 5 otazok (zmena formatu oproti poslednym statniciam, predpokladam ze kvoli korone). Potom sme museli polozit pera a po jednom nas volali pred 4 clennu komisiu pozostavajucu z ludi ktori mi zadali otazku. Boli 2 taketo 4 clenne komisie, kazda skusala 3-4 ludi.

Pocas skusania komisiou som najskor rozdistribuoval svoje pripravene odpovede prisluchajucim skusajucim, kazdy si precital co som napisal a popripade sa dopytal co ho zaujimalo

Mal som zameranie Vykonne systemy. Moje otazky:
1. [Petr Kucera] Haldy, zamerat sa na binomialne
Popisal som co je to halda, ze existuju d-regularne, binomialne, fibbonacciho. Popisal som strukturu binomialnej haldy, ako sa robia operacie, napisal som ich casove zlozitosti. Potom som popisal linou binomialnu haldu, aky je rozdiel. Skusajuci sa pytal na najhorsie a amortizovane zlozitosti operacii, najma preto, ze som to tam nemal napisane velmi prehladne. Viac do hlbky sa pytal ako presne sa robia jednotlive operacie, padla aj otazka co je amortizovana zlozitost a naznak dokazu ze insert ma amortizovanu zlozitost log n. Spomenul som len paralelu s binarnym citacom a skusajuci vyzeral spokojne.

2. [Petr Kucera] Algoritmicky nerozhodnutelné problémy (halting problem)
Popisal som turingov stroj, a (ciastocnu) rozhodnutelnost. Definoval som halting problem a pokusil sa o naznak dokazu. Skusajuci so mnou presiel ten dokaz a zistili sme ze argumentaciu dokazu nepoznam :cry:. Isli sme teda dalej, pytal sa na nejake prakticke problemy. Tu som spravil chybu, ked som spomenul Riceovu vetu, ale nerozumel som jej az tak dobre :D. Snazil sa ma na to naviest, ale vobec mi to neslo, navela sme sa k tomu aspon priblizili. Na konci sa opytal poslednu otazku, ze ako by som dokazal o nejakom probleme ze je nerozhodnutelny (pomocou prevoditelnosti, nie z definicie). To som nastastie vedel, asi sa chcel uistit ze aspon na trojku tomu rozumiem.

3. [Kopecky] Distribuované systémy (VS) - Komunikace a koordinace v distribuovanom prostredi.
Tu som si vobec nebol isty co vlastne ta tema pokryva... Ku komunikacii som napisal co je to distribuovany system (zo slajdov PDS), ze pocitace si posielaju spravy a popisal som ako funguje RPC. SKusajuci sa pytal co je to ta sprava, povedal som ze je to informacia ktoru jeden pocitac posiela druhemu. To sa mu nepacilo, tak som sa opravil ze si to posielaju procesy. Pytal sa ci je nejaky rozdiel medzi tym ked komunikuju 2 procesy na tom istom pocitaci a na rozdielnych pocitacoch.

Ku koordinacii som popisal co je to koordinator/leader a uviedol som bully algoritmus a jeden z kruhovych algoritmov. Skusajuci sa pytal co je to vlastne ta koordinacia, dostali sme sa k tomu ze je to dobre na kriticke sekcie, tak som popisal centralizovane riesenie (kazdy proces si od koordinatora pyta povolenie na vstup) ako najjednoduchsie riesenie a maekawa algoritmus.

4. Programování paralelních aplikací - paralelní řešení nehomogenních úloh [Yaghob]
Yaghob mi uz cez pocas zadavania povedal, ze je to co chce je load balancing. Popisal som task paralelizmus, ze potom potrebujeme scheduling, task stealing. Ku task stealingu sa pytal na problem toho ked vela threadov chce kradnut, ze to "kradnutie" zozerie viac vykonu ako samotna praca - thready budu hladat co by ukradli iba obcas. Pytal sa aj na to ako sa riesi ked mame nejake tasky, ale ich pocet nie je delitelny poctom threadov takze na konci by niektore thready nic nerobili - na konci mozme zmensit velkost tasku.

5. Systémové aspekty počítačů (VS) - Hierarchie paměti. [Krulis]
Nakreslil som architekturu moderneho pc, registre, cache, ram, cache associativity. Padli otazky co su to tie registre, a ako sa lisia od cachce, nespomenul som cache line. Potom sa pytal ci ta RAM ma tiez nejaku strukturu, spomenul som NUMA, rec bola aj o cache coherency - MESI protokol.

Celkovo za 2, ciastkove znamky nepoznam.
Odpovědět

Zpět na „Magisterské SZZ“