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

Po dvou letech výukových videí budou letos probíhat prezenční přednášky. Výuková videa budou nadále dostupná v učebních materiálech a vzhledem k jejich existenci nebudou zveřejňovány záznamy z přednášek. Na přednáškách budeme využívat "řídké" (nekompletní) slajdy, které budou taktéž k dispozici a které můžete použít pro vepisování vlastních poznámek z přednášky.

Cvičení budou probíhat prezenčně. 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ů). Cvičení rozvrhovaná před první přednáškou (tedy všechna cvičení rozvrhovaná na 12. a 13. října) odpadnou. Na cvičení si prosím noste (fyzicky či elektornicky) výše odkazovanou sbírku příkladů a (fyzické či virtuální) psací potřeby.

Jakékoliv dotazy k předmětu je možné pokládat 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:

počet bodů	hodnocení
90 a více	A
alespoň 80 a méně než 90	B
alespoň 70 a méně než 80	C
alespoň 60 a méně než 70	D
alespoň 50 a méně než 60	E

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.