Detail předmětu

Metody diskrétní matematiky

FSI-SDMAk. rok: 2021/2022

Předmět Metody diskrétní matematiky seznamuje studenty se základními oblastmi teorie množin, diskrétní matematiky a aplikované algebry. První oblastí jsou relace mezi množinami a na množině s důrazem na upořádané množiny. Další oblast zahrnuje axion výběru a kardinální a ordinální čísla. Poté je pozornost věnována teorii svazů, přičemž hlavní důraz je kladen na Booleovy algebry. Pak následuje algebraická teorie automatů a formálních jazyků. Poslední oblastí je pak úvod do teorie kódování. Ve všech oblastech se tedy jedná o poznatky tvořící teoretické základy informatiky. Vzhledem k rozvoji využití vypočetní techniky ve všech inženýrských odvětvích jsou získané vědomosti pro absolventy oboru matematické inženýrství nezbytné.

Jazyk výuky

čeština

Počet kreditů

6

Garant předmětu

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

Ústav matematiky (ÚM)

Výsledky učení předmětu

V kurzu získají studenti základní znalosti o chování uspořádaných mno-
žin a svazů, zejména Booleových algeber. Naučí se minimalizovat boole-
ovské funkce a realizovat je logickými obvody. Dále se seznámí s nej-
častejšími typy konečných automatů a s jejich vlastnostmi, s regulární-
mi jazyky a s problémem determinismu. Nakonec pak také získají předsta-
vu o základních problémech spojených s kódováním a dekódováním
zpráv.

Prerekvizity

Předpokládá se pouze středoškolská znalost teorie množin.

Plánované vzdělávací činnosti a výukové metody

Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách formou řešení problémů a cvičení.

Způsob a kritéria hodnocení

Podmínkou pro zápočet je aktivní účast ve cvičeních a prokázání znalostí
při písemných testech, které budou průběžně konány. V písemné části
zkoušky je třeba prokázat schopnost řešit zadaný problém na základě
získaných vědomostí, v její ústní části pan zvládnutí probrané teorie.

Učební cíle

Cílem předmětu je seznámit studenty s obvyklými metodami diskrétní matematiky užívanými v nejrůznějších aplikacích, např. v informatice při konstrukci a popisu činnosti počítače a při přenosu informace. Absolvováním kurzu získají studenti další důkaz toho, že vedle spojité matematiky je také matematika diskrétní základní vědní disciplínou, jejíž zvládnutí je nutným předpokladem pro úspěšnou tvůrčí činnost inženýra.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Cvičení jsou povinná a vyučující bude pravidelně kontrolovat účast. V případě omluvené nepřítomnosti budou studentovi zadány příklady tak, aby se mohl zameškanou látku doučit.

Základní literatura

A.D.Polimeni and H.J.Straight, Foundations of Discrete Mathematics, Brooks/Cole Publ. Comp., Pacific Grove, California, 1990. (EN)
D.R.Hankerson at al.: Coding Theory and Cryptography, Marcel Dekker, Inc., New York -Basel, 2000. (EN)
M.Piff, Discrete Mathematics, Cambridge Univ. Press, 1991. (EN)
N.L.Biggs, Discrete Mathematics, Oxford Univ. Press, 1999. (EN)
Steven Roman, Lattices and Ordered Sets, Springer, 2008. (EN)

Doporučená literatura

F. Preparata, R. Yeh: Úvod do teórie diskrétnych matematických štruktúr, Alfa, Bratislava, 1982.
J. Kopka: Svazy a Booleovy algebry, Univerzita J.E.Purkyně v Ústí nad Labem, 1991.
M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL, Praha, 1990.
M.Novotný, S algebrou od jazyka ke gramatice a zpět, Academia, Praha, 1988.

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

  • Program B-MAI-P bakalářský 2 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

Osnova

1. Relace mezi množinami a na množině
2. Tolerance, ekvivalence, předuspořádání a uspořádání
3. Uspořádané množiny
4. Axiom výběru a věty s ním ekvivalentní
5. Ordinální a kardinální čísla
6. Svazy, ireducibilita, ideály a filtry
7. Booleovy svazy a funkce, aplikace
8. Úplné svazy, uzávěrové operátory
9. Galoisova konexe, Dedekind-MacNeillovo zúplnění
10.Formální jazyky
11.Konečné automaty
12.Gramatiky
13.Samoopravné kódy

Cvičení

26 hod., povinná

Vyučující / Lektor

Mgr. Jan Pavlík, Ph.D.

Osnova

1. Relace mezi množinami a na množině
2. Tolerance, ekvivalence, předuspořádání a uspořádání
3. Uspořádané množiny
4. Axiom výběru a věty s ním ekvivalentní
5. Ordinální a kardinální čísla
6. Svazy, ireducibilita, ideály a filtry
7. Booleovy svazy a funkce, aplikace
8. Úplné svazy, uzávěrové operátory
9. Galoisova konexe, Dedekind-MacNeillovo zúplnění
10.Formální jazyky
11.Konečné automaty
12.Gramatiky
13.Samoopravné kódy