MB104 Diskrétní matematika

Fakulta informatiky
jaro 2015
Rozsah
2/2. 4 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Jan Slovák, DrSc. (přednášející)
RNDr. Jana Komárková, Ph.D. (cvičící)
Mgr. Martin Panák, Ph.D. (cvičící)
RNDr. Jiří Pecl, Ph.D. (cvičící)
Mgr. Jaroslav Šeděnka, Ph.D. (cvičící)
doc. Mgr. Josef Šilhan, Ph.D. (cvičící)
Mgr. Michal Bulant, Ph.D. (pomocník)
Mgr. et Mgr. Tomáš Sklenák (pomocník)
Garance
prof. RNDr. Jan Slovák, DrSc.
Fakulta informatiky
Dodavatelské pracoviště: Přírodovědecká fakulta
Rozvrh
Po 14:00–15:50 D3, Po 14:00–15:50 D1
  • Rozvrh seminárních/paralelních skupin:
MB104/T01: Po 16. 2. až Pá 15. 5. Po 8:00–9:35 108, Čt 19. 2. až Pá 15. 5. Čt 14:40–16:10 106, J. Pecl, T. Sklenák, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
MB104/T02: Čt 19. 2. až Pá 15. 5. Čt 12:00–13:35 116, J. Pecl, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
MB104/01: Út 16:00–17:50 A320, J. Slovák
MB104/02: Út 8:00–9:50 A320, M. Panák
MB104/03: Út 10:00–11:50 A320, M. Panák
MB104/04: St 8:00–9:50 A320, M. Panák
MB104/05: St 10:00–11:50 A320, M. Panák
MB104/06: Pá 8:00–9:50 A320, M. Panák
MB104/07: Pá 10:00–11:50 A320, M. Panák
MB104/08: Čt 12:00–13:50 A320, J. Šilhan
MB104/09: Út 12:00–13:50 A320, J. Šilhan
MB104/10: Út 14:00–15:50 A320, J. Šilhan
MB104/11: Út 8:00–9:50 B204, J. Šeděnka
MB104/12: St 8:00–9:50 B204, J. Šeděnka
MB104/13: Po 8:00–9:50 B204, J. Komárková
MB104/14: Po 10:00–11:50 B204, J. Komárková
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/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í 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
Studijní materiály
Předmět je vyučován každoročně.
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 2016, jaro 2017, jaro 2018, jaro 2019, jaro 2020.