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

Vysoká škola finanční a správní
zima 2023
Rozsah
2/1/0. 18 hodin KS/semestr. 6 kr. Ukončení: zk.
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á
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 2021, zima 2022.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.vsfs.cz/predmet/vsfs/zima2023/N_VSA