I2 - Softwarové inženýrství - 16. 6. 2015

Vše o státnicích úspěšně završujících roky studia na naší alma mater.
Xerxes
Matfyz(ák|ačka) level I
Příspěvky: 37
Registrován: 23. 1. 2007 16:32
Typ studia: Informatika Bc.
Bydliště: Zlínský kraj / Kolej 17. listopadu
Kontaktovat uživatele:

I2 - Softwarové inženýrství - 16. 6. 2015

Příspěvek od Xerxes »

Tak se rozloučím se zdejším fórem svými otázkami u státnic:

1) Složitost a vyčíslitelnost: Algoritmická rozhodnutelnost (zkoušející mně neznámý). Popsal jsem halting problem, neformálně dokázal jeho nerozhodnutelnost (použitím intuitivních pojmů jako "program" a jeho "kód"), napsal formální definici halting problému coby jazyka a množiny, provedl formálnější důkaz, že ona množina (resp. její diagonála) není rekurzivní. Doplňující otázka na význam pojmů "rekurzivně spočetná množina" a "rekurzivní množina". Definoval jsem pro množiny a jazyky. Otázka, zda jsou i jiné nerozhodnutelné problémy. Napsal jsem Riceovu větu a popsal její důsledek pro obecnou rozhodnutelnost otázek ohledně algoritmů. Otázka, zda existují i nerozhodnutelné problémy, které se neptají přímo na vlastnosti algoritmů. Řekl jsem, že určitě ano, ale na žádný si nevzpomenu. Byl mi dán příklad takového problému, už si přesně nevzpomenu, šlo o cosi s existencí celočíselných kořenů nějaké rovnice.

2) Datové struktury: Třídění ve vnitřní a vnější paměti (zkoušející mně neznámý). Pohodová otázka. Přehledově jsem popsal všechny běžné algoritmy a jejich výhody a nevýhody. Stačilo ke spokojenosti zkoušejícího.

3) Formální základy softwarového inženýrství: Algebraické specifikace (Bednárek). Neformálně jsem popsal, co to je a k čemu to je, a ukázal na příkladu přirozených čísel a zásobníku. Diskuze nad možnostmi indikace chybového stavu (speciální zásobník "error" či poddruh "neprázdný zásobník"). Otázka na možnosti dokazování nad takovou specifikací, no moc jsem tomu nerozuměl, ale zkoušejícímu šlo o to, že některé ty operace se označí jako konstruktory a pak uvažujeme jedině hodnoty sestavené pomocí těchto konstruktorů a nad takto vymezenými hodnotami už lze odvozovat věci. Otázka, kde jsou algebraické specifikace nevhodné, řekl jsem, že pokud máme složitý globální stav, který se mění. Ještě chtěl slyšet, že nejsou vhodné pro modelování souběžných a časovaných procesů.

4) Analýza, návrh a management softwarových systémů: Validace, verifikace, testování (Kruliš). Volná rozprava na dané téma, včetně formální verifikace.

5) Vývoj softwarových systémů: Vývojová prostředí, nástroje pro ladění a testování výkonu, akceptační a produkční prostředí, distribuce a instalace SW (zkoušející mně neznámý). Volná rozprava na daná témata.

Známka za jedna, takže jsem byl spokojený. Své zkoušející jsem až na dva moc neznal, ale pohybovalo se mezi námi mnoho známých vyučujících a každý student měl svou unikátní permutaci zkoušejících.

Velmi děkuji ostatním za materiály (hlavně tento dokument, který posloužil jako osnova, a všechny materiály pohromadě a se zvýrazněním), hodně mi pomohly připravit se na státnice v šibeničním termínu 14 dnů, a to abych tak řekl "z nuly na sto", neboť jsem si již docela odvykl na učení a zkoušky. Pro informaci:

4 dny na Složitost a vyčíslitelnost (až na výjimky z vlastních výpisků)
4 dny na Datové struktury (až na výjimky z vlastních výpisků)
4 dny na zbylé 3 předměty (ale byly to hodně perné 4 dny v dost nouzovém režimu)
2 dny na opakování (ale ten první jsem si navíc musel připravit obhajobu diplomky a ten druhý ji absolvovat)

Prvních 12 dnů znamenalo tvorbu výpisků drobným písmem na listy A5 (celkem popsáno cca 70 listů), poslední 2 dny jejich opakované pročítání.

Byl to dost záhul, ale konec dobrý, všechno dobré.
rumburak

Re: I2 - Softwarové inženýrství - 16. 6. 2015

Příspěvek od rumburak »

1) Překladače a výkonnost software: Analáza zdola nahoru (Yaghob). Řekl jsem co to je a v čem se principiálně liší od top-down analýzy, co to je redukce. Neformální definice FIRST a FOLLOW, neformální definice LR(0) položky, CLOSURE a GOTO, příklad s "pověstnou" gramatikou, maličký kousek kanonické kolekce jsem nakreslil a z ní napsal jeden řádek do výsledné tabulky SLR(1) automatu. Popsal jsem, jak automat pracuje, pak LR(1) položky a druhý příklad gramatiky, pro kterou jsem kanonickou kolekci (tentokrát LR(1) položek) zkonstruoval celou. Moc nebylo co řešit, na tuhle otázku jsem byl připravený, několikrát jsem si doma zkoušel ty kolekce a tabulky konstruovat. Všechny definice jsem měl velmi neformálně.

2) Operační systémy: Synchronizace procesů, synchronizační primitiva a problémy (Bulej). Při zadávání otázky mi bylo řečeno, ať hlavně popíšu nějaké konkrétní synchronizační primitivum, ať ukážu jeho implementaci a pak ať popíšu nějaký klasický problém, třeba producent-konzument. Napsal jsem něco obecně (k čemu je synchronizace, co je race condition, co je deadlock) a pak jsem hlavně popisoval mutex, naimplementoval jsem ho v skoro-x86 assembleru pomocí aktivního čekání a že je hodně variant, aktivní, pasivní, spinlock, rekurzivní, atd. Pak jsem napsal něco o semaforu, o conditional variable, a k producentovi-konzumentoval jsem prostě jenom napsal řešení z wikipedie. Diskuze se zkoušejícím byla primárně o mutexu, jak by se tam udělalo pasivní čekání, co by tam musel zajišťovat operační systém, a co by se dalo udělat v user-modu.

3) Vývoj softwarových systémů: Vývojová prostředí, nástroje pro ladění, testování funkčnosti a výkonnosti (Kruliš). Při zadávání mi zkoušející řekl, ať se hlavně soustředím na tu "výkonnost". Popsal jsem různé nástroje daných kategorií (Visual Studio, Xcode, gdb, lldb, valgrind, Address Sanitizer, FindBugs, JUnit, gprof, ...), interaktivní debata pak byla zejména o debuggerech, jak je zhruba nějaký debugger naimplementován, dále o instrumentaci a o profilingu a benchmarkingu.

4) Složitost a vyčíslitelnost: Aproximační algoritmy a schémata (Hric). Zadefinoval jsem přípustné řešení, hodnotu řešení, optimální řešení, aproximační algoritmus a aproximační poměr. Napsal jsem bin packing a first-fit algoritmus, myšlenku důkazu proč je apx. poměr 2. V definicích jsem měl obráceně nerovnosti, což se zkoušejícímu samozřejmě nezdálo, tak jsem je opravil. Ptal se na nějaké další věci k aproximačním algoritmům, jak postupovat, když mám nějaké heuristiky, ale o tom jsem prakticky nic nevěděl. Zadefinoval jsem schéma, polynomiální schéma a úplně polynomiální schéma, a příkladem byl batoh, s tím že jsem algoritmus popsal velice neformálně a navíc jsem řekl, že si nepamatuju jak spočítat tu konstantu "t", kterou pak dělím všechny ceny, že to prostě musí být "tak, aby to vyšlo" (čemuž se Hric zasmál). Nakonec to nějak prošlo, a bavili jsem se poměrně dlouho o tom algoritmu, proč funguje a jakou má složitost, tak jsem tam ještě naznačoval, jak funguje ten algoritmus bahotu, který má tabulku přes součty cen (a ne přes velikost batohu). Z toho, na co se mě zeptal, jsem skoro nic nevymyslel, ale i přesto Hric působil, že je tak nějak spokojený.

5) Datové struktury: Hašování a řešení kolizí (neznámý hodný zkoušející). Popsal jsem proč hašujeme, co je kolize, co je load faktor, jak vypadá hašování se separovanými řetězci, jaký je nejhorší čas a průměrný čas (při rovnoměrném rozdělení), nic jsem nedokazoval. Pak jsem popsal pár (4 až 5) dalších metod, vždycky ale velmi neformálně, napsaný na papíře jsem měl vždycky jenom název a zbytek jsem popsal slovně a k tomu kreslil obrázek, a ukazoval co se děje při kolizích. Zkoušející neřekl vůbec nic, a když jsem dopovídal, řekl, že mu to stačí a odešel.

Ještě se mi stala taková věc, že jsem nějak špatně pochopil, v jakém pořadí zkoušející přijdou, takže se mi samozřejmě stalo, že jsem si připravil otázku a přišel někdo jiný. Ale byl hodný, řekl, že zkusí sehnat toho druhého člověka, ale ten nemohl, zkoušel jinde. Tak mi řekl, ať se prostě připravuju dál, že si za mnou přijde až úplně nakonec. Takže doporučuju se při zadávání otázek (což se děje na začátku najednou!) každého zeptat, kolikátý vás bude zkoušet. Mě totiž zadali první otázku a nic mi k tomu neřekli, tak jsem myslel, že to bude v tom pořadí, jak přišli, ale až druhý nebo třetí mi řekl něco jako "já vás budu zkoušet až jako poslední", a to, že bych si to pořadí měl někam napsat, jsem pochopil až moc pozdě.
Odpovědět

Zpět na „Magisterské SZZ“