VSFS:N_VSA Výpočetní složitost algoritmů - Informace o předmětu
N_VSA Výpočetní složitost algoritmů
Vysoká škola finanční a správnízima 2015
- Rozsah
- 2/1. 10 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: Ing. Barbora Ptáč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ů.
- 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
- Michal Černý. Výpočty. Třídílná monografie vydaná VŠE.
- Výukové metody
- Přednáška pokrývající teorii, cvičení na probírání příkladů.
- Metody hodnocení
- Písemná zkouška.
- Další komentáře
- Předmět je dovoleno ukončit i mimo zkouškové období.
- Statistika zápisu (zima 2015, nejnovější)
- Permalink: https://is.vsfs.cz/predmet/vsfs/zima2015/N_VSA