Teorie složitosti

Garant předmětu:

Petr Ambrož, Jan Volec

Přednášející:

Petr Ambrož, Jan Volec

Cvičící:

Petr Ambrož

Předmět zajišťuje:

katedra matematiky

Anotace:

Obsahem předmětu je zohlednění složitosti při návrhu algoritmů, seznámení s NP úplností a obecně s třídami výpočtů deterministických či nedeterministických Turingových strojů omezených časem či prostorem. Důraz je kladen na vzájemné vztahy těchto tříd. Kromě nedeterministických tříd jsou probírány i pravděpodobnostní třídy. Přednáška končí seznámením s třídou interaktivních protokolů.

Požadavky:

Osnova přednášek:

1. Dimenze složitosti - očekávaná, randomizovaná, amortizovaná; základní datové struktury.

2. Rozděl a panuj - rekurence, Strassenův algoritmus, třídění (+dolní odhad), hledání mediánu, prune and search.

3. Fibonacciho haldy, Dijkstrův algoritmus, hledání minimální kostry - Fredman+Tarjan, Kruskalův algoritmus a DFU.

4. NP-úplnost a základní transformace. (SAT, kachlíčkování, klika).

5. Další příklady NP-úplných problémů (Hamiltonovskost, batoh) úplné polynomiální aproximační schéma pro batoh.

6. Turingovy stroje, lineární komprese a zrychlení, redukce počtu pásek, universální stroje.

7. Konstruovatelnost funkcí, inkluze mezi třídami složitosti. Věty o hierarchii.

8. Translační lemma, Borodinova věta, Blumova věta.

9. Zobecněný nedeterminismus a pravděpodobnostní třídy.

10. Polynomiální hierarchie, úplné problémy.

11. Interaktivní protokoly.

Osnova cvičení:

Cíle studia:

Znalosti:

Dimenzování složitosti, NP-úplné problémy, Turingovy stroje a zobecněný nedeterminismus.

Schopnosti:

Naučit se zohledňovat otázky složitosti při návrzích algoritmů, naučit se přemýšlet o dolních odhadech složitosti problémů. Znát základní vztahy mezi třídami složitosti.

Studijní materiály:

Povinná literatura:

[1] J. L. Balcázar, J. Díaz, J Gabarró: Structural Complexity I, Springer - Verlag Berlin Heidelberg New York London Paris Tokyo 1988.

Doporučená literatura:

[2] Hopcroft, Ullmann: Introduction to Automata Theory and Computing, ISBN 0-201-02988-X.

[3] Vladan Majerech: Úvod do složitosti a NP-úplnosti, skripta volně ke stažení.

[4] Vladan Majerech: Složitost a NP-úplnost, skripta volně ke stažení.

Poznámka:

Rozvrh na zimní semestr 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Matematické inženýrství (volitelný předmět)
• Aplikace softwarového inženýrství (volitelný předmět)
• Aplikovaná algebra a analýza (volitelný předmět)
• Aplikace informatiky v přírodních vědách (volitelný předmět)
• Matematická informatika (povinný předmět programu)