Obsahová náplň štátnicového predmetu

Štátna skúška je realizovaná formou rozpravy so zameraním na jednu z tém predmetov ÚINF/KMU1 (ekvivalentne ÚINF/KPI), ÚMV/TKO, ÚINF/VYZ1 a ÚMV/KOA.

1. Aritmetické kódovanie.

2. Využitie diskrétnej Fourierovej transformácie pri kódovaní.

3. Test na rozoznávanie kódov.

4. Využitie Bernoulliho distribúcie pri klasifikácii kódov.

5. Pojem nedeterministického algoritmu pracujúceho v polynomiálnom čase, NP-úplnosť.

6. Významné NP-úplné problémy.

7. Eulerovské grafy, úloha čínskeho poštára.

8. Problém obchodného cestujúceho - výsledky o zložitosti, aproximačné algoritmy.