[ATG] Algoritmická teória grafov

BCKIS

[ATG] Algoritmická teória grafov

Výsledky vzdelávania:

Štúdiom predmetu študent získa základné poznatky z algoritmickej teórie grafov, ktoré mu umožňujú ich použitie pri riešení technických úloh v inžinierskej praxi.
Po absolvovaní predmetu študent:
– pozná základné štruktúry teórie grafov,
– pozná základné grafové algoritmy ,
– vie implementovať základné grafové algoritmy,
– má schopnosť aplikovať získané poznatky pri riešení praktických úloh.

Informačný list predmetu
Vysoká škola: Žilinská univerzita v Žiline
Fakulta: Riadenia a informatiky
Kód predmetu: 5BA126Názov predmetu: algoritmická teória grafov (ATG)
Druh, rozsah a metóda vzdelávacích činností:
Týždenný počet hodín výučby vo forme prednášky,
cvičenia, semináre, klinickej praxe
Prednášky: 2.0 Cvičenia: 0.0 Lab.cvičenia: 2.0
Metóda, akou sa vzdelávacia činnosť uskutočňujeVýučba sa uskutočňuje prezenčne
Metódy dosiahnutia výsledkov vzdelávania
Počet kreditov: 5.0
Záťaž študenta: hodín
Špecifikácia záťaže:
Odporúčaný semester/trimester štúdia: 2. ročník, letný semester
Stupeň štúdia: 1.
Podmieňujúce predmety:
Prerekvizity:

Korekvizity:
Podmienky na absolvovanie predmetu:
Priebežné hodnotenie:
40% = 40 bodov
Podmienkou pre úspešné absolvovanie cvičení k predmetu je systematická práca na cvičeniach posudzovaná splnením nasledujúcich kritérií:
- Aktívna účasť na cvičeniach
- Úspešné zvládnutie krátkych testov zameraných na základené definície zadávaných na každom cvičení
- Úspešné zvládnutie záverečného písomného testu v 12. týždni semestra
- Za náročnejšie počítačové implementácie môže dostať študent body naviac

Záverečné hodnotenie:
60% = 60 bodov
Podmienkou pre úspešné absolvovanie predmetu je získanie minimálne 61 zo 100 bodov za prácu v semestri a vykonanie skúšky z predmetu. Skúška je ústna a je zameraná hlavne na pochopenie pojmov a algoritmov.

Výsledné hodnotenie predmetu:
100 - 92 A
91 - 84 B
83 - 76 C
75 - 68 D
67 - 61 E

Pre prihlásenie na skúšku musí študent dosiahnuť 20 bodov.
Výsledky vzdelávania:
Štúdiom predmetu študent získa základné poznatky z algoritmickej teórie grafov, ktoré mu umožňujú ich použitie pri riešení technických úloh v inžinierskej praxi.
Po absolvovaní predmetu študent:
- pozná základné štruktúry teórie grafov,
- pozná základné grafové algoritmy ,
- vie implementovať základné grafové algoritmy,
- má schopnosť aplikovať získané poznatky pri riešení praktických úloh.
Stručná osnova predmetu:
Stručná osnova predmetu:
Prednášky:
1. Základné pojmy teórie grafov: Základy kombinatoriky. Reprezentácia grafov.
2. Cesty v grafoch, súvislosť a prieskum grafov: Súvislosť a Tarryho algoritmus.
3. Algoritmy, výpočtová zložitosť a NP-ťažké úlohy: Výpočtová zložitosť a polynomiálne redukcia úloh.
4. Najkratšia cesta v grafe a digrafe. Hľadanie cyklov zápornej ceny: Algoritmy pre hľadanie najkratšej cesty v grafe a digrafe.
5. Stromy, kostra grafu a cesta maximálnej priepustnosti: Prehľadávanie grafu do šírky a do hĺbky, Kruskalov algoritmus a hľadanie cesty maximálnej priepustnosti.
6. Acyklické digrafy a úloha časového plánovania: Acyklické digrafy. Monotónne očíslovanie. Sieťová analýza-metóda CPM.
7. Toky v sieťach: Ford-Fulkersonov algoritmus pre maximálny tok v sieti.
8. Najlacnejší maximálny tok a ďalšie tokové úlohy: Najlacnejší maximálny tok v sieti.
9. Eulerovské ťahy. Párenia. Úloha čínskeho poštára: Algoritmy pre eulerovský ťah v grafe a digrafe, Edmonsov algoritmus pre úlohu čínskeho poštára.
10. Úloha obchodného cestujúceho: Heuristiky pre úlohu obchodného cestujúceho.
11. Mediány a centrá. Kliky, nezávislé množiny a pokrývacie množiny: Alokačné úlohy, nezávislá množina a klika.
12. Farbenie grafov: Farbenie grafov. Rovinné grafy

Cvičenia a laboratórne cvičenia:
1.Binárne relácie a opakovanie základov kombinatoriky.
2.Výpočtová zložitosť a polynomiálne redukcia úloh.
3.Súvislosť a Tarryho algoritmus.
4.Algoritmy pre hľadanie najkratšej cesty v grafe a digrafe. Hľadanie cyklu zápornej ceny.
5.Kruskalov algoritmus a hľadanie cesty maximálnej priepustnosti.
6.Acyklické digrafy. Monotónne očíslovanie. Sieťová analýza-metóda CPM.
7.Ford-Fulkersonov algoritmus pre maximálny tok v sieti.
8.Najlacnejší maximálny tok v sieti.
9.Algoritmy pre eulerovský ťah v grafe a digrafe, Edmonsov algoritmus pre úlohu čínskeho poštára.
10.Heuristiky pre úlohu obchodného cestujúceho.
11. Alokačné úlohy, nezávislá množina a klika.
12. Farbenie grafov. Rovinné grafy.
Odporúčaná literatúra:
Odporúčaná literatúra:
Palúch, S.: Teória grafov, EDIS, Žilina, ISBN 80-7100-874-5 (dostupné aj na http://frcatel.fri.uniza.sk/users/paluch/ resp. http://frcatel.fri.uniza.sk/users/paluch/grafy-ps.zip )
Plesník, J.: Grafové algoritmy, VEDA, SAV Bratislava 1983
Evans, J.,R., Minieka, E.: Optimizarion Algorithms for Networks and Graphs, Marcel Decker, New Yourk, second edition 1992, ISBN 0-8247-8602-5
Gross,J., Yellen, J.: Graph Theory and its Applications, CRC Press, 1998, ISBN 0-8493-3982-0
Jazyk, ktorého znalosť je potrebná na absolvovanie predmetu: slovenský/anglický
Poznámky:
Hodnotenie predmetov:
Celkový počet hodnotených študentov: 1121
ABCDEFX
25.16 % 8.74 %17.93 % 8.30 %14.99 %24.89 %
ABCDEFX
25.16 % 8.74 %17.93 % 8.30 %14.99 %24.89 %
Vyučujúci:
Dátum poslednej zmeny: 2021-08-25 06:20:00.000
Garant predmetu: Ing. Tomáš Majer, PhD.
Schválil: prof. Ing. Pavel Segeč, PhD.
ZDROJ: https://vzdelavanie.uniza.sk/vzdelavanie/planinfo.php?kod=274633&lng=sk