Zpět

Teoretická informatika

Přednášející: Cvičící: Tutor pro studenty v kombinované formě studia:

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. Výpočetní složitost algoritmů. Asymptotická notace. Analýza složitosti rekurzivních algoritmů.
  3. 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).
  4. Turingovy stroje. 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.
  5. Další třídy složitosti - PSPACE, EXPTIME, EXPSPACE, LOGSPACE, NLOGSPACE. Polynomiální hierarchie.
  6. Algoritmicky nerozhodnutelné problémy. Riceova věta.
  7. Randomizované algoritmy. Aproximační algoritmy.
  8. Výpočetní složitost paralelních algoritmů: výpočetní modely pro paralelní algoritmy (PRAM).
  9. Analýza výpočetní složitosti paralelních algoritmů. Třída NC. Souvislost s obvody (circuit complexity).
  10. Distribuované algoritmy: výpočetní modely pro distribuované algoritmy. Komunikační složitost.
  11. Kolmogorov complexity.
  12. Sémantika programovacích jazyků: formální popis sémantiky (operační sémantika, denotační sémantika).
  13. Metody dokazování korektnosti programů.
  14. Kvantové výpočty.

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 2024/25: referaty.pdf

Poznámka: Podklady k jednotlivým referátům jsou k dispozici v MS Teams v týmu Teoretická informatika 2024/25 v kanálu Obecné pod kartou Soubory 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 2024/2025.
  • 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
    – Třídy složitosti. Nedeterministické algoritmy.
    Slidy: ti-slides-04.pdf

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

  • 6. přednáška
    – Příklady důkazů NP-úplnosti některých problémů.
    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

  • 8. přednáška
    – Třídy L a NL. Logspace redukce. P-úplné problémy.
    Slidy: ti-slides-08.pdf

  • 9. přednáška
    – Paralelní algoritmy.
    Slidy: ti-slides-09.pdf

  • 10. přednáška
    – Distribuované algoritmy.
    Slidy: ti-slides-10.pdf

  • 11. přednáška
    – Řešení výpočetně náročných problémů. Randomizované algoritmy. Aproximační algoritmy.
    Slidy: ti-slides-11.pdf

Slidy z přednášek ze školního roku 2023/2024:
  • 1. přednáška
    – Úvod. Algoritmy a algoritmické problémy. Výpočetní modely (např. stroje RAM, ...). Churchova-Turingova teze.
    Slidy: ti-slides-01.pdf

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

  • 3. přednáška
    – Amortizovaná analýza.
    Slidy: ti-slides-03.pdf

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

  • 5. přednáška
    – Vzájemná simulace mezi různými druhy strojů. Algoritmicky nerozhodnutelné problémy.
    Slidy: ti-slides-05.pdf

  • 6. přednáška
    – Třídy složitosti. Nedeterministické algoritmy. NP-úplné problémy.
    Slidy: ti-slides-06.pdf

  • 7. přednáška
    – Příklady důkazů NP-úplnosti některých problémů.
    Slidy: ti-slides-07.pdf

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

  • 9. přednáška
    – Třídy L a NL. Logspace redukce. P-úplné problémy.
    Slidy: ti-slides-09.pdf

  • 10. přednáška
    – Paralelní algoritmy.
    Slidy: ti-slides-10.pdf

  • 11. přednáška
    – Distribuované algoritmy. Randomizované algoritmy. Aproximační algoritmy.
    Slidy: ti-slides-11.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 2024/2025.

Animace

Průvodce pro kombinované

Tabulka s problémy

Další literatura

Zpět