FI:MB154 Diskrétní matematika - Informace o předmětu

MB154 Diskrétní matematika

Rozsah

2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno kontaktně

Vyučující

doc. Mgr. Josef Šilhan, Ph.D. (přednášející)
doc. Lukáš Vokřínek, PhD. (přednášející)
Mgr. Pavel Francírek, Ph.D. (cvičící)
Mgr. Jan Procházka (cvičící)
Bc. et Bc. Martin Zahradníček, MSc (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

Po 23. 9. až Po 16. 12. Po 10:00–11:50 D2

• Rozvrh seminárních/paralelních skupin:

MB154/01: St 25. 9. až St 18. 12. St 8:00–9:50 B204, P. Francírek
MB154/02: Čt 26. 9. až Čt 19. 12. Čt 16:00–17:50 A320, J. Procházka
MB154/03: Čt 26. 9. až Čt 19. 12. Čt 18:00–19:50 A320, J. Procházka
MB154/04: Pá 27. 9. až Pá 20. 12. Pá 8:00–9:50 A320, M. Zahradníček
MB154/05: Pá 27. 9. až Pá 20. 12. Pá 10:00–11:50 A320, M. Zahradníček

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

• Analýza a zpracování obrazu (program FI, N-VIZ)
• Bioinformatika a systémová biologie (program FI, N-UIZD)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Informatika (program FI, B-INF) (2)
• Informatika ve vzdělávání (program FI, B-IVV) (2)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Principy programovacích jazyků (program FI, N-TEI)
• Programování a vývoj aplikací (program FI, B-PVA)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• Software Systems Development Management (program FI, N-RSSS_A)
• Softwarové systémy (program FI, N-PSKB)
• Strojové učení a umělá inteligence (program FI, N-UIZD)
• Učitel informatiky a správce sítě (program FI, N-UCI)
• Učitelství informatiky pro střední školy (program FI, N-UCI) (2)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

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

• SLOVÁK, Jan, Martin PANÁK a Michal BULANT. Matematika drsně a svižně. 1. vyd. Brno: Masarykova univerzita, 2013, 773 s. ISBN 978-80-210-6307-5. Dostupné z: https://dx.doi.org/10.5817/CZ.MUNI.O210-6308-2013. Základní učebnice matematiky pro vysokoškolské studium info

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ů

• MB141 Lineární algebra a diskrétní matematika
  !NOW(MB151) && ( !MB151 || !MB154 )  

• Statistika zápisu (nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2024/MB154