460-4039/01 – Grafové algoritmy (GAL)

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íkSemestrzimní
Jazyk výukyčeština
Rok zavedení2010/2011Rok zrušení2010/2011
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+5

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/

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

Prezenční forma (platnost od: 2010/2011 zimní 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.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2010/2011 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2649) Elektrotechnika (2601R004) Měřicí a řídicí technika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2649) Elektrotechnika (2602R014) Aplikovaná a komerční elektronika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2649) Elektrotechnika (3901R039) Biomedicínský technik (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2649) Elektrotechnika (3907R001) Elektroenergetika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2601T013) Telekomunikační technika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (N2649) Elektrotechnika (2601T004) Měřicí a řídicí technika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (N2649) Elektrotechnika (2612T015) Elektronika (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (N2649) Elektrotechnika (3901T009) Biomedicínské inženýrství (01) Exchange Students P čeština Ostrava volitelný odborný stu. plán
2010/2011 (N2649) Elektrotechnika (3907T001) Elektroenergetika (01) Exchange Students P čeština Ostrava 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