Předmět Discrete Methods and Optimalization (KIKM / ADMO)

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 / ADMO - Discrete Methods and Optimalization, 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.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.