456-0313/01 – Grafové algoritmy (GAL)
| Garantující katedra | Katedra informatiky | Kredity | 4 |
| Garant předmětu | RNDr. Eliška Ochodková, Ph.D. | Garant verze předmětu | RNDr. Eliška Ochodková, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
| Ročník | 3 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2003/2004 | Rok zrušení | 2009/2010 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Po absolvování předmětu student:
1. Bude umět vybrat vhodný grafový algoritmus a tento naimplementovat a použít pro řešení daného problému.
2. Bude schopen provést experimenty nad vybranými kolekcemi dat, analyzovat jejich výsledky.
3. Bude umět interpretovat výsledky experimentů a navrhnout případné modifikace použitých algoritmů a postupů.
4. Bude umět shrnout vlastnosti reálných sítí reprezentovaných testovacími kolekcemi dat.
5. Bude umět pracovat na projektu v týmu.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Projekt
Anotace
Cílem předmětu je seznámit studenty s grafovými algoritmy, možnostmi jejich využití a problémy, které se pomocí těchto algoritmů mohou řešit. Dále se předmět zabývá tzv. komplexními sítěmi, což jsou rozsáhlé grafy, jejich vlastnostmi a jejich jednotlivými typy (modely).
Povinná literatura:
1. Barabási A.-L.: V pavučině sítí, Paseka 2005
2. M. E. J. Newman: The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003
3. A.L. Barabasi: Scale Free Networks
4. S. H. Strogatz: Exploring Complex Networks
5. R. Albert and L.A. Barabasi: Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47-97 (2002).
6. Ochodková E.: Výuková opora předmětu (grant FR 1719/2003)
7. Večerka A.: Grafy a grafove algoritmy, PřF UP Olmouc, 2007
8. Nešetřil J.: Teorie grafů, SNTL, Praha, 1979.
9. Plesník J.: Grafové algoritmy, VEDA, Bratislava, 1983.
10. Demel J.: Grafy, SNTL, Praha, 1989
11. McHugh J. A.: Algorithmic graph theory, PRENTICE HALL, 1990.
12. Unčovský L. a kol.: Modely sieťovej analýzy, ALFA, Bratislava, 1991.
13. Cormen T.H., Leiserson Ch.E., Rivest R.L.: Introduction to algorithms, The MIT Press, 1990.
14. Kučera L.: Kombinatorické algoritmy, SNTL Praha, 1991
15. Bang-Jensen J., Guitn G.: Digraphs, Theory, Algorithms and Applications, Springer 2002
16. Jungnickel D.: Graphs, Networks and Algorithms, Springer 2005
Doporučená literatura:
1. The Stony Brook Algorithm Repository, http://www.cs.sunysb.edu/~algorith/
2. Journal of Graph Algorithms and Applications, ISSN: 1526-1719, http://www.cs.brown.edu/publications/jgaa/
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu - zvládnutí vybraného projektu: kontrolovat spočívá v posouzení pochopení problému, výběru algoritmu, implementace algoritmu, funkčnosti aplikace, provedených experimenty a interpretace jejich výsledků, prezentace projektu. K zápočtu musí student získat alespoň (>=) 23 bodů za projekt (z 45 možných).
Písemná zkouška.
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1. Reprezentace grafů - graficky, maticově, seznamem hran nebo seznamem vrcholů a jejich sousedů; volba reprezentace grafu v závislosti na aplikaci. Prohledávání grafů - základní algoritmus, prohledávání do šířky a do hloubky; zjišťování dostupnosti vrcholů.
2. Nejkratší cesty - základní algoritmus, modifikovaný alg., Bellman-Fordův algoritmus; úpravy algoritmů při hledání nejdelších cest. Topologické uspořádání vrcholů a hran - užití topolog. uspořádání k hledání nejkratších cest; test acykličnosti grafu.
3. Souvislé a silně souvislé grafy. Komponenty souvislosti - pomocí mocnin matice sousednosti (jejich součtová matice); Floydův algoritmus - testování existence cyklů se zápornou cenou.
4. Kostra grafu - Jarníkův a Borůvkův algoritmus. Souvislost s nejkratšími cestami v neorientovaném grafu. Kruskalův a Primův algoritmus.
5. Párování v bipartitních grafech - maximální párování, nejlevnější párování v bipartitních grafech. Maximální párování v obecných grafech - redukce grafu.
6. Eulerovské tahy - podmínky existence; algoritmus pro nalezení eulerova tahu v grafu (pokud existuje); úloha čínského pošťáka.
7. Vrcholové a hranové barvení grafu. Rovinné grafy.
8. Toky v sítích - maximální tok - ekvivalence úlohy maximálního párování v bipartitním grafu a maximálního toku v specifické síti; Ford-Fulkersonův algoritmus; přípustný tok v síti. Nejlevnější cirkulace v síti.
9. Heuristické algoritmy - izomorfismus, kliky a nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.
10. Komplexní sítě, jejich typy a vlastnosti (small world effect, clustering, scale-free nets).
11. Modely sítí (náhodné sítě, Watts-Strogatz model, bezeškálové sítě).
12. Chyby, útoky, robustnost, stabilita, hledání v sítích, ...
Cvičení:
Demonstrace jednotlivých algoritmů na konkrétních příkladech.
Reprezentace grafů, prohledávání grafů.
Nejkratší cesty, topologické uspořádání vrcholů a hran, souvislé a silně souvislé grafy, komponenty souvislosti
Kostra grafu. Eulerovské tahy
Párování v bipartitních grafech, maximální párování v obecných grafech.
Vrcholové a hranové barvení grafu. Rovinné grafy.
Toky v sítích, nejlevnější cirkulace v síti.
Heuristické algoritmy - nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.
Projekty:
Cílem projektu je vytvořit aplikaci demonstrující schopnost studenta porozumět grafovým algoritmům a implementovat je.
Podmínky absolvování předmětu
Podmínky absolvování jsou definovány pouze pro konkrétní verzi předmětu a formu studia
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky