Název: Diskrétní matematika Zkratka: DMA Typ: povinný Rozsah: 14 týdnů, týdně 2 hodiny přednášek + 2 hodiny seminárních cvičení Kredity: 5 Způsob ukončení: zkouška Katedra: katedra aplikované matematiky FP TUL Přednášející: RNDr. Miroslav Koucký, CSc. (50%)
Prof. RNDr. Bohdan Zelinka, DrSc. (50%)
Stručná anotace předmětu:V rámci předmětu budou studenti seznámeni se dvěma tématickými okruhy - základními algebraickými strukturami s jednou a dvěma binárními operacemi (především s grupami a tělesy) a následně se základy teorie kódování.
Témata přednášek:Základní algebraické pojmy - relace, zobrazení, operace a jejich vlastnosti. Pojem univerzální algebra, kongruence. Algebraické struktury s jednou binární operací - grupoid, pologrupa, monoid, grupa.
Základy teorie grup. Podgrupy, Lagrangeova věta, normální podgrupy. Abelovy grupy, cyklické grupy, symetrické grupy, permutační grupy. Struktura vybraných konečných grup.
Algebraické struktury se dvěma binárními operacemi - okruh, obor integrity, těleso. Ideál, prvoideál. Dělitelnost v oboru integrity.
Okruhy polynomů, ireducibilita. Konečná tělesa GF(p^n), jejich konstrukce a základní vlastnosti.
Základní pojmy z teorie kódování. Kraftova nerovnost, MacMillanova věta. Blokové a prefixové kódy. Huffmanova konstrukce nejkratšího kódu.
Lineární kódy, Hammingovy kódy, Reed-Mullerovy kódy, cyklické kódy, BCH kódy, Reed-Solomonovy kódy. Perfektní kódy.
Základní metody kódování s veřejným klíčem - RSA, knapsack, ElGamal, McEliece, DSA.
Náplň cvičení:Procvičuje se látka vyložená na předchozích přednáškách. V tématickém okruhu algebra budou probrány příklady základních algebraických struktur, především grup (Kleinova čtyřgrupa, kvaternióny, symetrické grupy, alternující grupy) a jejich vlastnosti, konstrukce konečných těles a počítání v nich. V tématickém okruhu kódování budou procvičeny konstrukce jednotlivých typů kódů. Průběžně budou poskytovány informace o zdrojích na internetu, které se vztahují k aktuálně probírané látce.
Literatura:Adámek, J.: Kódování. SNTL, Praha 1989.
Bečvář, J.: Úvod do algebry. Skripta MFF, SPN, Praha 1984.
Chajda, I. - Halaš, R.: Cvičení z algebry. UP Olomouc, Olomouc 1995.
Nešetřil, J. - Matoušek, J.: Kapitoly z diskrétní matematiky. Karolinum, Praha 2000.
VanLint, J.H.: Introduction to Coding Theory. 3th ed., Springer-Verlag, 1999.
Prerekvizity: -Navazující: -
Datum poslední změny: 5. 12. 2001