VSFS:B_ADS Algorithms and Data Structures - Course Information
B_ADS Algorithms and Data Structures
University of Finance and AdministrationSummer 2009
- Extent and Intensity
- 2/2. 5 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- prof. RNDr. Ondřej Čepek, 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: Lenka Bažantová - Timetable of Seminar Groups
- B_ADS/cAPH: Tue 10:30–11:14 E223, Tue 11:15–12:00 E223, O. Čepek
B_ADS/pAPH: Tue 8:45–9:29 E223, Tue 9:30–10:15 E223, O. Čepek
B_ADS/vAPH: Fri 27. 3. 12:00–13:30 E224, 13:45–15:15 E224, Fri 24. 4. 12:00–13:30 E222, 13:45–15:15 E222, Fri 15. 5. 12:00–13:30 E123, 13:45–15:15 E123, O. Čepek - Prerequisites (in Czech)
- Základy programování, matematické analýzy a lineární algebry.
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Applied Informatics (programme VSFS, B-INF) (2)
- Applied Informatics (programme VSFS, B-INF, specialization Manažerská informatika)
- Applied Informatics (programme VSFS, B-INF, specialization Software Systems)
- Course objectives (in Czech)
- 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.
- 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é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ů.
- Literature
- Úvod do teoretické informatiky. Praha: MATFYZPRESS, 1998, 123 pp. ISBN 80-85863-33-2. info
- Assessment methods (in Czech)
- 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.
- 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: 12hodin/semestr.
- Enrolment Statistics (Summer 2009, recent)
- Permalink: https://is.vsfs.cz/course/vsfs/summer2009/B_ADS