MB154 Diskrétní matematika

Fakulta informatiky
podzim 2020
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í)
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
Rozvrh
Po 14:00–15:50 D3
  • Rozvrh seminárních/paralelních skupin:
MB154/01: Po 18:00–19:50 B204, J. Jurka
MB154/02: St 12:00–13:50 B204, M. Štěpán
MB154/03: Čt 8:00–9:50 A320, D. Trnka
MB154/04: Čt 10:00–11:50 A320, D. Trnka
MB154/05: Čt 12:00–13:50 A320, M. Dzúrik
MB154/06: Čt 14:00–15:50 A320, M. Dzúrik
MB154/07: St 14:00–15:50 B204, P. Francírek
MB154/08: St 16:00–17:50 B204, P. Francírek
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 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ích (v případě potřeby nahrazených distanční formou doplněnou řešením domácích úloh).
Metody hodnocení
Během semestru proběhne vnitrosemestrální písemka, max 20 bodů. Ve cvičeních se píší malé písemky, celkově ohodnocené max 20 body (13 písemek po 2 bodech, nejhorší 3 výsledky se mažou; v případě distanční formy budou písemky nahrazeny domácími úkoly). Z těchto max 40 bodů je potřeba získat alespoň 15 bodů pro připuštění k závěrečné písemce, která se koná ve zkouškovém období a sestává z teoretické a početní části, 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ů.
-----
Upřesnění z 30.12.:
Závěrečná zkouška proběhne distanční formou. Zadání bude vygenerované prostřednictvím odpovědníku v ISu a bude sestávat z praktických a teoretických otázek (v poměru cca 70% : 30%) rozdělených do dvou částí. Řešení každé části bude potřeba vypracovat včetně postupu, nafotit/naskenovat a nahrát do odevzdávárny v ISu v rámci časového limitu. Obsahově bude zkouška čerpat z látky probrané na cvičeních a přednáškách.
Vnitrosemestrální písemky sestávají pouze z praktických otázek (nechtějí se tedy definice, věty ani důkazy, nicméně u výpočtů je potřeba popsat postup). Obsahově odpovídají tomu, co se zvládlo probrat na cvičeních v první/druhé polovině semestru. Forma je stejná jako u závěrečné zkoušky.
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 2021, podzim 2022, podzim 2023, podzim 2024.