grafové algoritmy

​ ​ Počet kreditů 3 Počet přednášek / týden 1 vh Počet cvičení / týden 1 vh Počet tutoriálů / semestr 2x 4h tutoriálů ​ ​ ​ Kapitoly z diskrétní matematiky: Matoušek, J., Nešetřil, J. ​

Cílem předmětu je navázat na základní fakta o grafech z předmětu Matematika II a rozšířit je o některé pokročilejší poznatky. Důraz bude tentokrát spíše na programátorský pohled na věc, přesto bude zároveň ale stavěno na pevném matematickém základě, protože z důkazů mnohých tvrzení přímo vyplývá implementace některých algoritmů. V rámci cvičení si potom studenti budou moci přednášené postupy v praxi vyzkoušet. ​ Grafy pojem grafu a základní tvrzení grafů se týkajících (opakování z MA2), reprezentace grafů v paměti počítače. Stromy pojem stromu a základní tvrzení stromů se týkajících (opakování z MA2), isomorfismus stromů. Průchody grafem průchod grafem do hloubky, průchod grafem do šířky, hledání nejkratší cesty v grafu (Dijkstrův algoritmus). Hledání minimální kostry grafu Kruskalův hladový algoritmus, Jarníkův algoritmus, Borůvkův algoritmus. Barvení grafu představení problému, algoritmy pro (neoptimální) obarvení grafu: naivní algoritmus, Welsh-Powellův algoritmus, DSATUR, RLF. Orientované grafy základní definice a tvrzení, topologické setřídění vrcholů. ​

​ ​   ENGLISH VERSION   ​   Podmínky použití   ​   Mapa stránek   ​   Kontakty   ​   Katalog bakalářských prací   ​   ​   ​   ​ Unicorn | Unicorn Systems | Unicorn Universe | Unicorn College © Unicorn College 2011