Předmět Grafové algoritmy a základy teorie složitosti (BIK-GRA)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu BIK-GRA - Grafové algoritmy a základy teorie složitosti, Fakulta informačních technologií, České vysoké učení technické v Praze (ČVUT).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Grafové modely a odpovídající grafové algoritmy patří k základní informatické výbavě, která má řadu aplikací v infromatice i mimo ni. Cílem předmětu je rozvinout schopnosti rozpoznat, jaký grafový model odpovídá určité konkrétní úloze a jakým algoritmem je možné tuto úlohu řešit, a dále naučit určovat či odhadovat meze algoritmické složitosti a hranice praktické řešitelnosti jistých typů úloh.
Literatura
Kolář, J. ''Teoretická informatika''. Praha: Česká informatická společnost, 2000. ISBN 80-900853-8-5.Demel, J. ''Grafy a jejich aplikace''. Praha: Academia, 2002. ISBN 80-200-0990-6.Kolář, J. ''Theoretical Computer Science''. Praha: ČVUT, 1998. ISBN 80-01-01788-5.Cormen, T. H., Leiserson, C. E., Rivest, R. L. ''Introduction to Algorithms''. The MIT Press, 2001. ISBN 0262032937.Sedgewick, R. ''Algorithms in Java, Part 5: Graph Algorithms (3rd Edition)''. Addison-Wesley Professional, 2003. ISBN 0201361213.
Požadavky
Předpokládá se znalost základních abstraktních datových typů, jejich efektivní implementace a použitelnost při řešení grafových problémů na úrovni předmětu BI-EFA. Studenti by měli pasivně zvládat základní důkazové postupy známé z povinných matematických předmětů (důkaz úplnou indukcí, důkaz sporem, konstruktivní důkaz) a vedle návrhu nového či modifikace známého algoritmu by měli být schopni provést jeho analýzu složitosti.
Vyučující
Jiří Chludil