# Zkouška 9.2.2016

<{ForumPost(poster="Classemence_", timestamp=2016-02-09 21:33:04)}>
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.
<{/ForumPost}>