Algoritmy a datové struktury

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik. V rámci cvičení se studenti seznamují s použitím vysvětlovaných algoritmů pro řešení praktických problémů. Studenti dále získají základní znalosti o konstrukci a použití konečných automatů, regulárních výrazů, o použití bezkontextových gramatik a konstrukci a použití zásobníkových automatů. Jsou seznámeni s Turingovým strojem a s třídami složitosti P a NP.

Požadavky:

Osnova přednášek:

1.Základní matematické pojmy – množiny, relace, graf, sekvence, strom.

2.Časová a paměťová složitost algoritmů. Příklady na lineární, polynomiální a exponenciální složitost.

3.Základní abstraktní datové typy – fronta, zásobník, tabulka, strom, vyhledávací stromy a jejich vyvažování.

4.Rekurzivní algoritmy a metoda Rozděl a panuj.

5.Algoritmy řazení.

6.Randomizované algoritmy a hešování.

7.Dynamické programování.

8.Minimální kostry grafu.

9.Nejkratší cesty v grafech.

10.Automaty jako modely výpočtů: Formální jazyk, Konečný automat a minimální deterministický konečný automat.

11.Regulární výrazy, základní vlastnosti regulárních formálních jazyků.

12.Zásobníkový automat a základní vlastnosti bezkontextových jazyků.

13.Turingův stroj, rekurzivně-spočetné a rekurzivní jazyky. Třídy P a NP.

Osnova cvičení:

Cvičení sledují témata přednášek.

Cíle studia:

Seznámit studenty se základními i pokročilejšími algoritmy a datovými strukturami. Student také získá základy teorie grafů a nejdůležitějších grafových algoritmů. Cílem je nejen vyučované algoritmy pochopit, ale také být schopen je aplikovat při řešení problémů a umět je modifikovat pro podobné úlohy.

Studijní materiály:

Povinná:

Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, 2022.

Doporučená:

Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2022.

Michael Sipser: Introduction to the Theory of Computation, MIT Přess, 2006.

John Hopcroft, Rajeev Motwani, Jeffrey Ullman: Introduction to Automata Theory, Languages, 2019.

Poznámka:

nutno doplnit

Další informace:

nutno doplnit

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: