Algoritmická složitost

Popis problematiky algoritmické složitosti jednak časové, tak i prostorové, metody jejího vyjádření a efektivní porovnání algoritmů pomocí těchto metrik, ukázky složitosti na základních grafových operacích.

Pokročilejší metodiky programování

Popis pokročilejších metodik programování jako jsou rekurze či dynamické programování, využití pro prohledávání grafů.

Pokročilé metody třídění a vyhledávání

Popis pokročilých metod pro problematiku třídění a vyhledávání (např. merge sort, quicksort, BB(α) strom, B-strom, vyhledávání v textu Boyer-Mooreovým algoritmem, apod.)

Standardní datové algoritmy

Popis různých metod standardních algoritmů na řazení a vyhledávání včetně odpovídajících vlastností algoritmů, snížení složitosti zacházení s grafy zavedením efektivnějších metod správy dat.

Heuristické řešení problémů

Hladové algoritmy a zavedení heuristik, představení jednoduchosti hladových algoritmů na jednoduchém případě minimální kostry grafu.

Třídy složitosti

Zavedení tříd složitosti P a NP, jejich rozdíl a potenciální vztah, NP-úplné problémy, předvedení problému barvení jako NP-úplného problému.

Aproximační a přibližné algoritmy

Uvedení do problematiky přibližných a aproximačních algoritmů, ukázka metod řešení problému barevnosti polynomiálními algoritmy.

Graf a jeho uložení v počítači

Problematika reprezentace reálných problémů grafem a jeho efektivní uložení v počítači s uvážením řešeného problému, orientované grafy, využití obecných definic algoritmické složitosti 

Průchody grafem

Základní metody průchodu grafem do hloubky a šířky a jejich využití pro charakterizaci grafu a realizaci reálných úloh, využití prohledávání pro algoritmus nejkratší cesty. Využití pokročilých metodik algoritmů jako rekurze či dynamické programování.

Stromy

Charakterizace stromů, jejich kódování a tím umožněné efektivní uložení v paměti, související problém isomorfismu stromů. 

Problém minimální kostry

Problém hledání kostry a její minimalizace, složitost celého přístupu a jednoduchý hladový algoritmus na řešení, využívá znalostí z obecných heuristických metod.

Problém barvení

Problém barvení grafu, využití pro plánovací algoritmy, složitost tohoto problému a jeho NP-úplnost, souvislost s obecnou definicí tříd složitosti.

Přibližné algoritmy na barvení grafů

Algoritmy na přibližné barvení grafů, přístupy na řešení složitých algoritmů polynomiálně s určitou mírou nepřesnosti, souvisí s obecnou definicí aproximačních a přibližných algoritmů.