B_ADS Algorithms and Data Structures

University of Finance and Administration
Summer 2011
Extent and Intensity
2/2. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
RNDr. Petr Kučera, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Ondřej Čepek, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ivana Plačková
Timetable of Seminar Groups
B_ADS/cAPH: Tue 10:30–11:14 E126, Tue 11:15–12:00 E126, P. Kučera
B_ADS/pAPH: Tue 8:45–9:29 E126, Tue 9:30–10:15 E126, P. Kučera
B_ADS/vAPH: Fri 18. 3. 15:30–17:00 E228, Sat 2. 4. 14:00–15:30 E228, 15:45–17:15 E228, Fri 15. 4. 15:30–17:00 E228, Sat 7. 5. 14:00–15:30 E228, 15:45–17:15 E228, P. Kučera
Prerequisites (in Czech)
Úvod do programování.
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives (in Czech)
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.
Syllabus (in Czech)
  • 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ů.
Literature
  • 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
Assessment methods (in Czech)
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 80%, 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í.
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
Information on the extent and intensity of the course: 12 hodin/semestr.
Teacher's information
http://kti.mff.cuni.cz/~cepek/vyuka.html
The course is also listed under the following terms Winter 2007, Summer 2008, Winter 2008, Summer 2009, Summer 2010, summer 2012, Summer 2013, Summer 2014, Summer 2015, Summer 2016, Summer 2017, Summer 2018, Summer 2019, Summer 2020, Summer 2021, Summer 2022, Summer 2023, Summer 2024, Summer 2025.
  • Enrolment Statistics (Summer 2011, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/summer2011/B_ADS