MB204 Diskrétní matematika B

Fakulta informatiky
jaro 2015
Rozsah
4/2. 6 kr. (plus ukončení). Ukončení: zk.
Vyučující
Mgr. Michal Bulant, Ph.D. (přednášející)
doc. Mgr. Aleš Návrat, Dr. rer. nat. (přednášející)
Mgr. Martin Panák, Ph.D. (pomocník)
Garance
prof. RNDr. Jan Slovák, DrSc.
Fakulta informatiky
Dodavatelské pracoviště: Přírodovědecká fakulta
Rozvrh
Po 18:00–19:50 A319, Čt 8:00–9:50 A319, Pá 12:00–13:50 A320
Předpoklady
! 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)
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
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á literatura
  • J. Slovák, M. Panák a kolektiv, Matematika drsně a svižně, učebnice v přípravě
    neurčeno
  • RILEY, 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
Záložky
https://is.muni.cz/ln/tag/FI:MB204!
Výukové metody
Dvě dvouhodinové přednášky kombinující teorii a řešené příklady. Seminární skupiny zaměřené na zvládnutí početních úloh.
Metody hodnocení
Během semestru jsou dvě povinné vnitrosemestrální písemky, každá na max 10 bodů. Ve cvičení se píší malé písemky, celkově ohodnocené max 5 body. Závěrečná písemka na max 20 bodů je následována ústní zkouškou. Pro úspěšné ukončení předmětu (hodnocení minimálně E) je zapotřebí získat z písemek alespoň 20 bodů a úspěšně absolvovat ústní zkoušku.
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2013, jaro 2014, jaro 2016, jaro 2017, jaro 2018, jaro 2019, jaro 2020.