FI:IA012 Složitost - Informace o předmětu

IA012 Složitost

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 10:00–11:50 B410

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

• Aplikovaná informatika (program FI, N-AP)
• Bezpečnost informačních technologií (program FI, N-IN)
• Bioinformatika (program FI, N-AP)
• Informační systémy (program FI, N-IN)
• Informatika (program FI, M-IN)
• Informatika (program FI, N-IN)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové systémy (program FI, N-IN)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Teoretická informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Učitelství výpočetní techniky pro střední školy (program FI, M-TV)
• Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
• Zpracování obrazu (program FI, N-AP)

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í

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2009/IA012/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

• Statistika zápisu (jaro 2009, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2009/IA012