N_VSA Výpočetní složitost algoritmů

Vysoká škola finanční a správní
zima 2021
Rozsah
2/1/0. 18 hodin KS/semestr. 6 kr. Ukončení: zk.
Vyučující
prof. RNDr. Ondřej Čepek, Ph.D. (cvičící)
Garance
prof. RNDr. Ondřej Čepek, Ph.D.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Ivana Plačková
Rozvrh seminárních/paralelních skupin
N_VSA/vAPH: Pá 15. 10. 14:00–15:30 S22, 15:45–17:15 S22, Pá 5. 11. 14:00–15:30 S22, 15:45–17:15 S22, Pá 19. 11. 14:00–15:30 S22, 15:45–17:15 S22, So 20. 11. 9:45–11:15 E304, 11:30–13:00 E304, 14:00–15:30 E304, O. Čepek
Předpoklady
Základy matematické analýzy, základy diskrétní matematiky, základy programování.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
Studenti získají základní přehled o konceptech spojených s časovou a prostorovou složitostí algoritmů.
Výstupy z učení
Studenti budou po absolvování předmětu schopni:
- analyzovat časovou a prostorovou složitost konkrétních algoritmů s polynomiální složitostí;
- rozpoznat výpočetně obtížné úlohy a zařadit je do správné třídy složitosti;
- dokázat NP-těžkost konkrétních výpočetně obtížných úloh pomocí polynomiálních transformací.
Osnova
  • 1. Definice časové a prostorové složitosti algoritmu, asymptotické notace, příklady použití.
  • 2. Determinismus versus nedeterminismus, příklady nedeterministických algoritmů.
  • 3. Definice tříd P a NP, příklady problémů ze třídy NP.
  • 4. Polynomiální transformace, příklady transformací mezi problémy ze třídy NP.
  • 5. NP-těžkost a NP-úplnost, příklady optimalizačních úloh a rozhodovacích problémů z těchto tříd.
  • 6. Cook-Levinova věta (existence NP-úplného rozhodovacího problému).
  • 7. Silná NP-úplnost, příklady.
  • 8. Pseudopolynomiální algoritmy.
  • 9. Aproximační algoritmy pro NP-těžké optimalizační úlohy.
  • 10. Neaproximovatelnost, příklady neaproximovatelných úloh.
  • 11. Pravděpodobnostní algoritmy typu Las Vegas a Monte Carlo.
  • 12.Prostorová složitost, Savičova věta.
Literatura
    doporučená literatura
  • Černý, Michal. Výpočty, svazky I,II,III. Professional Publishing 2012. ISBN: 978-80-7431-049-2
Výukové metody
Přednáška pokrývající teorii, cvičení na probírání příkladů.
Metody hodnocení
Písemná zkouška.
Informace učitele
http://ktiml.mff.cuni.cz/~cepek/vyuka.html
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 2014, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2022, zima 2023.