B_ADS Algoritmy a datové struktury

Vysoká škola finanční a správní
léto 2020
Rozsah
2/2. 14 hodin KS/semestr. 6 kr. Ukončení: zk.
Vyučující
RNDr. Petr Tesař, 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: Po 17:30–18:14 E223, Po 18:15–19:00 E223, P. Tesař
B_ADS/pAPH: Po 15:45–16:29 E223, Po 16:30–17:15 E223, P. Tesař
B_ADS/vAPH: Pá 13. 3. 15:45–17:15 E227, Pá 27. 3. 14:00–15:30 E128, 15:45–17:15 E128, So 18. 4. 14:00–15:30 E228, 15:45–17:15 E228, Pá 24. 4. 14:00–15:30 E228, 15:45–17:15 E228, P. Tesař
Předpoklady
Tento předmět nemá žádné předpoklady.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
Cílem předmětu je dát posluchačům přehled o běžných typech algoritmů a seznámit je se základy teorie výpočetní složitosti.
Posluchači porozumí problematice různých typů algoritmů (sekvenčních i paralelních, deterministických i pravděpodobnostních, optimalizačních i aproximačních). 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.
Výstupy z učení
Studenti budou po absolvování předmětu schopni:
- navrhnout efektivní implementaci jednoduchých algoritmů s polynomiální časovou složitostí;
- navrhnout datové struktury pro efektivní implementaci algoritmů s polynomiální časovou složitostí;
- analyzovat časovou a prostorovou složitost konkrétních algoritmů s polynomiální složitostí;
- rozpoznat výpočetně obtížné úlohy.
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 Přehled definic pojmů, datové struktury, prostředky pro popis složitosti algoritmů, příklad výpočtu složitosti algoritmu.
  • 2.přednáška Množiny – definice, grafy – definice.
  • 3.přednáška Složitost aritmetických operací, jednoduché třídící algoritmy, složité třídící algoritmy nezaložené na principu rozděl a panuj.
  • 4.přednáška Algoritmy rozděl a panuj, řešení rekurentních rovnic, algoritmy rozděl a panuj pro vyhledávání, třídění a aritmetiku , Strassenův algoritmus pro násobení matic.
  • 5.přednáška Vyhledávání v textu pomocí konečného automatu - algoritmus Aho-Corasicková a jeho analýza.
  • 6.přednáška Grafové algoritmy BFS (prohledávání do šířky), grafové algoritmy DFS (prohledávání do hloubky), testování souvislosti grafu., grafové algoritmy - hledání souvislých komponent neorientovaného grafu.
  • 7.přednáška Grafové algoritmy (pokračování): topologické třídění, detekce silně souvislých komponent orientovaného grafu.
  • 8.přednáška Grafové algoritmy - extremální úlohy
  • 9.přednáška Paralelní algoritmy - násobení matic na abstraktním paralelním stroji PRAM, testování dosažielnosti v grafu.
  • 10.přednáška Paralelní algoritmy (pokračování): transpoziční a třídící sítě. Grafové algoritmy - minimální kostra grafu
  • 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), NP-úplné problémy. polynomiální převoditelnost.
  • 12.přednáška Aproximační algoritmy.
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
Výukové metody
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).
Metody hodnocení
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 2012, léto 2013, léto 2014, léto 2015, léto 2016, léto 2017, léto 2018, léto 2019, léto 2021, léto 2022, léto 2023, léto 2024, léto 2025.