460-4055/01 – Grafové algoritmy a komplexní sítě (GAKS)
| 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 | volitelný odborný |
| Ročník | 2 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2011/2012 | Rok zrušení | 2014/2015 |
| 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 komplexními sítěmi, oblastí se širokým interdisciplinárním přesahem. Komplexní sítě jsou reálné rozsáhlé sítě (technologické, informační, sociální a biologické) jejichž vlastnostmi, jednotlivými modely a vývojem se předmět dále zabývá. Hlavními oblastmi zájmu předmětu jsou typy komplexních sítí, algoritmy pro efektivní analýzu sítí, matematické modely sítí, generativní modely a dynamické procesy v sítích. Protože se sítě modelují jako grafy, je nezbytnou součástí předmětu je také zopakování či doplnění potřebného matematického aparátu z teorie grafů, lineární algebry nebo statistiky.
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/
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Další požadavky na studenta najsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
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.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky