Detail předmětu

Metody diskrétní matematiky

FSI-SDMAk. rok: 2010/2011

Předmět Metody diskrétní matematiky seznamuje studenty se třemi základními oblastmi aplikované algebry. První oblastí je teorie uspořádaných množin a svazů, přičemž hlavní pozornost je soustředěna
na teorii Booleových algeber. Další oblastí je algebraická teorie automatů a formálních jazyků. Poslední oblastí je pak úvod do teorie kódování. Ve všech třech případech se tedy jedná o algebraické disciplíny 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é poznatky pro absolventy oboru matematické inženýrství nezbytné.
Binární relace (tolerance a ekvivalence), uspořádané množiny a svazy. Booleovy algebry (booleovske funkce, algebra logiky). Konečné automaty (Mealyho a Mooreovy automaty). Regulární jazyky a gramatiky. Zaklady teorie kódování.

Jazyk výuky

čeština

Počet kreditů

5

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

Metody vyučování závisejí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.

Způsob a kritéria hodnocení

Zkoušky se budou skládat ze dvou částí, písemné a ústní, na základě terých pak bude určena výsledná klasifikace.

Učební cíle

Cílem předmětu Metody diskrétní matematiky je seznámit studenty s ob-
vyklými algebraickými metodami užívanými při konstrukci a popisu čin-
nosti počítače a při přenosu informace. Absolvováním kurzu získají
studenti další důkaz toho, že matematika je základní vědní disciplínou
a její zvladnutí 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

Protože cvičení jsou povinná, bude na nich vyučující 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)

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 B3A-P bakalářský

    obor B-MAI , 2 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Ladislav Skula, DrSc.

Osnova

1. Relace mezi množinami
2. Zobrazení
3. Relace na množině
4. Tolerance a ekvivalence
5. Uspořádané množiny
6. Svazy
7. Booleovy svazy
8. Booleovy funkce
9. Aplikace Booleových svazů
10.Formální jazyky
11.Konečné automaty
12.Gramatiky
13.Samoopravné kódy

Cvičení

13 hod., povinná

Vyučující / Lektor

prof. RNDr. Ladislav Skula, DrSc.

Osnova

1. Relace mezi množinami
2. Zobrazení
3. Relace na množině
4. Tolerance a ekvivalence
5. Uspořádané množiny
6. Svazy
7. Booleovy svazy
8. Booleovy funkce
9. Aplikace Booleových svazů
10.Formální jazyky
11.Konečné automaty
12.Gramatiky
13.Samoopravné kódy