460-4055/01 – Grafové algoritmy a komplexní sítě (GAKS)

Garantující katedraKatedra informatikyKredity4
Garant předmětuRNDr. Eliška Ochodková, Ph.D.Garant verze předmětuRNDr. Eliška Ochodková, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník2Semestrzimní
Jazyk výukyčeština
Rok zavedení2011/2012Rok zrušení2014/2015
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
OH140 RNDr. Eliška Ochodková, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+1
kombinovaná Zápočet a zkouška 10+0

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

Kombinovaná forma (platnost od: 2011/2012 zimní semestr, platnost do: 2014/2015 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 45  23
        Zkouška Zkouška 55  20
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku
V - ECTS - mgr. 2014/2015 prezenční čeština volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - mgr. 2013/2014 prezenční čeština volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - mgr. 2012/2013 prezenční čeština volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - mgr. 2011/2012 prezenční čeština volitelný odborný 401 - Studijní oddělení FEI stu. blok