# Zkouška - Mareš 28. 1. 2019 - dopoledne

<{ForumPost(poster="Vilda", timestamp=2019-01-28 11:43:59)}>
1. FFT (DFT, inverze, FFT, aplikace)  
2. Máme šachovnici s chybějícími políčky. Jak na to položíme domino?  
3. Máme profil výšky na horách, chceme zjistit nejčastější výšku.  
[https://www.vyletnik.cz/data/trasy/cykl ... profil.jpg](https://www.vyletnik.cz/data/trasy/cyklo/krusne-hory-zapad//Magistr%C3%A1la%20%28Kr%C3%A1sn%C3%A1%20-%20B.Dar%20-%20M%C4%9Bd%C4%9Bnec%29-profil.jpg)  
(Je to prostě lomená čára, která je zároveň funkce)  
  
Mé řešení, které asi není moc optimální, ale na pěknou známku s trochou přesvědčování stačilo.  
1. Tady chtěl dost definice, složitosti i malý důkaz. To se nedá udělat jinak než si to přečíst.  
2. Lze řešit perfektním párováním. To obecně trvá dlouho, ale lze to i nacpat do bipartitního grafu a za pomocí FF na O(n^4)  
3. Úloha na barvení intervalů/zametání roviny. Stačí si udělat projekci a pak jen počítat otevírání a uzavírání závorek. O(n log n) za třízení podle výšky.
<{/ForumPost}>