MB154 Diskrétní matematika

Fakulta informatiky
podzim 2023
Rozsah
2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Jan Slovák, DrSc. (přednášející)
doc. Lukáš Vokřínek, PhD. (přednášející)
Mgr. Martin Dzúrik (cvičící)
Mgr. Pavel Francírek, Ph.D. (cvičící)
Mgr. Jan Jurka (cvičící)
Mgr. Martin Panák, Ph.D. (cvičící)
Mgr. Miloslav Štěpán (cvičící)
Mgr. Dominik Trnka (cvičící)
prof. Mgr. Petr Hasil, Ph.D. (pomocník)
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
Po 14:00–15:50 D2
  • Rozvrh seminárních/paralelních skupin:
MB154/01: Čt 12:00–13:50 A320, L. Vokřínek
MB154/02: Čt 14:00–15:50 A320, L. Vokřínek
MB154/03: St 8:00–9:50 B204, M. Dzúrik
MB154/04: St 10:00–11:50 B204, M. Dzúrik
MB154/05: Út 8:00–9:50 B204, M. Štěpán
Předpoklady
! MB104 Diskrétní matematika && ! MB204 Diskrétní matematika B && ( MB101 Lineární modely || MB201 Lineární modely B || MB151 Lineární modely || MB102 Dif. a integrální počet || MB202 Dif. a integrální počet B || 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
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 2024.