Dr. Vladan Majerech (externí spolupracovník)

www: http://ktiml.mff.cuni.cz/~maj/
instituce: MFF UK
 
rozvrh
předmět kód vyučující zs ls zs kr. ls kr.
Teorie složitosti01TSLO Majerech 3+0 zk - - 3 -
Předmět:Teorie složitosti01TSLOMajerech Vladan3+0 ZK-3-
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ů.
Osnova: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: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.
Požadavky:
Rozsah práce:
Kličová slova:Složitost, NP-úplnost, algoritmus.
Literatura: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í.


za obsah této stránky zodpovídá: Radek Fučík | naposledy změněno: 7.8.2011
Trojanova 13, 120 00 Praha 2, tel. 224 358 540, pevná linka 224 923 098, fax 234 358 643
České vysoké učení technické v Praze | Fakulta jaderná a fyzikálně inženýrská | Katedra matematiky