Statnice 2.2. - zkusenosti

[Jirka Horky]

Ahoj,

rikal jsem si, ze by se mozna hodili zkusenosti ze zimniho terminu statnic, zvidave otazky vyucujicich k jednotlivym oborum a tak. Mne v zaverecne priprave docela dost pomohlo.

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.

Toz hodne zdaru vsem, ktere to jeste ceka!
Jirka Horky

[ondrisko]

Zdravim,

pripajam aj svoje otazky:

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.

Vela stastia dalsim!

[qwyxyo]

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.

Drzim vam vsetkym prsty!

[Keleen]

Ahoj,

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

Hodne stesti vsem, ktere to jeste ceka.