Detail předmětu

Metody diskrétní matematiky

FSI-SDMAk. rok: 2024/2025

Předmět Metody diskrétní matematiky seznamuje studenty se základními poznatky z teorie množin, diskrétní matematiky a aplikované algebry. Nejprve jsou studovány relace mezi množinami a na množině s důrazem na ekvivalence a upořádané množiny. Pak je pozornost věnována axiomu výběru a kardinálním a ordinálním číslům. Poté následuje výklad teorie svazů, přičemž hlavní důraz je kladen na Booleovy algebry. Následuje algebraická teorie automatů a formálních jazyků. V poslední části je probírán úvod do teorie kódování. Náplní předmětu jsou tedy témata, která 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

Zajišťuje ústav

Vstupní znalosti

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

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

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 prokázat zvládnutí probrané teorie.


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.

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 v matematice i mimo ni, 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 nové poznatky z oblasti diskrétní matematiky, které jim spolu s poznatky z matematiky spojité získanými v jiných předmětech poskytnou základní vědomosti potřebné pro modelování a řešení různých, především inženýrských problémů.


V kurzu získají studenti základní znalosti o chování binárních relací, zejména ekvivalencí a uspořádání a svazů s důrazem na Booleovy algebry. Naučí se minimalizovat booleovské 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ředstavu o základních problémech spojených s kódováním a dekódováním zpráv.

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ý

  • Program C-AKR-P celoživotní vzdělávání v akr. stud. programu

    specializace CZS , 1 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

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

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