FI:IB107 Vyčíslitelnost a složitost - Informace o předmětu

IB107 Vyčíslitelnost a složitost

Rozsah

2/1/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučováno kontaktně

Vyučující

prof. RNDr. Jan Strejček, Ph.D. (přednášející)
Mgr. Paulína Ayaziová (cvičící)
RNDr. Martin Jonáš, Ph.D. (cvičící)
Bc. David Dokoupil (pomocník)
Bc. Ondřej Huvar (pomocník)
RNDr. David Klaška (pomocník)
Mgr. Martin Kurečka (pomocník)
Matúš Miškuf (pomocník)
Bc. Jindřich Sedláček (pomocník)
RNDr. Vojtěch Suchánek (pomocník)
Bc. Jakub Šárník (pomocník)
Bc. Adéla Štěpková (pomocník)

Garance

prof. RNDr. Jan Strejček, Ph.D.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Po 23. 9. až Po 16. 12. Po 10:00–11:50 D1

• Rozvrh seminárních/paralelních skupin:

IB107/A: Čt 26. 9. až Čt 21. 11. Čt 14:00–15:50 C511, Čt 28. 11. až Čt 19. 12. Čt 14:00–15:50 S209, J. Strejček
IB107/02: Út 24. 9. až Út 17. 12. Út 15:00–15:50 A218, J. Strejček
IB107/03: Út 24. 9. až Út 17. 12. Út 13:00–13:50 A218, M. Jonáš
IB107/04: Út 24. 9. až Út 17. 12. Út 12:00–12:50 A218, M. Jonáš
IB107/05: Út 24. 9. až Út 17. 12. Út 16:00–16:50 A218, P. Ayaziová

Předpoklady

IB005 FJA

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

předmět má 36 mateřských oborů, zobrazit

Cíle předmětu

Smyslem kurzu je objasnit základní přístupy a metody klasifikace problémů z hlediska možnosti jejich algoritmického řešení. 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í.
Po skončení kurzu budou studenti schopni: porozumět základním pojmům formalizujícím algoritmickou řešitelnost; zvládnout základní klasifikační techniky problémů (redukce, diagonalizace a uzávěrové vlastnosti); umět tyto techniky aplikovat na jednoduché situace.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- používat asymptotickou notaci, a to jak pasivně, tak i aktivně;
- vysvětlit rozdíl mezi složitostí algoritmu a problému;
- samostatně zařadit konkrétní problém do konkrétní složitostní třídy;
- vyvodit praktické důsledky ze zařazení problému do konkrétní složitostní třídy;
- vysvětlit, že existují problémy, které jsou algoritmicky neřešitelné, a uvést jejich příklady;
- vysvětlit rozdíly mezi různými třídami neřešitelných problému;

Osnova

• Algoritmus jako výpočetní model. Churchova teze.
• Klasifikace problémů. Rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy. Vyčíslitelné funkce.
• Uzávěrové vlastnosti, Riceovy věty.
• 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.

Literatura

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• BOVET, D. a Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
• KFOURY, A. J., Robert N. MOLL a Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info

Výukové metody

přednáška, cvičení, domácí úkoly

Metody hodnocení

Přednáška je doplněna cvičeními. Během semestru jsou studentům zadávány domácí úkoly. Zkouška je písemná s využitím materiálů. Požadavkem k připuštění ke zkoušce je získání daného počtu bodů za domácí úkoly.

Navazující předměty

• IA012 Složitost
• IA046 Vyčíslitelnost

Další komentáře

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

Nachází se v prerekvizitách jiných předmětů

• IB110 Základy informatiky
  !IB005 || !IB107  

• Statistika zápisu (nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2024/IB107