Zkouška 9.2.2016

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.