VSFS:B_ADS Algorithms and Data Structures - Course Information

B_ADS Algorithms and Data Structures

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