Smyslem předmětu je objasnit základní přístupy a metody klasifikace problémů z hlediska možnosti jejich algoritmického řešení a provést základní klasifikaci. Současně chce kurz poukázat na teoretické a praktické meze využití počítačů a důsledky, které tato omezení mají pro rozvoj informačních technologií. Hlavní cíle předmětu jsou: porozumět základním pojmům formalizujícím algoritmickou řešitelnost; zvládnout klasifikační techniky redukce, diagonalizace a uzávěrové vlastnosti; umět tyto techniky aplikovat na jednoduche situace.

Rozvrh

Přednáška: Čtvrtek, 10:00 - 11:50, posluchárna D2

Cvičení:

IB107/01 Čt 14:00--14:50 G123, J. Fabriková
IB107/02 Čt 15:00--15:50 G123, J. Fabriková
IB107/03 St 16:00--16:50 G125, J. Fabriková

Cvičení jsou povinná.
Cvičení začínají již 20.9.2012!

Osnova

• Problémy a algoritmy.
• Algoritmus jako výpočetní model. Základní výpočetní modely. Churchova teze.
• Klasifikace problémů. Rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy.
• Postův korespondenční problém. Vybrané nerozhodnutelné problémy z teorie jazyků.
• Výpočetní složitost problémů. Výpočetně těžké a lehké problémy.
• Redukce a úplnost v třídách problémů. Redukce a polynomiální redukce. Úplné problémy z hlediska rozhodnutelnosti, NP-úplné problémy. Aplikace.

Požadavky na absolvování předmětu

Účast na cvičeních je povinná a studenti jsou povinni se na cvičení řádně připravovat dle požadavků cvičících. Nepřipravenost na cvičení je posuzována jako nepřítomnost. Jsou povoleny 2 nepřítomnosti (v případě zdravotních či jiných důvodů je nutné situaci řešit individuálně s cvičícím).

Během semestru studenti vypracovávají domácí úkoly dle požadavků cvičících. Za tyto úkoly lze získat maximálně 15 bodů.

Předmět možné ukončit zkouškou, kolokviem nebo zápočtem. Všechna ukončení mají stejnou formu jako zkouška, liší se pouze počtem bodů, které je potřebné získat. Podmínkou pro připuštění ke zkoušce je řádná účast na cvičeních a získání minimálně 6 bodů za řešení domácích úkolů. Závěrečná zkouška je písemná. Za písemku lze získat maximálně 85 bodů. Body z domácích úkolů se započítávají do závěrečného hodnocení, celkem je tak možné získat 100 bodů.

Při závěrečné písemce není použití literatury a poznámek dovoleno.

Doporučená literatura

• Sipser, Michael. Introduction to the theory of computation. Boston : PWS Publishing Company, 1997.
• Kozen, Dexter C. Automata and computability. New York : Springer, 1997. Undergraduate texts in computer science.
• Kfoury, A. J. - Moll, Robert N. - Arbib, Michael A. A programming approach to computability. New York : Springer-Verlag, 1982. The AKM series in theoretical computer science.
• Bovet, D. (Daniel) - Crescenzi, Pierluigi. Introduction to the theory of complexity. New York : Prentice-Hall, 1994. Prentice Hall International Series in Computer Sience.
• Papadimitriou, Christos H.: Computational complexity. Addison-Wesley Publishing Company, c1994

Studijní materiály

Materiály jsou dostupné pouze z domény .muni.cz a nesmí být umístěny na veřejně dostupnou doménu!

• Pro první přednášky je k dispozici starší, ale osvědčený, učební text.
• Pro přednášky o složitosti lze k doplnění požít i tento pracovní předběžný text. Prosím o velkou shovívavost při jeho čtení!
• Příklady do cvičení.

Slidy k přednáškám

Slidy jsou dostupné pouze z domény .muni.cz a nesmí být umístěny na veřejně dostupnou doménu!

1. Výpočetní modely (PDF, slidy na obrazovku)
2. Numerace vyčíslitelných funkcí (PDF, slidy na obrazovku)
3. Vyčíslitelné vlastnosti množin (PDF, slidy na obrazovku)
4. Riceovy věty (PDF, slidy na obrazovku)
5. Metoda redukce (PDF, slidy na obrazovku)
6. Časová složitost výpočtů a modelů (PDF, slidy na obrazovku)
7. Třídy složitosti (PDF, slidy na obrazovku)
8. NP-úplnost problému SAT (PDF, slidy na obrazovku)
9. Vztahy mezi složitostními třídami (PDF, slidy na obrazovku)