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.

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

Příspěvekod mathemage » 9. 6. 2016 16:31

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!
mathemage
Matfyz(ák|ačka) level III
 
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Login do SIS: had

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

Příspěvekod Abby » 9. 6. 2016 21:04

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
Abby
Matfyz(ák|ačka) level I
 
Příspěvky: 21
Registrován: 4. 9. 2011 11:57
Typ studia: Informatika Mgr.


Zpět na Magisterské SZZ

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník