Metody diskrétní matematiky (FSI-SDM)

Akademický rok 1999/2000
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í zvládnutí 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-
častějšími typy konečných automatů a s jejich vlastnostmi, s regulární-
mi jazyky a s problémem determinismu. Konečně 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:
 
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ýchmnož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 teorie kódování, se kterou však budou studenti seznámeni jen velmi stručně. Ve všech třech případech se tedy jedná o algebraické disciplíny tvořící teoretické základyinformatiky. Vzhledem k rozvoji využití výpočetní techniky ve všechinženýrských odvětvích jsou získané poznatky pro absolventy oboru tematické inženýrství nezbytné.Uspořádané množiny a svazy. Booleovy algebry (booleovské funkce, algebra logiky). Konečné automaty (Mealyho a Mooreovy automaty). Regulárníjazyky (nedeterministické automaty). Základy teorie kódování.
Metody vyučování:
 
Způsob a kritéria hodnocení:
Podmínky udělení zápočtu: Aktivní účast na cvičení.
Zkouška: Prověří znalost definic zavedených pojmů a jejich vlastností. Schopnost aplikovat získané vědomosti bude ověřena na příkladech.Zkou- ška se skládá z písemné a ústní části.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:
 
Typ (způsob) výuky:
    Přednáška  10 × 2 hod. nepovinná                  
    Cvičení odborného základu  10 × 1 hod. povinná                  
Osnova:
    Přednáška 1. Uspořádané množiny, svazy a úplné svazy.
2. Galoisova korespondence, distributivní a komplementární svazy.
3. Booleovy algebry a booleovské funkce.
4. Minimalizace booleovských funkcí, logické obvody.
5. Konečné automaty - příklady a základní definice, činnost automatu.
6. Izomorfismy, realizace a kongruence automatů.
7. Ekvivalence a podobnost automatů.
8. Regulární jazyky, nedeterministické automaty.
9. Kleenova věta, některé další typy automatů.
10.Kódování a dekódování, samoopravné kódy.
    Cvičení odborného základu Cvičení bude probíhat v těsné návaznosti na přednášky.
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.
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.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
M2301-5 prezenční studium Matematické inženýrství -- kl 4 Povinný 2 2 L