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 E227, Tue 11:15–12:00 E227, O. Čepek
B_ADS/pAPH: Tue 8:45–9:29 E227, Tue 9:30–10:15 E227, O. Čepek
B_ADS/vAPH: Fri 26. 3. 12:00–13:30 E306, 13:45–15:15 E306, Fri 16. 4. 12:00–13:30 E222, 13:45–15:15 E222, Fri 30. 4. 12:00–13:30 E306, 13:45–15:15 E306, O. Čepek

Prerequisites (in Czech)

Úvod do programování.

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)

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: 12hodin/semestr.

Teacher's information

http://kti.mff.cuni.cz/~cepek/vyuka.html

• Enrolment Statistics (Summer 2010, recent)
  
• Permalink: https://is.vsfs.cz/course/vsfs/summer2010/B_ADS