Metody diskrétní matematiky (FSI-SDM)

Akademický rok 2012/2013
Garant: prof. RNDr. Josef Šlapal, CSc.  
Garantující pracoviště: ÚM všechny předměty garantované tímto pracovištěm
Jazyk výuky: čeština
Cíle předmětu:
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.
Výstupy studia a kompetence:
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.
Obsah předmětu (anotace):
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 (booleovské funkce, algebra logiky). Konečné automaty (Mealyho a Mooreovy automaty). Regulární jazyky a gramatiky. Základy teorie kódování.
Metody vyučování:
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.
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.
Typ (způsob) výuky:
    Přednáška  13 × 2 hod.
    Cvičení  13 × 2 hod.
Osnova:
    Přednáška 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í 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
Literatura - základní:
1. N.L.Biggs, Discrete Mathematics, Oxford Univ. Press, 1999.
2. M.Piff, Discrete Mathematics, Cambridge Univ. Press, 1991.
3. A.D.Polimeni and H.J.Straight, Foundations of Discrete Mathematics, Brooks/Cole Publ. Comp., Pacific Grove, California, 1990.
4. D.R.Hankerson at al.: Coding Theory and Cryptography, Marcel Dekker, Inc., New York -Basel, 2000.
Literatura - doporučená:
1. F. Preparata, R. Yeh: Úvod do teórie diskrétnych matematických štruktúr, Alfa, Bratislava, 1982.
2. M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL, Praha, 1990.
3. J. Kopka: Svazy a Booleovy algebry, Univerzita J.E.Purkyně v Ústí nad Labem, 1991.
4. M.Novotný, S algebrou od jazyka ke gramatice a zpět, Academia, Praha, 1988.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
B3A-P prezenční studium B-MAI Matematické inženýrství -- zá,zk 6 Povinný 1 2 Z