Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Teorie složitosti

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
01TSLO ZK 3 3+0 česky
Přednášející:
Vladan Majerech (gar.)
Cvičící:
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 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 15. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet12074805.html