![[ATG] Algoritmická teória grafov](https://www.kis.fri.uniza.sk/wp-content/themes/Divi-child/imgs/KIS-subject-default.png)
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: 5BA126 | Ná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čňuje | Vý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: 173
| |||||||||||||
| A | B | C | D | E | FX | ||||||||
| 34.10 % | 9.25 % | 21.39 % | 11.56 % | 19.08 % | 4.62 % | ||||||||
| Vyučujúci: | |||||||||||||
| Dátum poslednej zmeny: 2021-08-25 06:20:00.000 | |||||||||||||
| Garant predmetu: Ing. Tomáš Majer, PhD. | |||||||||||||
| Schválil: | |||||||||||||