Předmět Diskrétní matematika (KIKM / KDIMA)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KIKM / KDIMA - Diskrétní matematika, Fakulta informatiky a managementu, Univerzita Hradec Králové (UHK).

Materiál	Typ	Datum	Počet stažení

Obsah

Téma 1: Základní terminologie grafu:- Graf, reprezentace grafu- Podgraf, indukovaný podgraf- Stupeň vrcholu, princip sudosti, skóre grafu- Sled, tah, cesta, kružnice- Souvislost, komponenta, most, artikulace- Rovnost grafů, izomorfizmus grafů- Úplný graf, doplněk grafuTéma 2: Základní terminologie grafu speciální typy grafů:- Bipartitní graf, úplný bipartitní graf- Hamiltonovský graf- Eulerovský graf- Rovinný graf- Barevnost grafůTéma 3: Stromy:- Strom, les, vlastnosti stromu- Centrum, bicentrum- Kořenový strom, kořen stromu, předchůdce, následník- Binární strom, levý a pravý syn- Binární vyhledávácí strom, haldaTéma 4: Kostra grafu:- Kostra grafu- Počet koster grafuTéma 5: Problém minimální kostry:- Ohodnocený graf- Minimální kostra grafu- Klasické algoritmy na hledání minimální kostry grafu Borůvkův, Jarníkův a KruskalůvTéma 6: Procházení labyrintu:- Labyrint a jeho grafová reprezentace- Procházení částí labyrintu pravidlo pravé ruky, Ariadnina nit- Algoritmy na procházení celého labyrintu Trémauxův, Tarryho, Edmonds JohnsonůvTéma 8: Eulerovské tahy, pokrytí grafu tahy, úloha Čínskeho pošťáka:- Eulerovský graf- Uzavřený a otevřený eulerovský tah- Algoritmus na nalezení eulerovského tahu- Pokrytí grafu minimálním počtem tahů- Úloha čínského pošťákaTéma 9: Prohledávání grafu:- Datové struktury fronta, zásobník- Prohledávání vrcholů a hran grafu do šířky- Prohledávání vrcholů a hran grafu do hloubky- Strom prohledávání do šířky- Strom prohledávání do hloubky- Vlastnosti stromů prohledáváníTéma 10: Aplikace prohledávání grafu: obsah nebo sylabus:- Určení souvislosti grafu- Určení počtu komponent- Určení, zda je daná hrana most- Určení nejkratší cesty mezi dvěma vrcholy- Určení, zda je daný vrchol artikulace- Určení, zda je daný graf bipartitní- Určení, zda vrchol/hrana leží na kružnici

Získané způsobilosti

Student po absolvování předmětu získá základní teoretické znalosti z oblasti kombinatoriky, teorie grafů a kombinatorických algoritmů, seznámí se s řadou praktických aplikací a získá dovednosti v jejich použití. Bude způsobilý aplikovat probrané teoretické znalosti a algoritmy na řešení základních diskrétních optimalizačních jednoduchých problému z praxe a rozpoznat, který algoritmus je vhodný pro řešení dané úlohy.Podrobně, po absolvování předmětu bude student schopen:- aplikovat algoritmus na určení, zda daná posloupnost je/není skóre grafu a namalovat k dané posloupnosti graf- reprezentovat jednoduchou úlohu vhodným grafem a pomocí tohoto grafu ji vyřešit- dokázat větu Princip sudosti a její důsledek- aplikovat pravidla na určení, zda daný graf je/není hamiltonovský- určit vlastnosti zadaných grafů a aplikovat je v úlohách- dokázat jednoduché tvrzení týkající se výše uvedených vlastností grafu- aplikovat tvrzení o rovinných grafech - dokázat, že daný graf není rovinný - dokázat tvrzení a věty týkající se stromu, vlastností stromu a lesa- využit stromové datové struktury v předmětech zabývajících se programováním- dokázat větu o existenci kostry v souvislém grafu- aplikovat algoritmus na nalezení minimální kostry, algoritmus na průchod labyrintem, Dijkstrův algoritmus při řešení reálných úloh - dokázat tvrzení a věty týkající se eulerovských grafů- aplikovat vhodný algoritmus (eulerovský tah, minimální pokrytí tahy, úloha čínského pošťáka) při řešení reálných úloh- aplikovat algoritmy prohledávání do šířky/do hloubky a využit vlastností stromů prohledávání při řešení reálných úloh- aplikovat aplikace algoritmů prohledávání do hloubky a do šířky jak na grafu reprezentovaném obrázkem, tak na grafu reprezentovaném matici sousednosti, a tím si uvědomit, jaké informace je nutno při realizaci algoritmu uchovávat a využit je v reálných úlohách

Literatura

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

Požadavky

Požadavky k zápočtu: Od studenta se požaduje pravidelná příprava na základě samostatné práce s učebními texty, zejména s texty přednášek. Dále pro studenta PF se požaduje alespoň 80% účast na cvičeních, úspěšné napsání zápočtového testu a úspěšné obhájení zápočtového projektu a pro studenta KF se požaduje vypracování zápočtového projektu. Zadávání a hodnocení zápočtových písemek: - během semestru se uskuteční jedna zápočtová písemka, termín upřesněný na cvičení- doba trvání zápočtové písemky je 45 minut- zápočtová písemka obsahuje sedm úlohy s vyznačenou bodovou hodnotou- zápočtovou písemku je potřeba napsat na 60%- při neúspěchu lze napsat opravnou zápočtovou písemku, která je požadováná za úspěšnou, jestliže je napsaná na 60%, termín je předem oznámen- ukázku zápočtové písemky student nalezne na oliva.uhk.cz v kurzu DIMAZadáni zápočtového projektu: vypracovat prezentaci vhodného příkladu z praxe a aplikovat na řešení vhodný algoritmus nebo naprogramovat libovolný algoritmus z přednášek. Forma zkoušky: Zkouška proběhne formou písemnou (dvě části teorie+aplikace, grafové algoritmy) a ústní.Doba trvání zkouškové písemky je 90 minut.Zkoušková písemka - teorie+aplikace obsahuje devět úloh s vyznačenou bodovou hodnotou plus jeden prémiový úkol za 2 body, celkem 21+2 možných bodů, minimálně je potřeba získat 50% bodů - grafové algoritmy obsahuje tři úlohy, každá úloha za 3 body, minimálně je potřeba získat 50% bodů - - ukázku zkouškové písemky student nalezne na oliva.uhk.cz v kurzu DIMAV ústní části se probere písemní část, vysvětlí chyby a případně se položí doplňkové otázky, které složí na doladění známkyInformace o hodnocení zkoušky - body všech písemek se sečtou a hodnocení se provede podle následující tabulky:body hodnocení100 - 90% výborně89.9 - 70% velmi dobře69.9 - 50% dobře49.9 - 0% nevyhovující Tematické okruhy pro sestavování zkouškových písemek a teoretických otázek Podle sylabu DIMA

Garant

RNDr. Andrea Ševčíková

Vyučující

Mgr. Jiří Haviger, Ph.D.doc. RNDr. Pavel Pražák, Ph.D.RNDr. Andrea Ševčíková