Předmět Diskrétní metody a optimalizace (KIKM / DMO)

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 / DMO - Diskrétní metody a optimalizace, Fakulta informatiky a managementu, Univerzita Hradec Králové (UHK).

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

Obsah

Osnova předmětu:1. Algoritmus, výpočtová složitost, algoritmy pro hledání minimální kostry- Definice algoritmu a jeho vlastnosti- Druhy algoritmů a jejich reprezentace- Složitost algoritmu časová a prostorová- Jarníkův algoritmus pro hledání minimální kostry a určení složitosti- Kruskalův algoritmus pro hledání minimální kostry a určení složitosti- Borůvkův algoritmus pro hledání minimální kostry a určení složitosti2. Algoritmy prohledávaní do šířky a do hloubky a jejich složitosti, stromy prohledávání a jejich vlastnosti- Algoritmus prohledávaní do šířky (PŠ) a jeho složitost- Algoritmus prohledávání do hloubky (PH) a jeho složitost- Strom PŠ- Strom PH- Vlastnosti stromu PŠ- Vlastnosti stromu PH3. Aplikace algoritmů prohledávání do šířky a do hloubky- Algoritmus pro určení, zda graf je souvislý- Algoritmus pro určení počtu komponent v grafu- Algoritmus pro určení, zda x-y vrcholy spolu souvisí- Algoritmus pro určení, zda daná hrana je most- Algoritmus pro určení vzdálenosti a minimální cesty mezi danými vrcholy x a y- Algoritmus pro určení, zda graf je bipartitní- Algoritmus pro určení, zda existuje kružnice obsahující daný vrchol x- Algoritmus pro určení, zda existuje kružnice obsahující danou hranu- Obvod grafu- Algoritmus pro určení všech artikulací- Bloky a algoritmus pro určení všech bloků4. Procházení labyrintů, eulerovský tah a minimální pokrytí grafu tahy- Procházení labyrintů- Algoritmy pro průchod labyrintu (Trémauxův, Tarryho, EdmondsůvJohnsonův)- Eulerovský tah- Algoritmus pro nalezení uzavřeného a otevřeného eulerovského tahu- Minimální pokrytí grafu tahy5. Párování- Základní pojmy, úlohy a aplikace- Párování v obecných grafech- Párování v bipartitních grafech- Přiřazovací úloha6. Úloha čínského pošťáka- Dijkstrův algoritmus pro nalezení nejkratší cesty- Porovnání Jarníkova a Dijkstrova algoritmu- Úloha čínského pošťáka7. Orientované grafy a eulerovský tah v orientovaných grafech- Orientované grafy základní pojmy- Silná souvislost a silně souvislé komponenty- Orientované eulerovské grafy- Uzavřený a otevřený orientovaný eulerovský tah8. Acyklické grafy a topologické uspořádaní vrcholů grafu- Acyklické grafy- Topologické uspořádání grafu9. Barvení grafu- Třída P a NP- Nezávislost grafu- Klikovost grafu- Barvení grafu10. Hamiltonovské cesty a kružnice, problém obchodního cestujícího- Hamiltonovské cesty a kružnice- Heuristický Pósův algoritmus pro hledání hamiltonovské cesty- Problém obchodního cestujícího11. Matroidy- Systémy nezávislých množin- Matroidy a jejich vlastnosti- Průniky matroidů

Získané způsobilosti

Student po absolvování předmětu získá základní teoretické znalosti z oblasti kombinatorických algoritmů, seznámí se s řadou praktických aplikací a získá dovednosti v jejich použití. Bude způsobilý aplikovat probrané algoritmy na řešení základních diskrétních optimalizačních problémů z praxe a rozpoznat, který algoritmus je vhodné použít při řešení dané úlohy.

Literatura

Plesník Ján. Grafové algoritmy. Veda, Bratislava, 1983. Demel, Jiří. Grafy a jejich aplikace. Vyd. 1. Praha, 2002. ISBN 80-200-0990-6.Matoušek, J.: Nešetřil, J. Kapitoly z diskrétní matematiky. Karolinum, Praha, 2000. ISBN 978-80-246-1740-4.Kučera, Luděk. Kombinatorické algoritmy. Praha, 1989. Milková, E. Problém minimální kostry grafu. Gaudeamus, Hradec Králové, 2001. ISBN 80-7041-436-7.

Požadavky

Pravidla účasti na výuce: Účast na cvičení není povinná. Písemně vypracované úkoly z cvičení se hodnotí 0.4 bodem. Body za odevzdané úkoly se berou v úvahu při získání zápočtu. Dobrovolný projekt se hodnotí 4 body, bodování je bráno v úvahu při hodnocení u zkoušky. Požadavky k zápočtu: Během semestru se uskuteční jedna zápočtová písemka. Doba trvání zápočtové písemky je 60 minut, pro udělení zápočtu je potřeba 60% z 20 možných bodů, celkem tedy nejméně 12 bodů. Pokud student nezískal na zápočtové písemce potřebný minimální počet bodů, má nárok na psaní opravné písemky, která se píše v některém zkušebním termínu. K získání zápočtu se berou v úvahu i body za domácí úkoly. Za vypracování DÚ je možné získat celkem 4 body. Forma zkoušky: Zkouška se skládá ze dvou částí: písemné a ústní. Doba trvání zkouškové písemky je 90 minut. Zkoušková písemka obsahuje úlohy s vyznačenou bodovou hodnotou, celkem 30 možných bodů. V ústní části zkoušky se se studentem projde písemná část, případně se položí doplňkové otázky. K celkovému hodnocení u PF slouží i dobrovolný projekt.

Garant

prof. RNDr. Martin Gavalec, CSc.

Vyučující

prof. RNDr. Martin Gavalec, CSc.prof.RNDr.PhDr. Antonín Slabý, CSc.RNDr. Andrea Ševčíkovádoc. Ing. Hana Tomášková, Ph.D.prof. RNDr. Martin Gavalec, CSc.RNDr. Andrea Ševčíkovádoc. Ing. Hana Tomášková, Ph.D.