Zpět

Teoretická informatika

Přednášející: Cvičící:

Aktuální informace

Náplň předmětu

Cílem předmětu je seznámit studenty se základy některých oblastí teoretické informatiky, zejména oblasti týkající se algoritmů a výpočetní složiti. Po absolvování předmětu by tak studenti měli získat určitou představu o tom, jakými druhy problémů se teoretická informatika jako obor zaobírá.

Předběžný program přednášek:

  1. Úvod. Algoritmy a algoritmické problémy. Výpočetní modely (např. stroje RAM, ...). Churchova-Turingova teze.
  2. Algoritmicky nerozhodnutelné problémy. Riceova věta.
  3. Výpočetní složitost algoritmů. Asymptotická notace. Analýza složitosti rekurzivních algoritmů.
  4. Pokročilejší techniky analýzy a návrhu algoritmů: amortizovaná analýza, složitost algoritmů v průměrném případě (pravděpodobnostní analýza).
  5. Výpočetní složitost problémů. Třídy složitosti. Třídy P a NP. Redukce mezi problémy. NP-úplnost. Některé klasické NP-úplné problémy.
  6. Další třídy složitosti - PSPACE, EXPTIME, EXPSPACE, LOGSPACE, NLOGSPACE.
  7. Výpočetní složitost paralelních algoritmů: výpočetní modely pro paralelní algoritmy (PRAM).
  8. Analýza výpočetní složitosti paralelních algoritmů. Třída NC.
  9. Distribuované algoritmy: výpočetní modely pro distribuované algoritmy. Komunikační složitost.
  10. Randomizované algoritmy. Aproximační algoritmy.

Požadavky na zápočet

Referát

V průběhu semestru budou zveřejněna zadání témat referátů a každému studentovi bude přiděleno jedno z těchto témat.

Pro získání zápočtu je nutné zpracovat referát v písemné formě a prezentovat referát vyučujícímu. Při této prezentaci je třeba prokázat porozumění příslušné problematice. Konkrétní termín prezentace referátů bude stanoven v průběhu semestru.

Za referát je možné získat až 15 bodů. Pro úspěšné zvládnutí referátu je nutné získat minimálně 5 bodů.

Pokud student nezíská při prezentaci referátu minimální počet 5 bodů, bude možné prezentaci ještě jednou opakovat, ovšem již jen za maximálně 10 bodů, přičemž je nutné získat alespoň 1 bod

Zadání referátů pro školní rok 2026/27: referaty.pdf

Poznámka: Podklady k jednotlivým referátům jsou k dispozici v MS Teams v týmu Teoretická informatika 2026/27 v kanálu Obecné pod kartou Sdíleno ve složce Dokumenty / General / Referáty / Podklady.

Písemka

V průběhu semestru se bude psát zápočtová písemka, za kterou bude možno získat až 20 bodů, přičemž minimem nutným pro získání zápočtu je 10 bodů.

Zápočtová písemka se bude psát na některém ze cvičení. Konkrétní datum bude v průběhu semestru ještě upřesněno.

Pro studenty, kteří ze závažných důvodů (např. nemoc) nemohli písemku psát, bude vypsán náhradní termín.

Studenti, kteří ze zápočtové písemky nezískají potřebných 10 bodů, budou mít možnost získat body na zápočet v opravné písemce. Opravná písemka však bude jen za 17 bodů, ze kterých stále bude nutné získat minimálně 10 bodů. (Body na zápočet budou v tom případě počítány podle opravné písemky.)

Celkově je třeba z referátu a zápočtové písemky získat v součtu minimálně 15 bodů.

Zkouška

Za zkoušku bude možné získat až 65 bodů. Zkouška bude probíhat písemnou formou.

Pro absolvolvování zkoušky je nutné získat ze zkouškové písemky minimálně 25 bodů.

Materiály

Výukový text

Slidy z přednášek

Zde se budou v průběhu semestru postupně objevovat slidy z přednášek pro školní rok 2026/2027.
  • 1. přednáška
    – Úvod. Algoritmy a algoritmické problémy. Výpočetní modely (např. stroje RAM a Turingovy stroje). Churchova-Turingova teze.
    Slidy: ti-slides-01.pdf

  • 2. přednáška
    – Algoritmicky nerozhodnutelné problémy. Částečně rozhodnutelné problémy. Příklady důkazů nerozhodnutelnosti problémů. Riceova věta.
    Slidy: ti-slides-02.pdf

  • 3. přednáška
    – Výpočetní složitost algoritmů. Asymptotická notace. Analýza složitosti rekurzivních algoritmů.
    Slidy: ti-slides-03.pdf

  • 4. přednáška
    – Amortizovaná analýza. Složitost algoritmů v průměrném případě.
    Slidy: ti-slides-04.pdf

  • 5. přednáška
    – Třídy složitosti. Nedeterministické algoritmy.
    Slidy: ti-slides-05.pdf

  • 6. přednáška
    – NP-úplné problémy.
    Slidy: ti-slides-06.pdf

  • 7. přednáška
    – Úplné problémy pro další třídy složitosti. Třída PSPACE. PSPACE-úplné problémy. Hry.
    Slidy: ti-slides-07.pdf

Zadání příkladů na cvičení

Zde se budou v průběhu semestru postupně objevovat zadání příkladů na cvičení pro školní rok 2026/2027.

Animace

Tabulka s problémy

Další literatura

Zpět