Zkouška - Hric 7.2.2018

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Speedding
Matfyz(ák|ačka) level I
Příspěvky: 35
Registrován: 10. 1. 2017 19:32
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Zkouška - Hric 7.2.2018

Příspěvek od Speedding »

1)
A) Hledání toku metodou zlepšující cesty
- Hricova prezentace strana 21, 22
B) Vymyslet konkrétní graf s max 10 hranami, kde se zlepšující cesta najde až 1000x, dokud se nenalezne maximální tok (a popsat zvolenou strategii volby cest)
- https://en.wikipedia.org/wiki/Ford%E2%8 ... al_example

2) Aho-Corasick, popis vyhledávacího algoritmu a důkaz složitosti
- Hricova prezentace strana 7, 9

3) ‎DFT pro (1,3,1,3,1,3,1,3)
- Jednoduše pomocí FFT, na webu je spousta kalkulaček na ověření. Rozdělím na vektor sudých a lichých členů (3,3,3,3) a (1,1,1,1), na to dál pouštím rekurzi. Pro vektor (k,...,k) platí, že jeho obraz je (kn,0,...,0), proto obraz pro (3,3,3,3) je (12,0,0,0) a pro (1,1,1,1) je (4,0,0,0) - ale do zkoušky by to asi chtělo rozepsat. Ted už stačí jen projet ten for cyklus z prvního volání funkce, ani nemusím počítat omega, protože je vidět, že nenulové budou jen pozice y_0 a y_4. Odtud y_0 = 4 + 12 = 16 a y_4 = 4 - 12 = -8. Proto je odpověď (16,0,0,0,-8,0,0,0)

4)
A) Definice - rozhodovací problém, polynomiální převoditelnost, P, NP, NPÚ
- Hricova prezentace strana 58, 59, 62
B) Převod SAT na 3-SAT
- Marešovy skripta strana 435
Odpovědět

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