od mathemage » 9. 6. 2016 17: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 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
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.
Kvůli jistým osobním komplikacím jsem si zažádal o zkoušení dle nových studijních plánů:
[list]
[*] [url]http://www.mff.cuni.cz/studium/bcmgr/ok/i3b1.htm[/url]
[*] [url]http://www.mff.cuni.cz/studium/bcmgr/ok/i3b21.htm[/url] (Optimalizace)[/list]
Základní okruhy:
[list]
[*] [b]Základní třídy složitosti a jejich vztahy[/b]
[list]
[*] definice pro P, NP, co-NP, NP-těžkost, NP-úplnost, polynomiální převod
[*] hierarchie [latex]L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq NPSPACE \subseteq EXPTIME[/latex] Dotazy:
[list]
[*][i]existuje P-úplný problém[/i] - 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 [latex]L[/latex].
[*][i]příklad PSPACE-úplného problému[/i] - nevěděl jsem, ale je to něco jako problém existence vítězné strategie v (kombinatorické) hře (viz. [latex]\Sigma_2[/latex] hierarchie)[/list]
[*] znění Cook-Levinovy věty (dotaz: [i]KACHL oblíbený na matfyzu, ale v původním článku pro... SAT[/i]), znění Savičovy věty[/list]
[*] [b]Haldy[/b]
[list]
[*] operace min, insert, delete_min
[*] (d-) regulární halda
[*] binomiální haldy (dotaz: [i]Je tvar stromu a počet vrcholů binomiálního stromu jednoznačně určen jeho rankem (stupněm kořene)?[/i] - Ano, strom [latex]T_i[/latex] s rankem [latex]i[/latex] má přesně [latex]2^i[/latex] vrcholů a podstromy synů kořena zleva doprava jsou [latex]T_0, T_1, \dots T_{i-1}[/latex]).
[*] Dijkstrův algoritmus pro nejkratší vzdálenosti, motivace pro operaci decrease_key a haldu specializovanou pro jeji efektivní implementaci - Fibonacciho haldu
[*] Fibonacciho haldy (dotaz: [i]Může Fib. strom malého ranku (stupněm kořene) mít pod sebou obrovský strom?[/i]) - Ano, kořenu stromu [latex]T_i[/latex] můžeme utrhnout všechny syny s podstromy [latex]T_0, T_1, \dots T_{i-2}[/latex]. Tím zbyde jediný "velkým" podstrom [latex]T_{i-1}[/latex][/list][/list]
Specializace:
[list]
[*] [b]Algoritmická teorie her[/b]
[list]
[*] Volební mechanismy
[list]
[*] 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[/list]
[*] Mechanismy s penězmi
[list]
[*] 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[/list][/list]
[*] [b]Dualita v nelineárním programování[/b]
[list]
[*] 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: [i]Může zde někdy dojít k rovnosti?[/i] Ano, ale jsou k tomu potřeba dodatečné podmínky - viz. silná věta o dualitě nelineárního programování.)[/list][/list]
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:
[list]
[*] 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í
[list]
[*] 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.[/list][/list]