Předmět Diskrétní matematika B (MB204)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu MB204 - Diskrétní matematika B, Fakulta informatiky, Masarykova univerzita (MU).

Materiál	Typ	Datum	Počet stažení

Cíl

Na konci tohoto kurzu bude student schopen:porozumět a používat metody teorie čísel pro řešení středně obtížných úloh;rozumět tomu, jak jsou výsledky teorie čísel aplikovány v kryptografii;chápat základní výpočetní souvislosti;rozumět algebraickým konceptům a vysvětlit obecné důsledky a souvislosti;modelovat a řešit kombinatorické úlohy a při jejich řešení využívat vytvořující funkce.

Osnova

Čtvrtá část bloku čtyř semestrů matematiky v rozšířené verzi. V celém bloku jsou prezentovány základy algebry a teorie čísel, lineární algebry, analýzy, numerických metod, kombinatoriky a teorie pravděpodobnosti a statistiky.V tomto semestru se jedná o představení základů teorie čísel, algebry a vybraných kombinatorických metod, včetně souvislostí numerických a aplikačních.1. Teorie čísel (4 týdny) – dělitelnost - gcd, rozšířený Euklidův algoritmus (Bezout); počítání s velkými čísly (zejména gcd, modulární umocňování); prvočísla - vlastnosti, základní věta aritmetiky, faktorizace, testování prvočíselnosti a složenosti (Rabin-Miller, Mersenneho prvočísla); kongruence - základní vlastnosti, Malá Fermatova věta; Eulerova věta; řešení lineárních kongruencí a jejich soustav; binomické kongruence a primitivní kořeny; diskrétní logaritmus; prvočísla - testování prvočíselnosti až po AKS, hledání dělitele, eliptické křivky (úvod); Legendreův symbol a zákon kvadratické reciprocity; další testy prvočíselnosti;2. Aplikace teorie čísel (1 týden) – stručný úvod do asymetrické kryptografie (RSA, DH, ElGamal, DSA, ECC); základy teorie kódování - lineární a polynomiální kódy; aplikace Fourierovy transformace pro rychlé výpočty (např. Schönhage-Strassen)3. Úvod do počítačové algebry (3 týdny) – grupa – permutace, symetrie, modulární grupy, homomorfismy a faktorgrupy, akce grupy – Burnsideovo lemma. Okruhy a tělesa – polynomy a jejich kořeny, dělitelnost v oborech integrity, zejména dělitelnost v Z a v okruhu polynomů (nad tělesem), ideály. Konečná tělesa a jejich základní vlastnosti, využití v computer science. Polynomy více proměnných – Gröbnerova báze.4. Kombinatorické výpočty (4 týdny) – základy kombinatoriky (připomenutí); binomická věta a zobecněná binomická věta; kombinatorické identity; Catalanova čísla; algebra formálních mocninných řad; (obyčejné) vytvořující funkce; exponenciální vytvořující funkce; pravděpodobnostní vytvořující funkce; řešení kombinatorických úloh pomocí vytvořujících funkcí; řešení základních rekurencí (Fibonacci); a určení složitosti rekurentního algoritmu; vytvořujíci funkce v computer science (grafové aplikace, složitost, analýza hashování)

Literatura

doporučená literaturaJ. Slovák, M. Panák a kolektiv, Matematika drsně a svižně, učebnice v přípravěneurčenoRILEY, K.F., M.P. HOBSON a S.J. BENCE. Mathematical Methods for Physics and Engineering. second edition. Cambridge: Cambridge University Press, 2004. 1232 s. ISBN 0 521 89067 5. info

Požadavky

! MB104 Diskrétní matematika && ! NOW ( MB104 Diskrétní matematika )Středoškolská matematika. Elementární algebraické a kombinatorické znalosti a dovednosti (obsah MB101 nebo MB201)

Garant

prof. RNDr. Jan Slovák, DrSc.

Vyučující

Mgr. Michal Bulant, Ph.D.Mgr. Aleš Návrat, Dr. rer. nat.Mgr. Martin Panák, Ph.D.