MB104 Diskrétní matematika

Fakulta informatiky
jaro 2020
Rozsah
2/2/0. 4 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Jan Slovák, DrSc. (přednášející)
Mgr. Jana Bartoňová (cvičící)
Mgr. Jonatan Kolegar (cvičící)
Mgr. Radka Penčevová (cvičící)
Mgr. Mária Šimková (cvičící)
Mgr. Andrej Tokarčík (cvičící)
Bc. Dominik Trnka (cvičící)
doc. Lukáš Vokřínek, PhD. (cvičící)
Mgr. Michal Bulant, Ph.D. (pomocník)
Mgr. Martin Panák, Ph.D. (pomocník)
Garance
prof. RNDr. Jan Slovák, DrSc.
Fakulta informatiky
Dodavatelské pracoviště: Přírodovědecká fakulta
Předpoklady
! MB204 Diskrétní matematika B && ! NOW ( MB204 Diskrétní matematika B )
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
předmět má 53 mateřských oborů, zobrazit
Cíle předmětu
Na konci tohoto kurzu bude student schopen: porozumět a používat metody teorie čísel pro řešení jednoduchých úloh; přibližně rozumět tomu, jak jsou výsledky teorie čísel aplikovány v kryptografii; chápat základní výpočetní souvislosti;
modelovat a řešit jednoduché kombinatorické úlohy.
Osnova
  • Čtvrtá část bloku čtyř semestrů matematiky v základní 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.
  • Základy teorie čísel: gcd, rozšířený Euklidův algoritmus (Bezout); počítání s velkými čísly (zejména gcd, modulární umocňování) základní věta aritmetiky, faktorizace, testování prvočíselnosti a složenosti (Rabin-Miller, Mersenneho prvočísla); Malá Fermatova věta; Eulerova věta, řád čísla řešení lineárních kongruencí a jejich soustav, čínská zbytková věta binomické kongruence a primitivní kořeny, problém diskrétního logaritmu.
  • Aplikace teorie čísel:
  • RSA, DH, ElGamal, DSA, lineární a polynomiální kódy.
  • Kombinatorické výpočty:
  • binomická věta a zobecněná binomická věta; základní kombinatorické identity a jejich odvozování, základní způsoby řešení kombinatorických úloh, 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í, Fibonacciho čísla, Cayleyho formule a další využití vytvořujících funkcí, asymptotické odhady.
Literatura
Záložky
https://is.muni.cz/ln/tag/FI:MB104!
Výukové metody
Výuka je vedena formou klasických dvouhodinových přednášek a standardních cvičením.
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á praktická písemka na max 20 bodů. Pro úspěšné ukončení předmětu (hodnocení minimálně E) je zapotřebí získat z písemek alespoň 20 bodů.
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019.