MB154 Diskrétní matematika

Fakulta informatiky
podzim 2025
Rozsah
2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno kontaktně
Vyučující
doc. Lukáš Vokřínek, PhD. (přednášející)
Mgr. Pavel Francírek, Ph.D. (cvičící)
Bc. Štěpán Husa (cvičící)
Bc. Stanislav Valluš (cvičící)
Garance
doc. Lukáš Vokřínek, PhD.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Pá 19. 9. až Pá 19. 12. Pá 10:00–11:50 A,01026
  • Rozvrh seminárních/paralelních skupin:
MB154/01: Út 16. 9. až Út 16. 12. Út 14:00–15:50 A320, P. Francírek
MB154/02: Čt 18. 9. až Čt 18. 12. Čt 10:00–11:50 A320, P. Francírek
MB154/03: Čt 18. 9. až Čt 18. 12. Čt 12:00–13:50 A320, P. Francírek
MB154/04: St 17. 9. až St 17. 12. St 16:00–17:50 B204, Š. Husa
MB154/05: St 17. 9. až St 17. 12. St 18:00–19:50 B204, Š. Husa
MB154/06: Po 15. 9. až Po 15. 12. Po 16:00–17:50 A320, S. Valluš
MB154/07: Po 15. 9. až Po 15. 12. Po 18:00–19:50 A320, S. Valluš
Předpoklady
MB151 Lineární modely || MB152 Dif. a integrální počet || PřF:M1110 Lineární algebra a geom. I || PřF:M1100 Matematická analýza I
Středoškolská matematika. Elementární algebraické a kombinatorické znalosti a dovednosti.
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á 37 mateřských oborů, zobrazit
Cíle předmětu
Cílem předmětu je seznámit studenty se základy teorie čísel s aplikacemi na šifrování, dále pak se základy kódování a pokročilejšími kombinatorickými metodami.
Výstupy z učení
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
  • 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
Výukové metody
Výuka je vedena formou klasických dvouhodinových přednášek a standardních cvičení (v případě potřeby nahrazených distanční formou).
Metody hodnocení
Účast na cvičeních bude sledována, pro připuštění ke zkoušce je potřeba mít maximálně 3 neúčastí (tedy 10 účastí z 13 možných).


Během semestru proběhnou, nejspíše v době přednášek, dvě "vnitrosemestrální" písemky, celkově max 20 bodů (2 písemky po 10 bodech). Obsahově budou odpovídat tomu, co se zvládne probrat na cvičeních v první/druhé polovině semestru.


Během semestru bude zadáno 10 domácích úkolů po 2 bodech, po většinou každý týden jeden, takže lze z domácích úkolů získat max 20 bodů.


Před závěrečnou zkouškou tak lze získat max 20 + 20 = 40 bodů, z nichž alespoň 20 bodů bude potřeba pro připuštění k závěrečné písemce.


Závěrečná zkouška proběhne ve zkouškovém období a sestává z početní a teoretické části (v poměru cca 70% : 30%), max 60 bodů. Celkově tedy lze získat max 100 bodů. Pro úspěšné ukončení předmětu (hodnocení minimálně E) je zapotřebí získat alespoň 50 bodů.

Informace učitele
bodová rozpětí pro jednotlivé známky:
F: [0,50)
E: [50,60)
D: [60,68)
C: [68,76)
B: [76,84)
A: [84,100]
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/podzim2025/MB154