MB154 Diskrétní matematika

Fakulta informatiky
podzim 2019

Předmět se v období podzim 2019 nevypisuje.

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í)
Mgr. Martin Panák, Ph.D. (cvičící)
Mgr. Michal Bulant, Ph.D. (pomocník)
Garance
prof. RNDr. Jan Slovák, DrSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Přírodovědecká fakulta
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 )
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á 53 mateřských oborů, zobrazit
Cíle předmětu
Cílem předmětu je seznámit studenty se základy teorie čísel.
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í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 podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.