Vysoká škola finanční a správní

Garance

prof. RNDr. Ondřej Čepek, Ph.D.

Vyučující

prof. RNDr. Ondřej Čepek, Ph.D. (cvičící)

Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní Kontaktní osoba: Ivana Plačková

Osnova

Poradie	Téma prednášky
1.prednáška	Přehled definic pojmů, datové struktury, prostředky pro popis složitosti algoritmů, příklad výpočtu složitosti algoritmu.
2.prednáška	Složitost aritmetických operací, jednoduché třídící algoritmy, složité třídící algoritmy.
3.prednáška	Vyhledávání v textu pomocí konečného automatu - algoritmus Aho-Corasicková a jeho analýza.
4.prednáška	Algoritmy rozděl a panuj, řešení rekurentních rovnic, hledání mediánu v lineárním čase, Strassenův algoritmus pro násobení matic.
5.prednáška	Množiny – definice, grafy – definice.
6.prednáš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í dvousouvislých komponent neorientovaného grafu.
7.prednáška	Grafové algoritmy (pokračování): topologické třídění, detekce silně souvislých komponent orientovaného grafu.
8.prednáška	Stromové struktury, rozhodovací stromy
9.prednáška	Paralelní algoritmy - násobení matic na abstraktním paralelním stroji PRAM, testování dosažielnosti v grafu.
10.prednáška	Paralelní algoritmy (pokračování): transpoziční a třídící sítě.
11.prednáš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.prednáška	Aproximační algoritmy.