UIINFNP011 Kombinatorické algoritmy

Filozoficko-přírodovědecká fakulta v Opavě
zima 2025
Rozsah
2/0/0. 4 kr. Ukončení: zk.
Vyučující
RNDr. Radka Poláková, Ph.D. (přednášející)
Garance
RNDr. Radka Poláková, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Rozvrh
Po 18:05–19:40 PED1
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
Předmět přináší posluchačům základní orientaci v oblasti kombinatorických-grafových algoritmů. Obsahem předmětu je tedy zopakování odborných termínů z teorie grafů a seznámení se s několika grafovými algoritmy.
Výstupy z učení
Student bude mít přehled o základních grafových algoritmech a může je tak aplikovat při řešení různých diskrétních problémů.
Osnova
1. Graf. 2. Reprezentace grafu. 3. Prohledávání grafu. 4. Souvislost, komponenty. 5. Délka cesty v grafu. 6. Kostra grafu. 7. Eulerovské grafy, Hamiltonovský cyklus. 8. Párování v grafu. 9. Klika, nezávislá množina. 10. Barvení grafu. 11. Kružnice v grafu. 12. Toky v sítích.
Literatura
    povinná literatura
  • HLINĚNÝ, Petr. Základy Teorie grafů [online]. Masarykova univerzita. 2010. Dostupné na: https://is.muni.cz/do/1499/el/estud/fi/js10/grafy/Grafy-text10.pdf [cit. 8. 10. 2019]
  • KOVÁŘ, Petr. Úvod do teorie grafů [online]. VŠB TU v Ostravě, 2016. Dostupné na: http://homel.vsb.cz/~kov16/files/uvod_do_teorie_grafu.pdf. [cit. 8. 10. 2019]
    doporučená literatura
  • BONDY, J a MURTY. Graph theory. New York: Springer, 2010. ISBN 978-1-84996-690-0. info
  • GERA, Ralucca; Craig LARSON a Stephen HEDETNIEMI. Graph theory: Favorite Conjectures and OpenProblems. New York: Springer, 2016. ISBN 978-3-319-31938-4. info
  • Even, S., Even, G. Graph algorithms, 2nd edition. New York Cambridge University Press, 2012. ISBN 978-0-521-51718-8. info
  • KOCAY, William L a Donald L KREHER. Graphs, Algorithms and Optimization. 2nd Edition. Boca Raton,USA: CRC Press, 2016. ISBN 978-1-4822-5116-6. info
  • MILKOVÁ, Eva. Teorie grafů a grafové algoritmy. Hradec Králové: Gaudeamus, 2013. ISBN 978-80-7435-267-6. info
  • ŠEDA, Miloš. Teorie grafů [online]. Brno: VUT, 2003. Dostupné na: http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf. [cit. 8. 10. 2019]
Výukové metody
Přednášky, diskuse, cvičení, případové studie.
Metody hodnocení
• Docházka - prezenční studium: Navštěvovat přednášky je velmi doporučeno. • Docházka - kombinované studium: Přednášky jsou povinné. • Písemná zkouška - získání minimálně 50 % bodů
Předmět je zařazen také v obdobích zima 2021, zima 2022, zima 2023, zima 2024.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.slu.cz/predmet/fpf/zima2025/UIINFNP011