Matematická olympiáda – kategorie P

Knihovna základních algoritmů

Pokud ve svém řešení teoretické úlohy chcete použít nějaký základní algoritmus, jako třeba binární vyhledávání v uspořádaném poli, nemusíte ho detailně popisovat. Někdy ale nemusí být jasné, které algoritmy jsou „dostatečně základní“.

Uvádíme proto seznam algoritmů a datových struktur, které v MO-P považujeme za natolik známé, že se na ně v řešení stačí odkázat a není potřeba uvádět detaily. Pokud si algoritmus potřebujete nějak přizpůsobit, stačí popsat pouze změny od základní verze.

Ostatní algoritmy je potřeba popsat celé.

Matematika

Euklidův algoritmus

• Nalezení největšího společného dělitele čísel x,y
• Čas \mathcal{O}(\log x + \log y)
• zdroj: KSP – Teorie čísel

Eratosthénovo síto

• Nalezení prvočísel od 2 do n
• Čas \mathcal{O}(n \log \log n)
• zdroj: KSP – Teorie čísel

Faktorizace

• Rozklad čísla n na součin prvočísel zkoušením dělitelů až po \sqrt{n}
• Čas \mathcal{O}(\sqrt{n})

Posloupnosti

Označme n délku posloupnosti.

Merge sort

• Třídění sléváním
• Čas \mathcal{O}(n \log n)
• zdroj: KSP – Třídění, Průvodce – kapitoly 3.2 a 10.2.

Bucket sort

• Přihrádkové třídění
• Čas \mathcal{O}(n + r), kde n je počet prvků a r je jejich rozsah
• zdroj: Průvodce – kapitola 3.4

Binární vyhledávání

• Nalezení prvku x v setříděné posloupnosti, případně největšího prvku \leq x
• Čas \mathcal{O}(\log n)
• zdroj: KSP – Binární vyhledávání, Průvodce – kapitola 1.2.

Grafy

Označme n počet vrcholů grafu a m počet jeho hran.

Prohledávání do hloubky

• Čas \mathcal{O}(n + m)
• zdroj: KSP – Grafy, Průvodce – kapitola 5.6.

Prohledávání do šířky

• Nalezení nejkratší cesty ze startu do všech vrcholů v neohodnoceném grafu
• Čas \mathcal{O}(n + m)
• zdroj: KSP – Grafy, Průvodce – kapitola 5.2.

Dijkstrův algoritmus

• Nalezení nejkratší cesty ze startu do všech vrcholů v ohodnoceném grafu s nezápornými délkami hran
• Čas \mathcal{O}(m + n \log n)
• zdroj: KSP – Halda a cesty, Průvodce – kapitola 6.2.

Bellman-Fordův algoritmus

• Nalezení nejkratší cesty ze startu do všech vrcholů v ohodnoceném grafu
• Čas \mathcal{O}(nm)
• zdroj: Průvodce – kapitola 6.3.

Floydův-Warshallův algoritmus

• Nalezení nejkratší cesty z každého do každého vrcholu v ohodnoceném grafu
• Čas \mathcal{O}(n^3)
• zdroj: Průvodce – kapitola 6.3

Jarníkův algoritmus

• Nalezení minimální kostry pomocí řezů a haldy
• Čas \mathcal{O}(m + n \log n)
• zdroj: Průvodce – kapitola 7.2

Kruskalův algoritmus

• Nalezení minimální kostry pomocí Disjoin set union
• Čas \mathcal{O}(m \log n)
• zdroj: KSP – Minimální kostry, Průvodce – kapitola 7.4

Topologické uspořádání

• Uspořádání všech vrcholů orientovaného acyklického grafu tak, aby hrany vedly po směru uspořádání
• Čas \mathcal{O}(n + m)
• zdroj: Průvodce – kapitola 5.8

Geometrie

Základy

• Vzdálenost dvou bodů (čas \mathcal{O}(1))
• Vzdálenost bodu a přímky (čas \mathcal{O}(1))
• Průnik přímek, úhly jimi svírané (čas \mathcal{O}(1))
• Obsah mnohoúhelníku (čas \mathcal{O}(n), kde n je počet vrcholů)
• zdroj: KSP – Geometrie

Konvexní obal

• Nalezení konvexního obalu n bodů
• Čas \mathcal{O}(n \log n), případně \mathcal{O}(n) s již seřazenými body
• zdroj: KSP – Geometrie, Průvodce – kapitola 16.1.

Datové struktury

U datových struktur uvádíme operace, které podporují, s jejich složitostmi.

Fronta

• Enqueue: Přidání prvku na konec v \mathcal{O}(1)
• Dequeue: Odebrání prvku ze začátku v \mathcal{O}(1)
• zdroj: KSP – Základní algoritmy

Zásobník

• Push: Přidání prvku na konec v \mathcal{O}(1)
• Pop: Odebrání prvku z konce v \mathcal{O}(1)
• zdroj: KSP – Základní algoritmy

Nafukovací pole

• Append: Přidání prvku v amortizovaně \mathcal{O}(1)
• zdroj: Průvodce – kapitola 9.1

Prefixové součty

• Build: Vybudování v \mathcal{O}(n)
• Query: Dotaz na součet intervalu v \mathcal{O}(1)
• zdroj: KSP – Základní algoritmy

2D prefixové součty

• Build: Vybudování v \mathcal{O}(nm), kde n a m jsou strany mřížky
• Query: Dotaz na součet obdélníka v \mathcal{O}(1)
• zdroj: KSP – Základní algoritmy

Vyhledávací strom

• Reprezentace množiny prvků, které umíme porovnávat.
• Find: Nalezení pozice daného prvku, případné zahlášení jeho neexistence v \mathcal{O}(\log n)
• Insert: Přidání prvku v \mathcal{O}(\log n)
• Delete Smazání prvku v \mathcal{O}(\log n)
• zdroj: KSP – Vyhledávací stromy, Průvodce – kapitoly 8.1 a 8.2.

Písmenkový strom (Trie)

• Reprezentace množiny řetězců nad konstantně velkou abecedou.
• Find: Zjištění, zdali je slovo ve stromě v \mathcal{O}(\ell), kde \ell je délka slova
• Insert: Přidání slova v \mathcal{O}(\ell)
• Delete Smazání slova v \mathcal{O}(\ell)
• zdroj: Průvodce – kapitola 4.3

Binární halda

• Min: Vrácení minima v \mathcal{O}(1)
• ExtractMin: Odstranění minima v \mathcal{O}(\log n)
• Insert: Přidání prvku v \mathcal{O}(\log n)
• Delete Smazání prvku v \mathcal{O}(\log n), známe-li jeho pozici v haldě
• zdroj: KSP – Halda a cesty

Disjoint set union

• Find: Nalezení reprezentanta množiny obsahující daný vrchol v amortizovaně \mathcal{O}(\alpha(n)), kde \alpha je inverzní Ackermannova funkce, která sice roste do nekonečna, ale mnohem pomaleji než logaritmus.
• Union: Sjednocení dvou množin obsahujících vrcholy u a v v amortizovaně \mathcal{O}(\alpha(n))
• zdroj: KSP – Minimální kostry, Průvodce – kapitola 7.4

Intervalový strom (s línou aktualizací)

• Pro zvolenou asociativní operaci (minimum, maximum, součet, …) a posloupnost prvků x_1,\ldots,x_n
• Build: Vybudování v \mathcal{O}(n)
• Query: Určení hodnoty operace provedené na všechny prvky s indexy v daném intervalu v \mathcal{O}(\log n)
• UpdatePoint: Aktualizace prvku v \mathcal{O}(\log n)
• Je-li operace minimum, maximum či součet, můžete dále bez popisu používat i operaci UpdateRange: Ke všem hodnotám s indexy v daném intervalu přičte zadané číslo, pracuje v čase \mathcal{O}(\log n).
• Potřebuje-li vaše řešení operaci UpdateRange v jiných situacích (jiná asociativní operace, jiný druh změny hodnot na intervalu), musíte vysvětlit, jak ji implementujete.
• zdroj: Průvodce – kapitola 4.5