==== Co se hodí ==== **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 . ---- . ^ **Grafové algoritmy** ^ **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 ^ **Orientované grafy** ^ **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.\\ ^ **(DAG) Acyklické orientované grafy** ^ **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: {{:courses:a4b36acm:origfpic.pdf| pdf}} nebo {{:courses:a4b36acm:origfpic.pptx| 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. ^ **Stromy** ^ **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).\\ [[http://en.wikipedia.org/wiki/File:Socotra_dragon_tree.JPG| Vizualizace stromové struktury]] \\ ^ **Algoritmy dynamického programování** ^ **Nejdelší společná podposloupnost**\\ -- [[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences|Standardní ukázky]] **Nejdelší rostoucí podposloupnost**\\ -- [[http://en.wikipedia.org/wiki/Longest_increasing_subsequence |Standardní ukázky]] ** Optimální násobení matic**\\ -- [[http://en.wikipedia.org/wiki/Dynamic_programming#Matrix_chain_multiplication |Anglicky: Matrix chain multiplication]]\\ ** Optimální lámání klacku**\\ **Optimální vyhledávací strom**\\ DP v kuchařkách na MFF: [[https://ksp.mff.cuni.cz/tasks/24/cook2.html| html výklad I ]], [[http://ksp.mff.cuni.cz/tasks/17/cook5.html| html výklad II]], [[http://ksp.mff.cuni.cz/study/cooks/cookbook-chapters/09-dynamicke-programovani.pdf| přibližně shrnuto v pdf.]] \\ ^ **Algoritmy výpočetní geometrie** ^ **Konvexní obálka (Convex hull)** \\ -- [[http://en.wikipedia.org/wiki/Convex_hull_algorithms#Algorithms|Seznam algoritmů ]] na výpočet konvexní obálky, kódy v jednotlivých odkazech. -- Pojem zametací přímky (sweep line)\\