od Classemence_ » 9. 2. 2016 21:33
Na dnešní zkoušce zadal opět tři úlohy.
1) Napište definici diskrétní Fourierovy transformace, inverzní matici (+dk), co je to FFT + složitost
2) Je dán bipartitní graf. Úkolem je najít podmnožinu hran takovou, že každému vrcholu zbyde stupeň přesně 2.
3) Je dán strom s ohodnocenými vrcholy. Ze všech nezávislích podmnožin v tomto stromě najděte tu, která je nejtěžší.
Spoiler k řešení:
2) Úloha se převede na hledání toku v síti. Tim, že má graf takovýto speciální tvar tak se ten tok najde rychleji než v obecném grafu. (myslím, že Dinic by to měl stihnout v O(nm))
3) dynamické programování od listů směrem vzhůru. U každého vrcholu X si pamatuju dvě hodnoty "je","neni" které mi říkají, jakou největší NzMn v podstromu s kořenem X dokážu vytvořit ´, když v ní X bude, nebo nebude.
Na dnešní zkoušce zadal opět tři úlohy.
1) Napište definici diskrétní Fourierovy transformace, inverzní matici (+dk), co je to FFT + složitost
2) Je dán bipartitní graf. Úkolem je najít podmnožinu hran takovou, že každému vrcholu zbyde stupeň přesně 2.
3) Je dán strom s ohodnocenými vrcholy. Ze všech nezávislích podmnožin v tomto stromě najděte tu, která je nejtěžší.
Spoiler k řešení:
2) Úloha se převede na hledání toku v síti. Tim, že má graf takovýto speciální tvar tak se ten tok najde rychleji než v obecném grafu. (myslím, že Dinic by to měl stihnout v O(nm))
3) dynamické programování od listů směrem vzhůru. U každého vrcholu X si pamatuju dvě hodnoty "je","neni" které mi říkají, jakou největší NzMn v podstromu s kořenem X dokážu vytvořit ´, když v ní X bude, nebo nebude.