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

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Vilda
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 15. 1. 2018 15:02
Typ studia: Informatika Bc.

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

Příspěvek od Vilda »

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.
Obrázek
(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.
Odpovědět

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