Všeobecně

Rychlé neformální určování asymptotické složitosti. Identifikace NP-těžkých úloh: Knapsack, splnitelnost fromulí. V grafu: Nejdelší cesta, barevnost, nezávislost, klikovost apod.

Algoritmická paradigmata brute force, greedy, divide and conquer.

Hlavní datové struktury, (prioritní) fronta, halda, hash tabulky, binární strom, zásobník

Rekurze, backtrack

Principy rychlého řazení, Insert-Merge-Quick-Radix-Bucket Sort. Binární hledání

Grafy, jejich efektivní implementace, BFS, DFS, Eulerova formule.

Princip dynamického programování. Varianty s vícerozměrnou tabulkou, memoizace, knapsack, LCS, LIS, optimální násobení matic, řezání tyče aj.

Bitové manipulace jako součást řešení jiných témat

Předpočítání a předřazení dat, prefixová suma

Součet aritmetické a geometrické posloupnosti, Fibonacciho, Catalanova čísla

Matematika vůbec

A speciálně

Cesty v grafu (Dijkstra, Bellman-Ford, Floyd-Warshall), MST (Kruskal, Prim), Union-Find.

Zpracování stromů v lineárním čase, závorkové struktury

Specifika DAG, topologické uspořádání, mosty, cutvertices

Teorie čísel: Dělitelnost, GCD, Euklidův algoritmus, Malý Fermat, rozklad čísla, Eratosthenovo síto, modulární aritmetika, práce s velkými čísly (> 10^20), rychlé mocnění (matic), číselné soustavy

Kombinatorika: Permutace, binomiální koeficienty,

Analytická geometrie a výpočty ve 2D a 3D, počítání s vektory, výpočetní geometrie (konvexní obálka, sweep line, sliding window)

Klasické algoritmické “legendy”: Hanojské věže, Josephus problem , Collatz 3n+1, 8 dam na šachovnici…

Hledání v textu, Aho-Corasick, slovníkové stromy, trie

Hry na principu odebírání zápalek, nim, jádro grafu

Toky v sítích (Ford -Fulkerson, Dinic), maximální párování v (bipartitních) grafech

Kombinatorické generování složitějších objektů (Polyomina, grafové struktury)

Vyhledávací/intrevalové/speciální stromy .

.

Průchod grafem do šířky, BFS, používá frontu.
– Může posloužit k: Nalezení komponent souvislosti, určení vzdálenosti jiných vrcholů od daného vrcholu, určení bipartitnosti (= dvoubarevnosti) grafu.

Průchod grafem do hloubky, DFS, používá zásobník nebo rekurzi.
– Může posloužit k: Nalezení komponent souvislosti, určení topologockého uspořádání orientovaného grafu.
– Po vhodné a nevelké modifikaci poslouží k nalezení silně souvislých komponent v orientovaném grafu, nalezení mostů a artikulací v neorientovaném grafu.
– Nelze ho použít k určení vzdálenosti jiných vrcholů od daného vrcholu.

Dijkstrův algoritmus
– Najde nejlacinější nebo nejdražší cestu v nezáporně ohodnoceném grafu, orientovaném i neorientovaném.
– Může existovat s prioritní frontou i bez ní. Při vhodné implementaci se od Primova algoritmu hledání minimální kostry liší jen jedním řádkem.
– Je to pohledávání do šířky s prioritou nejbližších vrcholů.

Bellman-Fordův algoritmus
– Detekuje existenci cyklů s negativní váhou. Nahradí Dijkstrův algoritmus v případě orientovaného grafu obsahujícího také záporně vážené hrany.

Floyd-Warshallův algoritmus
– Najde nejkratší cesty mezi všemi dvojicemi uzlů ve váženém orientovaném i neorientovaném grafu, je-li zaručeno, že graf je bez negativních cyklů.

Nejdelší cesty v grafu
– Efektivně to jde jen v acyklickém orientovaném grafu (DAG-u) pomocí topologického uspořádání a pak jednoho průchodu ve směru toho uspořádání, v ostatních netriviálních případech je to NP-těžké.

Primův algoritmus hledání minimální kostry
– Může existovat s prioritní frontou i bez ní. Při vhodné implementaci se od Dijkstrova algoritmu hledání nejkratší cesty liší jen jedním řádkem.
– Nelze použít v orientovaném grafu

Kruskalův algoritmus hledání minimální kostry
– Typicky využívá Union-Find strukturu, hodí se na doplňování neúplných minimálních koster, budování kostry z větších kousků.
– Nelze použít v orientovaném grafu

Ford-Fulkersonův algoritmus hledání maximálního toku
– Najde také maximální párování v bipartitním grafu.

Maximální párování v neváženém bipartitním grafu
– Metoda alternující cesty, prakticky DFS

Detekce silně souvislých komponent
– Prohledáváním do hloubky, algoritmus Kosaraju-Sharir anebo Tarjanův.
– Tarjanův postup se použije při hledání mostů a artikulací v neorientovaném grafu.

Topologické uspořádání
– Prohledáváním do hloubky a registrací zavíracích časů nebo postupným usekáváním kořenů (použij frontu).

Různé extremální cesty
– Průchodem uzlů v pořadí jejich topologického uspořádání.
– Faktická podoba mnoha snazších úloh DP.
– Ilustrace: pdf nebo ppt

Eulerova cesta/kružnice
– Projde každou hranou jednou. Konstruovatelná v čase Theta (N) hladovým přístupem: přidávej kružnice, dokud jsou.

Nejkratší cesty
– jako v obecném grafu.

Nejdelší cesty
– vyjdi z libovolného uzlu x, najdi jemu nejvzdálenější y (BFS), pak vyjdi z y a najdi jemu nejvzdálenější w. Nejdelší cesta ve stromu je ta z y do w. Platí ve vážených i nevážených neorientovaných stromech. Nebo zvol libovolně kořen a navrhni rekurzivní algoritmus. Vždy Theta(N).

Vizualizace stromové struktury

Nejdelší společná podposloupnost
– Standardní ukázky

Nejdelší rostoucí podposloupnost
– Standardní ukázky Optimální násobení matic
– Anglicky: Matrix chain multiplication
Optimální lámání klacku

Optimální vyhledávací strom

DP v kuchařkách na MFF: html výklad I , html výklad II, přibližně shrnuto v pdf.

Konvexní obálka (Convex hull)
– Seznam algoritmů na výpočet konvexní obálky, kódy v jednotlivých odkazech.

– Pojem zametací přímky (sweep line)