MB204 Diskrétní matematika B

Fakulta informatiky
jaro 2013
Rozsah
4/2. 6 kr. (plus ukončení). Ukončení: zk.
Vyučující
Mgr. Michal Bulant, Ph.D. (přednášející)
Mgr. Martin Panák, Ph.D. (přednášející)
prof. RNDr. Jan Slovák, DrSc. (přednášející)
doc. Mgr. Aleš Návrat, Dr. rer. nat. (cvičící)
Mgr. Jaroslav Šeděnka, Ph.D. (cvičící)
RNDr. Jan Vondra, Ph.D. (cvičící)
Garance
prof. RNDr. Jan Slovák, DrSc.
Fakulta informatiky
Dodavatelské pracoviště: Přírodovědecká fakulta
Rozvrh
Po 12:00–13:50 G101, Út 8:00–9:50 G126, St 10:00–11:50 G101
  • Rozvrh seminárních/paralelních skupin:
MB204/01: Rozvrh nebyl do ISu vložen. A. Návrat
Předpoklady
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
předmět má 16 mateřských oborů, zobrazit
Cíle předmětu
Č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.
Osnova
  • 1. Ú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.
  • 2. 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;
  • 3. 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)
  • 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
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í
Čtyřhodinová přednáška a dvouhodinové cvičení. Zakončení písemnou zkouškou a ústní zkouškou. Výsledky ze cvičení a průběžných písemek se částečně přenášejí do hodnocení zkoušky.
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 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, jaro 2020.