Detail předmětu

Matematické základy informatiky

FSI-VZI-A Ak. rok: 2027/2028 Zimní semestr

Předmět poskytuje úvod do matematických a teoretických základů informatiky se zaměřením na formální modely výpočtu, vyčíslitelnost, výpočetní složitost a návrh algoritmů. Cílem je vytvořit systematický základ pro porozumění možnostem a omezením výpočetních metod a pro správnou volbu algoritmických postupů při řešení informatických a technických problémů.

První část předmětu je věnována teorii formálních jazyků a automatů. Studenti se seznámí s deterministickými a nedeterministickými konečnými automaty, regulárními jazyky, regulárními výrazy, bezkontextovými gramatikami, zásobníkovými automaty a Turingovými stroji. Na těchto modelech jsou vysvětleny základní principy formálního popisu výpočtu, rozhodovatelnosti a nerozhodnutelnosti. Následuje úvod do analýzy časové složitosti algoritmů a klasifikace výpočetních problémů, zejména tříd P a NP.

Druhá část předmětu se zabývá návrhem a analýzou klasických algoritmů. Zahrnuje prohledávání grafů, algoritmy pro hledání nejkratších cest, minimálních kosterních stromů, párování a maximálních toků, stejně jako vybrané problémy řešené pomocí hladových algoritmů a dynamického programování. Na konkrétních úlohách jsou demonstrovány principy správnosti algoritmů, jejich výpočetní náročnost a vhodnost použití.

Výuka propojuje matematické modely a teoretické výsledky s jejich praktickou implementací v jazyce Python. V počítačových cvičeních studenti vytvářejí a testují implementace vybraných automatů a algoritmů, analyzují jejich chování a interpretují získané výsledky.

Jazyk výuky

angličtina

Počet kreditů

6

Vstupní znalosti

Předpokládá se znalost základů algoritmizace a strukturovaného programování, zejména práce s proměnnými, datovými typy, podmíněnými příkazy, cykly, funkcemi a základními datovými strukturami.

Student by měl být schopen samostatně sestavit a implementovat jednoduchý algoritmus v jazyce Python nebo obdobném programovacím jazyce, spustit program a ověřit jeho správnost na zvolených vstupních datech.

Z matematických disciplín se předpokládá základní orientace v teorii množin, matematické logice, funkcích a relacích. 

Způsob zakončení předmětu a pravidla hodnocení studentů

Požadavky pro zápočet: Aktivní účast na cvičeních, zpracování zadaného projektu. Zkouška: Písemná a ústní.
Účast na přednáškách i cvičeních je povinná. Zameškaná výuka může být nahrazena zpracováním zadaných úloh.

Učební cíle

Po úspěšném absolvování předmětu student:

  1. Formálně popíše, sestaví a analyzuje deterministické a nedeterministické konečné automaty, určí jimi přijímané jazyky a použije vztahy mezi konečnými automaty, regulárními jazyky a regulárními výrazy při řešení vybraných úloh.

  2. Sestaví a použije bezkontextovou gramatiku nebo zásobníkový automat pro popis jednoduchého formálního jazyka, provede základní syntaktickou analýzu a vysvětlí rozdíly ve vyjadřovací síle vybraných formálních modelů.

  3. Popíše a simuluje výpočetní proces pomocí Turingova stroje, rozliší rozhodnutelné a nerozhodnutelné problémy a na příkladech zdůvodní základní omezení algoritmicky řešitelných úloh.

  4. Analyzuje a porovná časovou složitost vybraných algoritmů pomocí asymptotické notace, rozliší základní charakteristiky tříd P a NP a vysvětlí vztah mezi vlastnostmi problému a výpočetní náročností jeho řešení.

  5. Navrhne, implementuje a zdůvodní správnost vybraných algoritmů pro grafové a kombinatorické problémy s využitím prohledávání grafů, hladových postupů, dynamického programování a síťových algoritmů.

  6. Ověří a experimentálně vyhodnotí implementace vybraných formálních modelů a algoritmů v jazyce Python, navrhne vhodné testovací případy, porovná jejich výpočetní náročnost a posoudí vhodnost použitých postupů.

Studijní opory

Pro podporu studia jsou studentům poskytovány materiály k přednáškám a počítačovým cvičením. Materiály jsou zpřístupňovány prostřednictvím univerzitního e-learningového prostředí. 

Použití předmětu ve studijních plánech

Program N-AIŘ-P: Aplikovaná informatika a řízení, magisterský navazující, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., povinná

Osnova

1. Deterministické konečné automaty.
2. Nedeterministické konečné automaty.
3. Regulární jazyky.
4. Bezkontextové gramatiky.
5. Turingovy stroje.
6. Rozhodovatelnost.
7. Časová složitost, třída P.
8. Třída NP.
9. Algoritmy pro úlohy: Stable matching, Graph connectivity, Topological ordering.
10. Algoritmy pro úlohy: Interval scheduling, Shortest paths, Minimum spanning tree.
11. Algoritmy pro úlohy: Huffman coding, Weighted interval scheduling, Knapsack problem.
12. Algoritmy pro úlohy: Sequence alignment, Maximum flow, Bipartite matching.
13. Shrnutí probírané látky.

Cvičení s počítačovou podporou

26 hod., povinná

Osnova

Cvičení navazují na látku probíranou na přednáškách praktickými ukázkami daných problémů.

1. Deterministické konečné automaty – problém jednoduchého zámku.
2. Nedeterministické konečné automaty – rozpoznávání gest.
3. Regulární jazyky – záznamy událostí (logy).
4. Bezkontextové gramatiky – syntaktická analýza jazyka pro jednoduchého robota.
5. Zásobníkové automaty – záznamy volání.
6. Simulátor Turingova stroje.
7. Zastavení výpočtu v jednoduchém jazyce bajtkódu.
8. Algoritmy řazení a jejich časová složitost.
9. Prohledávání grafů a úplné průchody grafem.
10. Algorithms for problems: Stable matching, Graph connectivity, Topological ordering.
11. Algorithms for problems: Interval scheduling, Shortest paths, Minimum spanning tree.
12. Algorithms for problems: Huffman coding, Weighted interval scheduling, Knapsack problem.
13. Algorithms for problems: Sequence alignment, Maximum flow, Bipartite matching.