CourseWare Wiki
Switch Term
Winter 2023 / 2024
Winter 2018 / 2019
Summer 2017 / 2018
Search
Log In
b181
courses
a4b36acm2
algoritmy
Warning
This page is located in archive. Go to the latest version of this
course pages
.
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Go
Go
courses:a4b36acm2:algoritmy [2018/10/03 03:51]
courses:a4b36acm2: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/a4b36acm2/algoritmy.txt
· Last modified: 2018/10/03 03:51 (external edit)