B_DMa Diskrétní matematika

Vysoká škola finanční a správní
zima 2016
Rozsah
2/1. 10 hodin KS/semestr. 5 kr. Ukončení: zk.
Vyučující
RNDr. Ivan Havlíček, CSc. (cvičící)
Garance
RNDr. Ivan Havlíček, CSc.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Ing. Barbora Ptáčková
Rozvrh seminárních/paralelních skupin
B_DMa/cAPH: každou sudou středu 14:00–14:44 E129, každou sudou středu 14:45–15:30 E129, I. Havlíček
B_DMa/pAPH: St 12:15–12:59 E129, St 13:00–13:45 E129, kromě St 26. 10. ; a St 19. 10. 15:45–17:15 E228, I. Havlíček
Předpoklady
Nejsou vyžadovány žádné předpoklady
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
Na konci tohoto kurzu budou studenti schopni: - Provádět důkazy tautologií, pracovat s kvantifikátory, správně negovat tvrzení. - Provádět důkazy tvrzení sporem a matematickou indukcí, operace s množinami. - Využívat kombinatorické počítání a diskrétní pravděpodobnost na příkladech. - Chápat binární relaci na množině A jako podmnožinu kartézského součinu AxA, relaci uspořádání a relaci ekvivalence a její vlastnosti. Zobrazení na, do a vzájemně jednoznačné. - Využívat kombinatorické počítání a diskrétní pravděpodobnost k počítání příkladů. - Umět základní pojmy týkající se neorientovaných grafů. Graf úplný, bipartitní, cyklus,(kružnice), cesta. Co je Izomorfismus. - Hledat nejkratší cesty v grafu Dijkstrovým algoritmem, párování v grafu a jejich změny střídavých cest. - Používat skóre grafu a jeho přepočty, řešit eulerovské tahy a úlohu čínského listonoše. - Kódovat stromy a užívat algoritmy hledání minimální kostry grafu (Kruscal, Jarník/Prim, Borůvka). - Vytvářet duální grafy, Umět barvit stěny grafu, jeho vrcholy a hrany. - Pochopit orientované grafy, jejich symetrizaci, acyklické grafy. Hledat kondenzace orientovaných grafů. De Bruijnovy posloupnosti. - Hledat v síti maximální tok a minimální řez.
Osnova
1. Úvod do matematické logiky 2. Matematické důkazy, množiny, číselné množiny. 3. Relace, zobrazení. 4. Kombinatorické počítání a diskrétní pravděpodobnost. 5. Neorientovaný graf. 6. Hledání nejkratší délky cesty. párování v grafu. 7. Eulerovské grafy a k-souvislost. 8. Speciální třída grafů - stromy. 9. Minimální kostra, rovinné kreslení grafů. 10. Barevnost mapy – problém čtyř barev. 11. Orientované grafy. 12. Toky v sítích. ¨
Literatura
    povinná literatura
  • Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky. Nakladatelství Karolinum: Praha, 2002.
  • Havlíček, I.: Diskrétní matematika. Praha: VŠFS - Eupress, 2007.
  • Havlíček, I. Sbírka příkladů y diskrétní matematiky, VŠFS Praha 2017.
  • Demel, J., Grafy a jejich aplikace, ČVUT Praha 2015.
Výukové metody
Přednášky, cvičení/semináře v prezenční formě studia; řízené skupinové konzultace v kombinované formě studia; a minimální povinná účast ve výuce, která je stanovena prorektorem na 75% na cvičeních/seminářích v prezenční formě studia a na 50% na řízených skupinových konzultacích v kombinované formě studia.
Metody hodnocení
Zápočet (75% účasti na cvičení), zkouška písemná (50% správných odpovědí) a ústní.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
pouze prezenční forma.
Předmět je zařazen také v obdobích zima 2013, zima 2014, zima 2015, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023, zima 2024, zima 2025.