- http://www.mff.cuni.cz/studium/bcmgr/ok/i3b1.htm
- http://www.mff.cuni.cz/studium/bcmgr/ok/i3b21.htm (Optimalizace)
- 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 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 .
- 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. 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 s rankem má přesně vrcholů a podstromy synů kořena zleva doprava jsou ).
- 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 můžeme utrhnout všechny syny s podstromy . Tím zbyde jediný "velkým" podstrom
- 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
- Volební mechanismy
- 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í.)
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.