Detail předmětu

Diskrétní matematika

FP-dimPAk. rok: 2026/2027

Základní teoretické prostředky aplikované informatiky - matematická logika, relace, teorie grafů a teorie formálních jazyků a automatů. Zvládnutí těchto metod posluchačům umožní hlubší proniknutí do jejich oboru a efektivnější využívání výpočetní techniky při řešení konkrétních problémů.

Jazyk výuky

čeština

Počet kreditů

4

Garant předmětu

Mgr. Martina Bobalová, Ph.D.

Zajišťuje ústav

Ústav informatiky (ÚI)

Vstupní znalosti

Středoškolská matematika. Matematika 1.

Pravidla hodnocení a ukončení předmětu

Požadavky pro udělení zápočtu:
Absolvování kontrolních testů a dosažení alespoň 50 % bodů nebo absolvování souhrnné písemné práce a dosažení alespoň 50 % bodů. U všech úloh musí být zapsán výpočet, nebo popsaný postup nebo musí být výsledek odůvodněn slovně. 
Zakončení předmětu pro studenty s individuálním studiem:
Absolvování souhrnného kontrolního testu a dosažení alespoň 50 % bodů. U všech úloh písemné části musí být zapsán výpočet, nebo popsaný postup nebo musí být výsledek odůvodněn slovně. Termíny pro zakončení předmětu se domlouvají individuálně dle odmínek schválených v ISP.

Účast na cvičeních je kontrolována.

Učební cíle

Cílem předmětu je seznámit se se základními pojmy a vztahy matematické logiky, relací, teorie grafů a principy teorie jazyků a automatů, s možnostmi jejich aplikací v oboru.

Studijní opory

Viz literatura

Základní literatura

MEZNÍK, Ivan, 2013. Diskrétní matematika pro užitou informatiku. Vyd. 2., rozš. Brno: Vysoké učení technické v Brně, Fakulta podnikatelská. ISBN 978-80-214-4761-5. (CS)

Doporučená literatura

MATOUŠEK, Jiří a NEŠETŘIL, Jaroslav, 2022. Kapitoly z diskrétní matematiky. ISBN 8024650843. (CS)
ROSEN, Kenneth H., [2019]. Discrete mathematics and its applications. Eighth edition. New York: McGraw-Hill education. ISBN 9781260091991. (EN)
TOURLAKIS, George, 2025. Discrete Mathematics. Springer International Publishing. ISBN 9783031304903. (EN)

Zařazení předmětu ve studijních plánech

  • Program BAK-MIn bakalářský 1 ročník, letní semestr, povinně volitelný

Typ (způsob) výuky

 

Přednáška

13 hod., nepovinná

Vyučující / Lektor

Mgr. Martina Bobalová, Ph.D.

Osnova

1. Matematická logika - zákony výrokové logiky, Booleovy funkce, logické obvody.
2. Relace - relace na množině, vlastnosti a typy relací.
3. Teorie grafů - základní druhy grafů, základní poznatky o neorientovaných grafech.
4. Teorie grafů - orientované grafy, ohodnocené grafy, Dijkstrův algoritmus nejkratší cesty, Kruskalův algoritmus.
5. Jazyky, gramatiky - pojem jazyka a gramatiky, Chomského hierarchie.
6. Automaty - konečný automat, Kleeneho charakterizace.
7. Shrnutí

Cvičení

26 hod., povinná

Vyučující / Lektor

Mgr. Martina Bobalová, Ph.D.

Osnova

1. Matematická logika - zákony výrokové logiky. 
2. Matematická logika - Booleovy funkce, logické obvody.
3. Relace - relace na množině.
4. Relace -  vlastnosti a typy relací.
5. Teorie grafů - základní druhy grafů.
6. Teorie grafů - základní poznatky o neorientovaných grafech.
7. Teorie grafů - orientované grafy, ohodnocené grafy.
8. Teorie grafů - Dijkstrův algoritmus nejkratší cesty, Kruskalův algoritmus.
9. Jazyky, gramatiky - pojem jazyka a gramatiky.
10. Jazyky, gramatiky - Chomského hierarchie.
11. Automaty - konečný automat.
12. Automaty - Kleeneho charakterizace.
13. Shrnutí

Odborné znalosti:
Student má ucelené znalosti základů matematické logiky, relací a teorie grafů. Rozumí principům formálních jazyků, gramatik, konečných automatů a jejich vzájemným vztahům. Zná základní algoritmy teorie grafů a jejich teoretické pozadí.

Odborné dovednosti:
Student je schopen aplikovat poznatky matematické logiky a relací při řešení formálně definovaných úloh. Dokáže modelovat problémy pomocí grafů a využívat základní grafové algoritmy k jejich řešení. Umí pracovat s formálními jazyky, gramatikami a konečnými automaty v jednoduchých úlohách.

Obecné způsobilosti:
Student rozvíjí schopnost logického, abstraktního a algoritmického myšlení. Je schopen samostatně analyzovat problém a zvolit vhodný formální model jeho řešení. Získané znalosti dokáže využít jako teoretický základ pro další studium informatiky a příbuzných oborů.



Samostudium

35 hod., nepovinná

Vyučující / Lektor

Mgr. Martina Bobalová, Ph.D.

Individuální příprava na ukončení

30 hod., nepovinná

Vyučující / Lektor

Mgr. Martina Bobalová, Ph.D.