You are currently viewing the whole syllabus; go back to default view.
The speed of loading and viewing the syllabus may be slower when showing a large amount of content.
Sylaby
Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity
výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických
problémů a~rozvíjí techniky, které dovolují redukovat hledání
efektivních algoritmů pro celou třídu algoritmických problémů na hledání
efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje
problémy podle jejich výpočetní složitosti na prakticky zvladatelné a
nezvladatelné a ukazuje důvody nezvladatelnosti (praktické
neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout
hranici zvladatelnosti techniky jako randomizace, aproximace a
paralelní postupy řešení problémů.
- Struktura a vlastnosti časových složitostních tříd. Vztah
determinizmu a nedeterminizmu. - Struktura a vlastnosti prostorových složitostních tříd. Vztah
determinizmu a nedeterminizmu. - Nezvladatelné problémy. Nekonečnost hierarchie složitostních
tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní
složitost. - Pravděpodobnostné složitostní třídy a jejich struktura.
- Aproximativní složitostní třídy a neaproximovatelnost.
- Alternování a hry. Interaktivní protokoly a interaktivní
důkazové systémy. - Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská
složitost. - Deskriptivní složitost.
Uvedený seznam je orientační, konkrétní náplň přednášek je přispůsobena znalostem a zájmům posluchačů.
Organizace výuky
Každý týden přednáška v rozsahu 2 hodin.
V průběhu semestra studenti samostaně řeší sady problémů, obvyklá frekvence je 1 sada / 2 týdny.
Ústní zkouška na konci semestra.
Literatura a linky
Doporučené
www.cs.princeton.edu/theory/complexity/
Knihy
- Jose Luis Balcazar, Josep Diaz, Joaquim Gabarro: Structural Complexity I,II, Springer Verlag 1995
- Daniel Pierre Bovet, Pierluigi Crescenzi: Introducition to the Theory of Complexity, Prentice Hall 1993
- Michael R. Garey, David S. Johnson: Computers and Intractability: a Guide to the Theory of NP-completness, W.H.Freeman and Company, San Francisco, 1979
- Lane A. Hemaspaandra, Mitsumori Ogihara: The Complexity Theory Companion. Springer, 2005
- Christos H. Papadimitriou: Computational Complexity, Addison-Wesley 1994
- Uwe Schonig, Randall Pruim: Gems of Theoretical Computer Science, Springer Verlag, 1998
- Michale Sipser: Introduction to the Theory of Computation, PWS Publishing Company 1996
- Ingo Wegener: Complexity Theory (Exploring the Limits of Efficient Algorithms, Sprin
On-line
Laszlo Lovasz: Computation Complexity
Ingo Wegener: The Complexity of Boolean Functions
Johan Hastad: Complexity Theory
Pierluigi Crescenzi and Viggo Kann: A compendium of NP optimization problems
Richard Ladner: Complexity Theory Lectures
Herbert Wilf:Algorithms and Complexity
Uri Zwick: Boolean Circuit Complexity
Oded Goldreich: Foundations of Cryptography
Oded Goldreich: Probabilistic Proof Systems
Sada problémů 1
řešení odevzdávejte do 5. 3. 2009 do 10.00 a to buď elektronicky do odevzdávárny anebo papírově na sekretariát kateder nebo přímo na přednášce.
Informace o obtížnosti příkladů a způsobu hodnocení řešení na přednášce 19. 2. 2009.
Sada problémů 2
řešení odevzdávejte do 19. 3. 2009 do 10.00 a to buď elektronicky do odevzdávárny anebo papírově na sekretariát kateder nebo přímo na přednášce.
Sada problémů 3
Sada 3 a její vzorové řešení
řešení odevzdávejte do 26. 3. 2009 do 10.00 a to buď elektronicky do odevzdávárny anebo papírově na sekretariát kateder nebo přímo na přednášce.
Příklady z přednášky 19.3.2009
Sada problémů 4
řešení odevzdávejte do 23. 4. 2009 do 10.00 a to buď elektronicky do odevzdávárny anebo papírově na sekretariát kateder nebo přímo na přednášce.
Sada problémů 5
- Prečítajte si text The P?=NP Poll a napíšte svoje odpovede na otázky 2.1., 2.2. a 2.3.
- Prelistujte si stránku P-versus-NP page a napíšte, čo si o probléme P?=NP myslí Homer Simpson (a v ktorej epizóde?)
Riešenia odovzdajte do 14.5.2009 do 10:00 na prednáške alebo do odevzdávarny.
Vzorove riesenie prikladov Sady 5