ITI - 10.09.2015

Vše o státnicích úspěšně završujících roky studia na naší alma mater.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

ITI - 10.09.2015

Příspěvek od Davpe »

1) Složitost (A. Kučera)
Savičova věta
- Kučera v rychlosti důkaz proletěl a jen se zeptal jaká je jeho hlavní myšlenka

2) Datové struktury (Pangrác)
Třídění vě vnitřní a vnější paměti
- U třídění ve vnitřní paměti jsem tam vypsal jen názvy známých algoritmů, podrobněji jsem popsal jen HybridSort a u Shellsortu jsem napsal něco o přírůstkových posloupnostech.
- U třídění ve vnější paměti jsem popsal Exquisit pro třídění na discích (z přednášky od Koubkové), tam se Pangrác vyptával jak funguje a chtěl vědět jak volit pivota. U pásek jsem popsal dva základní Mergesorty. Ještě po mně chchtěl analýzu očekávané složitosti Quicksortu (včetně předpokladů) což jsem mu spočítal, jinak nikde jinde po mně žádné důkazy nebo složitosti říct nechtěl.

3) Rekurze a strukturální složitost (A. Kučera)
1-generické množiny
- Kučera mi dal na výběr mezi 1-generickými a 1-náhodnými. Vybral jsem si 1-generické, zadefinoval je, dokázal jsem že existuje 1-generická pod Halting problémem. Dále jsem bez důkazu vyslovil věty o tom že 1-generická nemá nekonečnou r.s. podmnožinu a že pod 1-generickou nejsou nerekurzivní r.s. množiny. Ptal se jen jaká je idea důkazu těchto vět.

4) Konkrétní algoritmy (Majerech)
FFT
- Dal mi zvolit číslo od 1 do 14, mnou zvolené číslo 13 vedlo na externí třídění. Vzhledem k tomu že podobnou otázku jsem měl už v datovkách tak jsem se zeptal co s tím a dal mi zvolit jiné číslo. Asi pět dalších jich vedlo opět na třídění (což napovídá že Majerech zkouší asi jen velice omezený okruh otázek) až jsem se trefil do Fourierky
- Zadefinoval jsem evaluaci a interpolaci polynomů, n-tou primitivní odmocninu z 1, Vandermondovu matici, její invers (vytáhl ze mě i důkaz). Pak už jsem tápal, nemohl jsem si vzpomenout jak přesně ten algoritmus funguje a na co se rekurzí a Majerech mě tam docela koupal v komplexních číslech (chtěl vědět o té n-té primitivní odmocnině z 1 v komplexních číslech, kolik jich tam je, jak vypadají, jak to vypadá na té kružnici, co jsou polární souřadnice a jak se v nich násobí čísla).

5) Umělá inteligence (Vomlelová)
Rezoluce a unifikace
- Původně mi zadala EM-algoritmus ale spíš než zadávala se ptala, tak jej po mém nesouhlasném zamručení vyměnila za rezoluci.
- UI jsem si nestihl zopakovat takže se mi povedlo zapomenout co a k čemu rezoluce je a s unifikací jsem na tom nebyl o moc líp, takže jsem měl skoro prázdný papír. Vomlelová si ke mně přisedla, napsala mi jednoduchou výrokovou formuli kterou jsem měl rezolvovat, což se mi úspěšně povedlo. Pak napsala dvě predikátové formule které jsem měl unifikovat, což se mi moc nepodařilo tak mi navrhla že mi to ukáže ale sníží mi známku. Když jsem ji ujistil že to nevadí, ty formule zunifikovala, prohlásila že je spokojená a odešla. Na to že jsem vzhledem ke svým znalostem čekal naprostý výbuch to bylo opravdu milé překvapení.

Závěrem horší jednička. Vyhodili jednoho člověka, ale ten nezvládl ani zadefinovat po značné době PSPACE, vyslovit aspoň přibližně Saviče a nevěděl nic o vztahu tříd P a NP.
Odpovědět

Zpět na „Magisterské SZZ“