Sylabus

• Algoritmus jako výpočetní model. Churchova teze.
  
• Vyčíslitelné funkce a jejich numerace.
  
• Vyčíslitelné vlastnosti množin a rozhodnutelnost problémů.
• Uzávěrové vlastnosti, Riceovy věty.
• Redukce.
  
• Časová a prostorová složitost algoritmů a problémů.
  
• Základní složitostní třídy.
  
• Polynomiální redukce a úplnost v třídách problémů.
  
• NP-úplné problémy.

Literatura

Výuka se bude opírat o tři základní texty: skripta prof. Brima o Vyčíslitelnosti, skripta téhož autora o Složitosti, a dále o sbírku příkladů.

Ke studiu lze využít i následující literaturu.

• 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

Jako bonus přidáváme odkaz na pěkné motivační video.

Výuka

Vzhledem k platným omezením a horšící se situaci prezenční přednášky nebudou. V prvním týdnu v úterý 14. 9. 2021 od 10:00 proběhne úvodní část přednášky věnovaná organizačním záležitostem formou videokonference v MS Teams (odkaz naleznete v ISu). Tato přednáška bude nahrávána a záznam bude následně zveřejněný. Vlastní učivo bude prezentováno v 11-12 blocích. Každý blok bude obsahovat několik kratších videí. Videa budou využívat "řídké" slajdy, které také budou k dispozici.

V dalších týdnech budou vždy v úterý od 10:00 probíhat online konzultační hodiny přes MS Teams, kde můžete klást dotazy k učivu nebo k předmětu obecně.

Cvičení budou probíhat prezenčně (alespoň prozatím). Na všech skupinách se budou cvičit stejné příklady. Skupina IB107/A bude klást více důrazu na samostatnou práci (a je proto nevhodná pro studenty, kteří preferují společné řešení příkladů). V pondělí 13. 9. 2021 cvičení nebudou.

Jakékoliv dotazy k předmětu je možné pokládat také v diskusním fóru předmětu, které budou vyučující sledovat.

Domácí úkoly

Během semestru zadáme tři domácí úkoly (přibližně na konci první, druhé a třetí čtvrtiny semestru). Z každého úkolu bude možné získat až 6 bodů. Úkoly nebudou povinné, ale k úspešnému absolvování bude třeba získat z úkolů alespoň 9 bodů. Body získané z úkolů nad tuto hranici slouží jako tzv. měkké body a mohou vylepšit známku v připadě úspěšného absolvování předmětu.

Hodnocení

V předmětu nebude žádná vnitrosemestrální písemka, pouze závěrečná zkoušková písemka. Na tuto písemku mohou přijít pouze studenti, kteří z domácích úkolů získají alespoň 9 bodů. Písemka bude na 100 bodů. Kdo z písemky získá méně než 50 bodů, dostane hodnocení F. Kdo z písemky získá alespoň 50 bodů, tomu se přičtou měkké body z domácích úkolů a známka se určí dle následující tabulky:

Studenti, kteří si zvolí ukončení předmětu zápočtem (zdaleka ne všechny studijní programy tuto volbu umožňují), musí taktéž získat z domácích úkolů alespoň 9 bodů. Body z domácích úkolů získaných nad tuto hranici se jim však přičtou k bodům ze závěrečné písemky automaticky. Pro získání zápočtu musí součet těchto bodů být alespoň 50.