B_DMa Diskrétní matematika

Vysoká škola finanční a správní
zima 2024
Rozsah
2/2/0. 14 hodin KS/semestr. 6 kr. Ukončení: zk.
Vyučující
RNDr. Eva Ulrychová, Ph.D. (cvičící)
Garance
RNDr. Eva Ulrychová, Ph.D.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Ivana Plačková
Rozvrh seminárních/paralelních skupin
B_DMa/cAPH: Po 10:30–11:14 E230, Po 11:15–12:00 E230, E. Ulrychová
B_DMa/pAPH: Po 8:45–9:29 E230, Po 9:30–10:15 E230, E. Ulrychová
Předpoklady
Nejsou vyžadovány žádné předpoklady
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
Na konci tohoto kurzu budou studenti schopni: - 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ů. - Znát základní algebraické struktury. - 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 podél střídavé cesty. - 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.
Výstupy z učení
Po úspěšném ukončení tohoto kurzu jsou studenti schopni: Používat logické postupy při důkazu matematického tvrzení, především důkaz matematickou indukcí a sporem. Rozumět binárním relacím uspořádání a ekvivalence, zobrazením prostým a na. Užívat kombinatorické počítání. Znát různé třídy neorientovaných grafů, tj. ovládat terminologii teorie grafů. Umět hledat nejkratší vzdálenost v ohodnoceném grafu užitím Dijstrova algoritmu. Znát párování v grafu a jeho změny. Aplikovat skóre grafu a jeho úpravy. Umět hledat Eulerův uzavřený graf. Užívat různé algorimy hledání minimální kostry ( Kruscal, Jarník/Prim, Borůvka). Kreslit rovinné grafy a konstruovat k nim duální grafy. Hledat minimální vybarvení stěn grafu, jeho vrcholů popř. hran. Znát pojem orientovaný graf, jeho symetrizaci, acyklické grafy a jejich kondenzaci, De Brujnovy posloupnosti. Hledat v síti maximální tok a minimální řez.
Osnova
  • 1. Matematické důkazy, množiny, číselné množiny.
  • 2. Relace, zobrazení.
  • 3. Kombinatorické počítání a diskrétní pravděpodobnost.
  • 4. Algebraické struktury.
  • 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
  • HAVLÍČEK, Ivan. Diskrétní matematika. Praha: VŠFS - Eupress, 2007.
  • MILKOVÁ, Eva. Teorie grafů a grafové algoritmy. Hradec Králové: Gaudeamus, 2013. ISBN 978-80-7435-267-6.
    doporučená literatura
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. Páté, upravené a doplněné vydání. Praha: Univerzita Karlova, nakladatelství Karolinum, 2022. ISBN 978-80-246-5084-5.
  • DEMEL, Jiří. Grafy a jejich aplikace, 3. (elektronické) vydání, 2019.
  • KOSMÁK, Ladislav a Radovan POTŮČEK. Úvod do algebry. Ostrava: Key Publishing, 2012. Učebnice (Key Publishing). ISBN 978-80-7418-162-7.
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í.
Předmět je zařazen také v obdobích zima 2013, zima 2014, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.vsfs.cz/predmet/vsfs/zima2024/B_DMa