Differences

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

--- courses:a4b36acm1:algoritmy [2018/10/03 03:51]
+++ 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)\\