B_ADS Algoritmy a datové struktury

Vysoká škola finanční a správní
léto 2012
Rozsah
2/2. 12 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
B_ADS/cAPH: Út 10:30–11:14 E228, Út 11:15–12:00 E228, O. Čepek
B_ADS/pAPH: Út 8:45–9:29 E228, Út 9:30–10:15 E228, O. Čepek
B_ADS/vAPH: Pá 30. 3. 12:00–13:30 E227, 13:45–15:15 E227, 15:30–17:00 E227, So 21. 4. 14:00–15:30 E227, 15:45–17:15 E227, Pá 4. 5. 13:45–15:15 E227, O. Čepek
Předpoklady
Úvod do 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
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.
Cíl předmětu: cílem předmětu je dát studentům přehled o běžných typech algoritmů a seznámit je se základy teorie výpočetní složitosti. Cíl předmětu platí i pro kombinované studium.
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ých listů (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 (pokračování): transpoziční a třídící sítě. Cvičení: Konstrukce konkrétní třídící sítě.
  • 10.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.
  • 11.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.
  • 12.přednáška Aproximační algoritmy. Cvičení: Návrh jednoduchých aproximačních algoritmů.
Literatura
  • Povinná literatura
  • A.Koubková, J.Pavelka: Úvod do teoretické informatiky, Matfyzpress 1998 (aktualizované vydání 2003), ISBN: 80-85863-33-2
  • Doporučená literatura
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd. Ed., MIT Press/McGraw Hill, 2001. ISBN: 0-262-03293-7
  • Další zdroje
  • www.vsfs.cz/knihovna
  • www.knihovna.vsfs.cz/info/volne_eiz.html
  • IS VŠFS → osobní administrativa → ProQuest
Metody hodnocení
Typ výuky: Výuka probíhá formou přednášek a cvičení v prezenčním studiu a formou řízených skupinových konzultací v kombinovaném studiu.
Rozsah povinné účasti ve výuce: Minimální povinná účast na cvičení v prezenčním studiu je 75%, na řízených skupinových konzultacích v kombinovaném studiu 50%. Studentům, kteří nesplní povinný rozsah účasti, mohou být v průběhu semestru zadány dodatečné studijní povinnosti (v míře, která umožní prokázat studijní výsledky a získané kompetence nezbytné pro úspěšné zakončení předmětu).
Způsob zakončení předmětu: Předmět je zakončen zápočtem a zkouškou. Zkouška probíhá písemnou formou a na její napsání je k dispozici 90 minut. Zápočet osvědčuje splnění stanovených studijních povinností.
Informace učitele
http://kti.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 2007, léto 2008, zima 2008, léto 2009, léto 2010, léto 2011, 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.