FI:IB107 Vyčíslitelnost a složitost - Informace o předmětu
IB107 Vyčíslitelnost a složitost
Fakulta informatikypodzim 2020
- Rozsah
- 2/1/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
- Vyučující
- prof. RNDr. Jan Strejček, Ph.D. (přednášející)
Mgr. Marek Jankola (cvičící)
doc. RNDr. Petr Novotný, Ph.D. (cvičící)
RNDr. Samuel Pastva, Ph.D. (cvičící)
Zbyněk Cincibus (pomocník)
Mgr. Adam Kabela, Ph.D. (pomocník)
Mgr. Juraj Major (pomocník)
RNDr. Kristýna Pekárková (pomocník)
RNDr. Vojtěch Suchánek (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
- St 12:00–13:50 D3
- Rozvrh seminárních/paralelních skupin:
IB107/01: Po 10:00–10:50 A218, M. Jankola, J. Strejček
IB107/02: Po 16:00–16:50 A320, M. Jankola, S. Pastva
IB107/03: St 16:00–16:50 C525, P. Novotný, S. Pastva - Předpoklady
- IB005 FJA || IB102 Automaty a gramatiky
- 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
- Analýza a zpracování obrazu (program FI, N-VIZ)
- Aplikovaná informatika (program FI, B-AP)
- Bioinformatika a systémová biologie (program FI, N-UIZD)
- Bioinformatika (program FI, B-AP)
- Computer Games Development (program FI, N-VIZ_A)
- Computer Graphics and Visualisation (program FI, N-VIZ_A)
- Computer Networks and Communications (program FI, N-PSKB_A)
- Cybersecurity Management (program FI, N-RSSS_A)
- Formální analýza počítačových systémů (program FI, N-TEI)
- Grafický design (program FI, N-VIZ)
- Graphic Design (program FI, N-VIZ_A)
- Hardware Systems (program FI, N-PSKB_A)
- Hardwarové systémy (program FI, N-PSKB)
- Image Processing and Analysis (program FI, N-VIZ_A)
- Informační bezpečnost (program FI, N-PSKB)
- Informatika a druhý obor (program FI, B-BI)
- Informatika a druhý obor (program FI, B-EB)
- Informatika a druhý obor (program FI, B-FY)
- Informatika a druhý obor (program FI, B-GE)
- Informatika a druhý obor (program FI, B-GK)
- Informatika a druhý obor (program FI, B-CH)
- Informatika a druhý obor (program FI, B-IO)
- Informatika a druhý obor (program FI, B-MA)
- Informatika a druhý obor (program FI, B-SO)
- Informatika a druhý obor (program FI, B-TV)
- Informatika (program FI, B-IN)
- Informatika (program FI, B-INF) (2)
- Informatika ve vzdělávání (program FI, B-IVV) (2)
- Information Security (program FI, N-PSKB_A)
- Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
- Matematická informatika (program FI, B-IN)
- Paralelní a distribuované systémy (program FI, B-IN)
- Počítačová grafika a vizualizace (program FI, N-VIZ)
- Počítačová grafika a zpracování obrazu (program FI, B-IN)
- Počítačové sítě a komunikace (program FI, B-IN)
- Počítačové sítě a komunikace (program FI, N-PSKB)
- Počítačové systémy a zpracování dat (program FI, B-IN)
- Principy programovacích jazyků (program FI, N-TEI)
- Programování a vývoj aplikací (program FI, B-PVA)
- Programovatelné technické struktury (program FI, B-IN)
- Programovatelné technické struktury (program FI, N-IN)
- Řízení kyberbezpečnosti (program FI, N-RSSS)
- Řízení vývoje služeb (program FI, N-RSSS)
- Řízení vývoje softwarových systémů (program FI, N-RSSS)
- Services Development Management (program FI, N-RSSS_A)
- Služby - výzkum, řízení a inovace (program FI, N-AP)
- Sociální informatika (program FI, B-AP)
- Software Systems Development Management (program FI, N-RSSS_A)
- Software Systems (program FI, N-PSKB_A)
- Softwarové systémy (program FI, N-PSKB)
- Strojové učení a umělá inteligence (program FI, N-UIZD)
- Učitel informatiky a správce sítě (program FI, N-UCI)
- Učitelství informatiky pro střední školy (program FI, N-UCI) (2)
- Umělá inteligence a zpracování přirozeného jazyka (program FI, B-IN)
- Vývoj počítačových her (program FI, N-VIZ)
- Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
- Zpracování přirozeného jazyka (program FI, N-UIZD)
- 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í 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í.
Po skončení kurzu budou studenti schopni: 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. - 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é; 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 povinnými cvičeními. Během semestru jsou studentům zadávány domácí úkoly. Zkouška je písemná. Požadavkem k připuštění ke zkoušce je získání daného počtu bodů za domácí úkoly. Tyto body se rovněž započítavájí do celkového hodnocení. Pomocné materiály nejsou při zkoušce povoleny.
- Navazující předměty
- 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ů
- Statistika zápisu (podzim 2020, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2020/IB107