MB104 Diskrétní matematika

Fakulta informatiky
jaro 2014
Rozsah
2/2. 4 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Jan Slovák, DrSc. (přednášející)
Mgr. Marek Filakovský, Ph.D. (cvičící)
Mgr. Bc. Tomáš Janík (cvičící)
RNDr. Jana Komárková, Ph.D. (cvičící)
Mgr. David Kruml, Ph.D. (cvičící)
Mgr. Bc. Jaromír Kuben (cvičící)
Mgr. Lenka Mžourková Macálková (cvičící)
Mgr. Martin Panák, Ph.D. (cvičící)
RNDr. Jiří Pecl, Ph.D. (cvičící)
Mgr. Milan Werl, Ph.D. (cvičící)
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: Út 18. 2. až So 31. 5. Út 13:00–14:35 Učebna S2 (36b), Čt 20. 2. až So 31. 5. Čt 13:00–14:35 Učebna S6 (20), Pá 21. 2. až So 31. 5. Pá 8:00–9:35 Učebna S10 (56), J. Pecl, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
MB104/T02: Čt 27. 2. až So 31. 5. Čt 8:00–9:35 Učebna S6 (20), M. Werl, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
MB104/T03: Út 25. 2. až So 31. 5. Út 9:40–11:15 Učebna S4 (35a), Pá 28. 2. až So 31. 5. Pá 13:30–15:10 Učebna S4 (35a), M. Werl, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
MB104/01: St 8:00–9:50 G331, M. Panák
MB104/02: St 10:00–11:50 G331, M. Panák
MB104/03: Čt 14:00–15:50 G331, D. Kruml
MB104/04: St 8:00–9:50 G125, D. Kruml
MB104/05: Čt 10:00–11:50 B410, M. Panák
MB104/06: Čt 12:00–13:50 G330, D. Kruml
MB104/07: Čt 16:00–17:50 G331, M. Filakovský
MB104/08: Čt 18:00–19:50 G331, M. Filakovský
MB104/09: Út 16:00–17:50 G331, T. Janík
MB104/10: Út 18:00–19:50 G331, T. Janík
MB104/11: Pá 12:00–13:50 G331, J. Komárková
MB104/12: Pá 14:00–15:50 G331, J. Komárková
MB104/13: Čt 16:00–17:50 G125, J. Kuben
MB104/14: Čt 18:00–19:50 G125, J. Kuben
MB104/15: Pá 8:00–9:50 G331, M. Werl
MB104/16: Pá 10:00–11:50 G330, M. Werl
MB104/17: Čt 14:00–15:50 G330, L. Mžourková Macálková
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
předmět má 16 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
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 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, jaro 2020.