Zkouška 9.2.2016

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Classemence_

Zkouška 9.2.2016

Příspěvek od Classemence_ »

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.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“