Státnice Informatika: Diskrétní modely a algoritmy 8.6.2016

Vše o státnicích úspěšně završujících roky studia na naší alma mater.
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Státnice Informatika: Diskrétní modely a algoritmy 8.6.2016

Příspěvek od mathemage »

Kvůli jistým osobním komplikacím jsem si zažádal o zkoušení dle nových studijních plánů: Základní okruhy:
  • Základní třídy složitosti a jejich vztahy
    • definice pro P, NP, co-NP, NP-těžkost, NP-úplnost, polynomiální převod
    • hierarchie L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq NPSPACE \subseteq EXPTIME Dotazy:
      • existuje P-úplný problém - to záleží na funkci použité pro převod. Většinou se bere funkce z nižší složitostní třídy než je třída, kterou zkoumáme pro úplnost. Tj. pro polynomiální převod by každý problém byl "P-úplný". Lze též uvážit převod funkcí z L.
      • příklad PSPACE-úplného problému - nevěděl jsem, ale je to něco jako problém existence vítězné strategie v (kombinatorické) hře (viz. \Sigma_2 hierarchie)
    • znění Cook-Levinovy věty (dotaz: KACHL oblíbený na matfyzu, ale v původním článku pro... SAT), znění Savičovy věty
  • Haldy
    • operace min, insert, delete_min
    • (d-) regulární halda
    • binomiální haldy (dotaz: Je tvar stromu a počet vrcholů binomiálního stromu jednoznačně určen jeho rankem (stupněm kořene)? - Ano, strom T_i s rankem i má přesně 2^i vrcholů a podstromy synů kořena zleva doprava jsou T_0, T_1, \dots T_{i-1}).
    • Dijkstrův algoritmus pro nejkratší vzdálenosti, motivace pro operaci decrease_key a haldu specializovanou pro jeji efektivní implementaci - Fibonacciho haldu
    • Fibonacciho haldy (dotaz: Může Fib. strom malého ranku (stupněm kořene) mít pod sebou obrovský strom?) - Ano, kořenu stromu T_i můžeme utrhnout všechny syny s podstromy T_0, T_1, \dots T_{i-2}. Tím zbyde jediný "velkým" podstrom T_{i-1}
Specializace:
  • Algoritmická teorie her
    • Volební mechanismy
      • definice voličů, množiny preferenčního uspořádání, social welfare function, social choice function
      • vlastnost diktatorství, jednohlasnosti (unanimity), independence of irrelevant alternatives
      • znění Arrowovy věty, Gibbard–Satterthwaiteovy věty
    • Mechanismy s penězmi
      • definice mechanismu, social choice function, value functions, payment functions, utility
      • vlastnost incentive-compatibility
      • Vickreyho aukce (2nd price auction), její incentive-compatibility
      • VCG mechanismus, incentive-compatibility všech VCG mechanismů, Clarkovo pivotovací pravidlo
  • Dualita v nelineárním programování
    • Farkasovo lemma, Gordanova věta
    • podmínky Fritze-Johna, KKT podmínky, se Slaterovou podmínkou
    • Lagrangův duál, Lagrangova funkce. gap mezi hodnotou duální a primární optimální hodnoty (dotaz: Může zde někdy dojít k rovnosti? Ano, ale jsou k tomu potřeba dodatečné podmínky - viz. silná věta o dualitě nelineárního programování.)
U komise: prof. L. Kučera, doc. P. Kolman, doc. M. Klazar, doc. P. Valtr

Výsledky: všichni 4 studenti za 1

Komentáře:
  • Trvalo to od 9:00 do cca 12:30 - 13:00.
  • Jeden z nás měl i obhajobu. Ta probíhala, zatímco jsme se písemně připrovali. Dotyčný dostal pak otázky po konci obhajoby.
  • Když měl někdo (aspoň částečně hotovo), šel to říkat aspoň 2 zkoušejícím. Tím se šetřil čas. Typicky 2 (nejvíc) hotové otázky, prezentování, návrat k písemné přípravě pro zbytek.
  • Normálně by to netrvalo tak dlouho, ale naše skupina měla problém, že toho napsala "až moc". Normálně lidi napíšou půl stránky a pak to z nich zkoušející tahají. My jsme 1 téma popsali až na 3 stránky A4, takže u nás to trvalo z opačných důvodů :-)
  • Tipy na učení
    • Učte se hlavně do šířky než do hloubky. U každé otázky musíte aspoň něco vědět, co napsat.
    • Důkazy nejsou třeba, hlavně když jsou extrémně technické. To se nebude chtít číst a sledovat ani vám, ani zkoušejícím.
    • Ale člověk by měl chápat, proč věci fungujou a proč něco jiného nefunguje bez daných předpokladů. Může přijít otázka, která odhalí porozumění tématiky.
Carpe Diem!
Abby
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 4. 9. 2011 12:57
Typ studia: Informatika Mgr.

Re: Státnice Informatika: Diskrétní modely a algoritmy 8.6.2

Příspěvek od Abby »

Pridávam moje zážitky, rovnako zameranie Optimalizace podľa nových plánov.

Základné okruhy:
  • Algoritmicky nerozhodnutelné problémy
    • Definície Turingovho stroja, ČRF, rekurzívnych a rek. spočetných množín
    • Veta + dôkaz: K0 a K sú rekurzívne spočetné, ale nie rekurzívne.
    • Riceova veta + dôkaz
  • Hašování, univerzální hašování
    • Definícia hašovacej funkcie a kolízie, prehľad rôznych typov hašovania
    • Kukaččí hašování + dôkaz o pravdepodobnosti cyklu v grafe
    • Motivácia pre univerzálne hašovanie, c-univerzálny systém a lemma o strednom počte prvkov v priehradke, 1-univerzálny systém zo skalárneho súčinu
Špecializácia:
  • Kvadratické programování
    • Charakterizácia konvexity cez pozitívnu semidefinitnosť
    • Prevod zo set partitioning na maximalizáciu konv. kvadratickej funkcie
    • Aplikácia duality na konv. kvadratický program, charakterizácia optimality pomocou gradientu + dôkaz
  • Úlohy lineárního programování s podmínkami celočíselnosti
    • Unimodularita + dôkaz Hoffman-Kruskalovej vety
    • Prehľad metód (Branch-and-bound, sečné nadroviny, heuristiky)
    • Aplikácia na TSP (modelovanie podmienky na hamiltonovskú kružnicu, základná hrebeňová nerovnosť + dôkaz) a problém batohu (cover nerovnosti)
Moja stratégia bola naučiť sa k jednotlivým okruhom 1-2 hlavné dôkazy a mať prehľad o ostatných veciach. Doba prípravy na štátnice necelé 3 týždne, keďže som predtým ešte dorábala skúšky a viac času sa nenašlo.

Okrem vlastných poznámok sa mi osvedčili materiály:
  • Složitost a vyčíslitelnost: Slajdy a poznámky od P. Kučery
  • Datové struktury: poznámky k prednáške od M. Kouckého a text k univerzálnemu hašovaniu od M. Mareša
  • Optimalizace: skriptá k prednáškam od M. Hladíka
Odpovědět

Zpět na „Magisterské SZZ“