Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2 značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS
BIK-GRA | Grafové algoritmy a základy teorie složitosti | Rozsah kontaktní výuky: | 13KP+4KC | ||
---|---|---|---|---|---|
Vyučující: | Způsob zakončení: | Z,ZK | |||
Zodpovědná katedra: | 18101 | ECTS Kredity: | 5 | Semestr: | L |
Anotace:
Studenti získají základní přehled o používání grafových modelů v informatice, se zaměřením především na algoritmické otázky a řešení grafových problémů. Zahrnuta jsou rovněž další témata, která tento přehled doplňují o specifické aplikace nebo postupy (toky v sítích, heuristické hledání, aproximační algoritmy) nebo se týkají obecnější problematiky algoritmické řešitelnosti a složitosti úloh (Turingovy stroje, NP úplné problémy).
Osnovy přednášek:
1. | Grafové modely, neorientované grafy, izomorfismus. Sousednost, souvislost, orientované grafy. | |
2. | Silná souvislost, acyklické grafy, reprezentace grafů, procházení do šířky. Procházení do hloubky, topologické uspořádání, silně souvislé komponenty. | |
3. | Eulerovy grafy, dominující a nezávislé podmnožiny, barevnost, vzdálenost. Stromy, kostry, kružnice, minimální kostry. | |
4. | Nejkratší cesty, algoritmy hledání nejkratších cest 1 -> n. Algoritmy hledání nejkratších cest n -> n, planarita. | |
5. | Toky v sítích, určení maximálního toku v síti. Nejlevnější cirkulace, párování, řešení přiřazovací úlohy. | |
6. | Stavový prostor úloh, prohledávání, heuristické hledání. Turingovy stroje. | |
7. | Třídy složitosti, NP-úplné problémy. Aproximační algoritmy. |
Osnovy cvičení:
1. | Indukce, rekurze, rekurence Druhy stromů a jejich reprezentace, procházení stromů. Vlastnosti grafů (izomorfismus, souvislost, komponenty, stupně uzlů). Silná souvislost, rozklad na silné komponenty, topologické uspořádání. Reprezentace a procházení grafu, použití. Určení Eulerova tahu, úloha čínského listonoše, zadání semestrální práce. Určování charakteristik (nezávislost, dominance, barevnost, cyklomatické číslo). | |
2. | Stromy, kostry a minimální kostry. Nejkratší cesty. Nejkratší cesty, planarita, konzultace k semestrální úloze. Maximální tok v síti, cirkulace, párování. Algoritmy heuristického hledání. Turingovy stroje. |
Literatura:
Kolář, J. ''Teoretická informatika''. Praha: Česká informatická společnost, 2000. ISBN 80-900853-8-5.
Demel, J. ''Grafy a jejich aplikace''. Praha: Academia, 2002. ISBN 80-200-0990-6.
Kolář, J. ''Theoretical Computer Science''. Praha: ČVUT, 1998. ISBN 80-01-01788-5.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. ''Introduction to Algorithms''. The MIT Press, 2001. ISBN 0262032937.
Sedgewick, R. ''Algorithms in Java, Part 5: Graph Algorithms (3rd Edition)''. Addison-Wesley Professional, 2003. ISBN 0201361213.
Požadavky:
Předpokládá se znalost základních abstraktních datových typů, jejich efektivní implementace a použitelnost při řešení grafových problémů na úrovni předmětu BI-EFA. Studenti by měli pasivně zvládat základní důkazové postupy známé z povinných matematických předmětů (důkaz úplnou indukcí, důkaz sporem, konstruktivní důkaz) a vedle návrhu nového či modifikace známého algoritmu by měli být schopni provést jeho analýzu složitosti.
|
Předmět je zahrnut do těchto studijních plánů:
Stránka vytvořena 29. 4. 2024, semestry: Z/2023-4, Z/2019-20, L/2021-2, L/2020-1, L/2022-3, Z/2021-2, L/2019-20, Z/2022-3, Z/2020-1, L/2023-4, Z/2024-5, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: J. Novák, I. Halaška |