Ukončeno v akademickém roce 2014/2015

Grafové algoritmy a komplexní sítě

Typ studia	navazující magisterské
Jazyk výuky	čeština
Kód	460-4055/01
Zkratka	GAKS
Název předmětu česky	Grafové algoritmy a komplexní sítě
Název předmětu anglicky	Graph Algorithms and Complex Networks
Kreditů	4
Garantující katedra	Katedra informatiky
Garant předmětu	RNDr. Eliška Ochodková, Ph.D.

Osnova předmětu

Osnova předmětu
Přednášky:
1. Úvod. Komplexní sítě a jejich typy. Empirické studie komplexních sítí.
2. Vlastnosti sítí.
3. Počítačová reprezentace sítí.
4. Matematické základy komplexních sítí.
5. Teorie grafů a její aplikace v oblasti komplexních sítí.
6. Míry a metriky pro analýzu sítí.
7. Fundamentální algoritmy.
8. Modely sítí - náhodné sítě, Watts-Strogatz model.
9. Modely sítí - bezeškálové sítě.
10. Modely vývoje sítí.
11. Detekce komunit.
12. Procesy v sítích – perkolace, šíření informací.
13. Vizualizace sítí, používané algoritmy.
14. Software pro práci s komplexními sítěmi.

Cvičení:
Cílem cvičení je demonstrace jednotlivých algoritmů, problémů, vlastností a metod na konkrétních příkladech.
• Procvičení matematického aparátu z předchozího studia.
• Možnosti počítačová reprezentace různě rozsáhlých sítí (grafů) .
• Jednoduché algoritmy pro komplexní sítě (grafové algoritmy).
• Obtížnější algoritmy pro komplexní sítě.
• Vlastnosti komplexních sítí.
• Modely sítí.
• Modely vývoje sítí.
• Míry a metriky pro analýzu sítí.
• Detekce komunit.
• Procesy v sítích.
• Vizualizace sítí.
• Software pro práci s komplexními sítěmi I.
• Software pro práci s komplexními sítěmi II.

Projekty:
Cílem projektu je implementace aplikace dle zadání demonstrující schopnost studenta porozumět probíraným tématům. Studenti zpravidla pracují s reálnými rozsáhlými sítěmi jako je Web, sociální sítě a řeší problémy korespondující s obsahem předmětu.

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, , http://www.cs.brown.edu/publications/jgaa/

zpět na vyhledávání