Detail předmětu

Metody diskrétní matematiky

FSI-SDMAk. rok: 1999/2000

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í.

Jazyk výuky

čeština

Počet kreditů

4

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-
č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.

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.

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í zvládnutí je nutným předpokladem pro úspěšnou tvůrčí činnost
inženýra.

Základní literatura

N.L.Biggs, Discrete Mathematics, Oxford Univ. Press, 1999. (EN)
M.Piff, Discrete Mathematics, Cambridge Univ. Press, 1991. (EN)
A.D.Polimeni and H.J.Straight, Foundations of Discrete Mathematics, Brooks/Cole Publ. Comp., Pacific Grove, California, 1990. (EN)

Doporučená literatura

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

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

  • Program M2301-5 magisterský

    obor , 2. ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

20 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

Osnova

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

10 hod., povinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

Osnova

Cvičení bude probíhat v těsné návaznosti na přednášky.