Differences

This shows you the differences between two versions of the page.

Link to this comparison view

courses:a4b36acm1:algoritmy [2018/10/03 03:51] (current)
Line 1: Line 1:
 +==== 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)\\
 +
 +
  
courses/a4b36acm1/algoritmy.txt · Last modified: 2018/10/03 03:51 (external edit)