IA012 Složitost

Fakulta informatiky
jaro 2004
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Rozvrh
Út 8:00–9:50 B410
Předpoklady
! I017 Strukturní složitost
Znalost problematiky v rozsahu předmětu IB107 - Vyčíslitelnost a složitost.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
Mateřské obory/plány
Cíle předmětu
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ů.
Osnova
  • 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.
Literatura
  • SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Záložky
https://is.muni.cz/ln/tag/FI:IA012!
Metody hodnocení
Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na průběžné práci v semestru. Přesná specifikace požadavkú viz www stránka předmětu.
Informace učitele
http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.