Diskrétní matematika

Popis

Pokud jste aktivním studentem nebo zaměstnancem UHK, máte nárok na zlevněné kurzovné. Pro uplatnění slevy prosím vyplňte formulář zde.

Termíny výuky: bude upřesněno. Kurz probíhá v letním semestru akademického roku 2026/2027 (únor až květen 2027).

Místo výuky: Univerzita Hradec Králové, Fakulta informatiky a managementu, budova J.

Rozsah: 3 prezenční setkání, celkem 16 vyučovacích hodin, a samostudium v e-learningovém kurzu v Moodle.

Přihlášky: od 1. 12. 2026.

Předmět dává základní znalosti z teorie grafů, kombinatoriky a kombinatorických algoritmů a učí principy dokazování matematických vět. Absolvent dokáže jednoduché tvrzení z teorie grafů, použije teoretické znalosti a algoritmy při řešení základních diskrétních optimalizačních úloh z praxe a rozhodne, který algoritmus se pro danou úlohu hodí.

Jedná se o program zakončený mikrocertifikátem.

Hlavní témata:

1. prezenční setkání: základní terminologie grafů, speciální typy grafů, stromy, kostra grafu.
2. prezenční setkání: problém minimální kostry, Dijkstrův algoritmus, průchod labyrintem, hledání eulerovského tahu, minimální pokrytí tahy, úloha čínského pošťáka.
3. prezenční setkání: prohledávání grafu a jeho aplikace.

Výsledky učení (profil absolventa)

Odborné znalosti: po absolvování předmětu student

• definuje základní pojmy teorie grafů (graf, vrchol, hrana, podgraf, sled, cesta, izomorfismus),
• charakterizuje hamiltonovský, eulerovský, rovinný a bipartitní graf, strom a barevnost grafu,
• popíše algoritmy hledání minimální kostry (Jarníkův, Kruskalův, Borůvkův), eulerovského tahu, průchodu labyrintem, prohledávání grafu do hloubky a do šířky a Dijkstrův algoritmus.

Odborné dovednosti: po absolvování předmětu student

• nakreslí graf k danému skóre, matici sousednosti a incidence a určí vlastnosti zadaných grafů včetně izomorfismu,
• sestrojí haldu a vyhledávací rozhodovací strom,
• použije algoritmy pro minimální kostru, průchod labyrintem a Dijkstrův algoritmus při řešení reálných úloh,
• dokáže základní věty teorie grafů a pomocí kombinatoriky určí počet hran, cest a podgrafů.

Obecné způsobilosti: po absolvování předmětu student

• zvolí vhodný algoritmus (eulerovský tah, minimální pokrytí tahy, úloha čínského pošťáka, prohledávání grafu) pro reálnou úlohu,
• dokáže malé tvrzení z teorie grafů vhodně zvoleným způsobem.

Předpoklady potřebné k zápisu do programu CŽV

• Orientace v základních matematických pojmech.
• Práce se základními matematickými postupy a řešení jednodušších úloh.
• Schopnost logicky uvažovat, analyzovat problém a hledat vhodný způsob jeho řešení.

Forma způsobu ověření výsledků učení a další požadavky na studenta

• Zápočet: úspěšně vypracovaný zápočtový projekt. Téma se zadává na prvním prezenčním setkání a v kurzu v Moodle, kam se projekt také odevzdává.
• Zkouška: písemná část (90 minut; teoretická, aplikační a grafové algoritmy, z každé části je potřeba alespoň 50 % bodů) a ústní část, ve které se probere písemná práce a případně se položí doplňující otázky.
• Hodnocení: A 90–100 %, B 80–89,9 %, C 70–79,9 %, D 60–69,9 %, E 50–59,9 %, F pod 50 %.
• Časová náročnost: 130 hodin (16 h kontaktní výuky, 54 h e-learningu, 10 h projektu, 50 h přípravy na zkoušku).

Studijní literatura a studijní pomůcky

Základní:

• Kurz KIKM/KDIMA v Moodle.
• Milková, E. Teorie grafů a grafové algoritmy. Hradec Králové: Gaudeamus, 2012. ISBN 978-80-7435-267-6.

Doporučená:

• Matoušek, J., Nešetřil, J. Kapitoly z diskrétní matematiky. Praha: Karolinum, 2000. ISBN 978-80-246-1740-4.
• Milková, E. Problém minimální kostry grafu. Hradec Králové: Gaudeamus, 2001. ISBN 80-7041-436-7.

Další informace:

Přihlášení probíhá elektronickou formou, je závazné a kurzovné nevratné. Před zahájením kurzu obdrží přihlášení organizační pokyny e-mailem. Vzdělavatel si vyhrazuje právo kurz neotevřít z důvodu dlouhodobé nemoci lektora, dále pak v případě nedostatečného počtu přihlášených osob, či z jiných závažných organizačních důvodů. O neotevření kurzu budou přihlášení v předstihu informováni e-mailem. V případě zrušení kurzu ze strany vzdělavatele se kurzovné přihlášeným vrací v plné výši.