PředmětyPředměty(verze: 948)
Předmět, akademický rok 2023/2024
  
Grafy v inženýrství - N445044
Anglický název: Graphs in Engineering
Zajišťuje: Ústav počítačové a řídicí techniky (445)
Fakulta: Fakulta chemicko-inženýrská
Platnost: od 2020
Semestr: letní
Body: letní s.:3
E-Kredity: letní s.:3
Způsob provedení zkoušky: letní s.:
Rozsah, examinace: letní s.:2/1, KZ [HT]
Počet míst: neurčen / neurčen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Úroveň:  
Pro druh:  
Další informace: http://moodle.vscht.cz/course/view.php?id=117
Poznámka: předmět je možno zapsat mimo plán
povolen pro zápis po webu
Garant: Cejnar Pavel RNDr. Mgr. Ph.D.
Termíny zkoušek   Rozvrh   
Anotace -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (12.11.2012)
Předmět je zaměřen na důležité problémy z teorie grafů s důrazem na inženýrské aplikace. Zabývá se základními pojmy teorie grafů, vlastnostmi různých typů grafů a metodami jejich číselného kódování se zaměřením na výpočetní složitost algoritmů. Systematicky probírá praktické grafové problémy (rozsáhlé soustavy rovnic, numerické aplikace, inženýrské problémy, úkoly operačního výzkumu/operační analýzy a rozhodovací problémy) a uvádí efektivní algoritmy jejich řešení.
Výstupy studia předmětu -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (13.11.2012)

Studenti budou umět:

  • Analyzovat průmyslovou úlohu pohledem teorie grafů a abstrahovat řešený problém

  • Řešit danou úlohu pomocí známých efektivních grafových algoritmů a dále budou mít přehled o mnoha problémech řešitelných pomocí různých grafových algoritmů

  • Rozlišovat výpočetně náročně řešitelné úlohy

Literatura -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (16.11.2012)

Z: Demel J.: Grafy a jejich aplikace. Academia, Praha, 2002. ISBN 80-200-0990-6.

Z: Matoušek J., Nešetřil J.: Kapitoly z Diskrétní matematiky. Matfyzpress, Praha, 1996. ISBN 80-85863-17-0.

D: Töpfer P.: Algoritmy a programovací techniky. Prometheus, Praha, 1995. ISBN 80-85849-83-6.

D: Kučera L.: Kombinatorické algoritmy. SNTL, Praha, 1983.

Studijní opory -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (13.11.2012)
  • elektronické materiály k předmětu dostupné na http://moodle.vscht.cz/course/view.php?id=117

  • Ondřej Čepek: Přednášky na MFF UK z předmětů Algoritmy a datové struktury I, Složitost I.

Metody výuky -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (13.11.2012)

Přednášky a cvičení.

Sylabus -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (12.11.2012)

1. Grafy, terminologie a základní definice, popis a kódování grafů.

2. Výpočetní a paměťová složitost algoritmů, NP-úplné problémy.

3. Acyklické očíslování, topologické uspořádání grafu, test acykličnosti grafu.

4. Prohledávání grafů a šířky a hloubky, vzájemná dosažitelnost uzlů a její analýza.

5. Výstupní zobrazení soustavy rovnic, párování v bipartitních grafech - přiřazovací problémy, souvislost s výstupním zobrazením soustavy rovnic.

6. Silné komponenty souvislosti, komponenty 2-souvislosti - ireducibilní subsystémy soustavy rovnic, záložní provoz a analýza kritických prvků sítě.

7. Kondenzace a hierarchická struktura grafu, splňování preferencí - optimální posloupnost výpočtů.

8. Nakreslení grafu do roviny - aplikace při návrhu tištěných spojů a integrovaných obvodů.

9. Hledání nejkratší cesty v grafu.

10. Kostra grafu - nalezení nezávislých obvodů, minimalizace potrubní sítě.

11. Toky v sítích, eulerovský tah.

12. Síťové grafy, maximální párování v obecném grafu - metoda kritické cesty.

13. Lokální a systematické prohledávání, programování s omezujícími podmínkami - hledání optimálních cest, diskrétní optimalizace, principy řešení, metoda větví a mezí.

14. Příklady technických a inženýrských aplikací teorie grafů.

Studijní prerekvizity -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (13.11.2012)

  • Matematika I

  • alespoň jeden předmět o programování v libovolném programovacím jazyku
Podmínky zakončení předmětu (Další požadavky na studenta) -
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (26.04.2018)

Pro udělení klasifikovaného zápočtu je třeba úspěšně vyřešit 5 zadaných úloh. Zadání jednotlivých úloh je postupně zveřejňováno v průběhu semestru a všechny úlohy je třeba úspěšně vyřešit nejpozději k určenému datu ve zkouškovém období.

Zátěž studenta
Činnost Kredity Hodiny
Účast na přednáškách 1 28
Příprava na přednášky, semináře, laboratoře, exkurzi nebo praxi 0.5 14
Práce na individuálním projektu 1 28
Účast na seminářích 0.5 14
3 / 3 84 / 84
Hodnocení studenta
Forma Váha
Aktivní účast na výuce 40
Protokoly z individuálních projektů 60

 
VŠCHT Praha