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

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

Vysoká škola finanční a správní
zima 2017

Rozsah

2/1. 10 hodin KS/semestr. 6 kr. Ukončení: zk.

Vyučující

prof. RNDr. Ondřej Čepek, Ph.D. (cvičící)

Garance

Rozvrh seminárních/paralelních skupin

N_VSA/vAPH: Pá 6. 10. 17:30–19:00 S14, 19:15–20:45 S14, Pá 20. 10. 14:00–15:30 S14, Pá 3. 11. 17:30–19:00 S14, 19:15–20:45 S14, 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ů.

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

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í.