B_ADS Algoritmy a datové struktury

Vysoká škola finanční a správní
léto 2008
Rozsah
2/2. 12hodin/semestr. 6 kr. Ukončení: zk.
Vyučující
prof. RNDr. Ondřej Čepek, Ph.D. (cvičící)
RNDr. Petr Kučera, 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: Lenka Bažantová
Rozvrh seminárních/paralelních skupin
B_ADS/cAPH: Út 15:45–16:29 E304, Út 16:30–17:15 E304, P. Kučera
B_ADS/pAPH: Út 14:00–14:44 E304, Út 14:45–15:30 E304, P. Kučera
B_ADS/vAPH: So 23. 2. 15:45–17:15 E125, So 8. 3. 9:45–11:15 E125, 11:30–13:00 E125, Pá 28. 3. 17:15–18:45 E125, So 12. 4. 14:00–15:30 E125, 15:45–17:15 E125, P. Kučera
Předpoklady
Základy programování, matematické analýzy a lineární algebry.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Anotace js stejná pro všechny formy studia. Cíl kursu. Hlavní náplní přednášky je přehled různých typů algoritmů (sekvenční i paralelní, deterministické i pravděpodobnostní, optimalizační i aproximační). U každého typu jsou probrány příklady konkrétních algoritmů s důrazem na analýzu jejich časové složitosti. Přednáška též pokrývá úvod do výpočetní složitosti: jsou zavedeny třídy P a NP, definována polynomiální převoditelnost problémů a vysvětlena metodika důkazů NP-úplnosti.
Osnova
  • Tato osnova je určena pro prezenční studium, průběh výuky pro kombinované studium je uveden ve studijních materiálech formou metodického listu(ML). 1.přednáška Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami (asymptotická notace), příklady použití asymptotické notace. Opakování jednoduchých třídících algoritmů. Cvičení: Příklady analyzování složitosti konkrétních (třídících) algoritmů. 2.přednáška Algoritmy rozděl a panuj a jejich analýza pomocí řešení rekurentních rovnic. Cvičení: Analýza konkrétních algoritmů: binární vyhledávání, mergesort a quicksort. 3.přednáška Algoritmy rozděl a panuj a jejich analýza (pokračování): hledání mediánu v lineárním čase, Strassenův algoritmus pro násobení matic. Cvičení: Řešení konkrétních rekurentních rovnic, použití Strassenova algoritmu pro obdélníkové matice. 4.přednáška Dolní odhady složitosti sekvenčních algoritmů, rozhodovací stromy (aplikace: dolní odhad pro třídění pomocí porovnávání) Cvičení: Konstrukce rozhodovacích stromů pro konkrétní třídící algoritmy. 5.přednáška Grafové algoritmy:BFS (prohledávání do šířky) a DFS (prohledávání do hloubky), verze pro neorientované i orientované grafy, testování souvislosti grafu. Cvičení: Použití BFS a DFS pro konkrétní grafové problémy (testování bipartitnosti grafu, rozhodnutí o existenci stoku v grafu) 6.přednáška Grafové algoritmy (pokračování): hledání dvousouvislých komponent neorientovaného grafu. Cvičení: Použití probraných grafových algoritmů pro řešení dalších úloh na neorientovaných i orientovaných grafech. 7.přednáška Grafové algoritmy (pokračování): topologické třídění, detekce silně souvislých komponent orientovaného grafu. Cvičení: Použití probraných grafových algoritmů pro řešení dalších úloh na neorientovaných i orientovaných grafech. 8.přednáška Vyhledávání v textu pomocí konečného automatu: algoritmus Aho-Corasicková a jeho analýza. Cvičení: Konstrukce konkrétních vyhledávacích automatů pro různé množiny vyhledávaných vzorků (slov). 9.přednáška Paralelní algoritmy: násobení matic, použití tohoto algoritmu pro testování dosažitelnosti v grafu. Cvičení: Příklady na testování dosažitelnosti pro konkrétní grafy. 10.přednáška Paralelní algoritmy (pokračování): transpoziční a třídící sítě. Cvičení: Konstrukce konkrétní třídící sítě. 11.přednáška Problémy řešitelné deterministicky v polynomiálním čase (třída P), problémy řešitelné nedeterministicky v polynomiálním čase (třída NP), polynomiální převoditelnost. Cvičení: Příklady konkrétních polynomiálních transformací mezi problémy. 12.přednáška NP-úplnost. Definice, důkazové postupy, příklady NP-úplných problémů. Cvičení: Další příklady NP-úplných problémů a důkazy jejich NP-úplnosti. 13.přednáška Aproximační algoritmy. Cvičení: Návrh jednoduchých aproximačních algoritmů.
Literatura
  • Úvod do teoretické informatiky. Praha: MATFYZPRESS, 1998, 123 s. ISBN 80-85863-33-2. info
Metody hodnocení
Vyučující metody: Metody hodnocení: Způsob zakončení: Zkouška, která se provádí písemnou formou. Písemka sestává z několika bodovaných příkladů. Pro každý klasifikační stupeň je stanovano kolik bodů je pro daný stupeň potřeba dosáhnout.
Předmět je zařazen také v obdobích zima 2007, zima 2008, léto 2009, léto 2010, léto 2011, léto 2012, léto 2013, léto 2014, léto 2015, léto 2016, léto 2017, léto 2018, léto 2019, léto 2020, léto 2021, léto 2022, léto 2023, léto 2024, léto 2025.