456-0097/01 – Grafové algoritmy (GRA)

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íPovinnostpovinně volitelný
RočníkSemestrzimní
Jazyk výukyčeština
Rok zavedení1997/1998Rok zrušení2003/2004
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+1

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Cílem předmětu je seznámit studenty se základními grafovými algoritmy, možnostmi jejich využití a problémy, které se mohou řešit pomocí těchto algoritmů.

Vyučovací metody

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.

Povinná literatura:

Sylaby předmětu. Internetové zdroje. Nešetřil J.: Teorie grafů, SNTL, Praha, 1979. Plesník J.: Grafové algoritmy, VEDA, Bratislava, 1983. Demel J.: Grafy, SNTL, Praha, 1989 McHugh J. A.: Algorithmic graph theory, PRENTICE HALL, 1990. Unčovský L. a kol.: Modely sieťovej analýzy, ALFA, Bratislava, 1991. Cormen T.H., Leiserson Ch.E., Rivest R.L.: Introduction to algorithms, The MIT Press, 1990. Kučera L.: Kombinatorické algoritmy, SNTL Praha, 1991

Doporučená literatura:

Forma způsobu ověření studijních výsledků a další požadavky na studenta

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: 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ů. 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. 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. 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. Tranzitivní uzávěr a tranzitivní redukce. 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. Eulerovské tahy - podmínky existence; algoritmus pro nalezení eulerova tahu v grafu (pokud existuje); úloha čínského pošťáka. Vrcholové a hranové barvení grafu. Rovinné grafy. 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. Heuristické algoritmy - izomorfismus, kliky a nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 1960/1961 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 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
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
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (B2612) Elektrotechnika a informatika (1801R001) Informatika P čeština Ostrava 3 povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinně volitelný stu. plán
2000/2001 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinně volitelný stu. plán

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

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku