V této sekci nalezneš odkazy na studijní materiály, které tě uvedou do základních principů pro řešení algoritmických úloh, které se mohou objevit ve FIKSu.
Budeme se hodně odkazovat do knihy Průvodce Labyrintem Algoritmů, která je volně dostupná elektronicky. U matematičtějších témat se odkážeme na matematika.cz a pro obecné definice na Wikipedii.
Když řekneme problém nebo úloha, tak máme na mysli slovní nebo matematický popis vstupu a chtěného výstupu. Například: vstup by mohl být jízdní řád autobusových linek po republice a odkud kam se chceme dostat, a chtěný výstup je seznam spojů s přestupy, který Tě dostane ze startu do cíle.
Algoritmus je popis postupu řešení, který by měl být dostatečně podrobný, aby podle něj čtenář dovedl ze vstupů zjistit správný výstup.
FIKS má za cíl, aby sis vyzkoušel(a) návrh algoritmů. Hlavní je slovní popis algoritmu, který jasně vysvětluje co a jak se provede. Druhá část by měla ukázat, že je algoritmus „rychlý“. A nakonec, pokud je algoritmus složitý, tak je navíc potřeba pořádně dokázat jeho správnost.
Pole je nejjednodušší způsob reprezentace dat. Základní operace nad polem je setřídění. Nejčastěji najdeme třídění jako knihovní funkci o které nepotřebujeme nic vědět, takže jen zavoláme sort(pole) a je hotovo. Co ale dělá funkce sort pod pokličkou? a jak rychle třídit miliony prvků?
Když máme setříděné pole, tak lze velice rychle zjistit jestli v něm je nějaká hodnota.
Když chceme rychle sčítat prvky pole v daném rozmezí, tak lze pole předzpracovat a umožnit rychlé součty v O(1), potom ale už nepůjde rychle měnit prvky v poli. Pokud chceme mít rychlé součty i změnu prvků, je potřeba použít Intervalové stromy.
V polích lze hledat různé struktury. Jedna z nich je LIS, kde hledáme co nejvíce prvků pole (ne nutně sousedních) takových, že jsou rostoucí.
Při hledání vhodného algoritmu se můžeme setkat s matematickým problémem, a tak je dobré mít znalosti základů Teorie čísel, Kombinatoriky a Modulární aritmetiky.
Z této hluboké studně znalostí se nám nejčastěji bude hodit vědět co to jsou prvočísla, jak je rychle najít a jejich zajímavé vlastnosti. Každé číslo lze rozložit na unikátní seznam prvočísel, tomu se říká faktorizace (např.: 12=2*2*3). Jak hledání prvočísel tak i faktorizace se dá pro čísla do milionu algoritmicky rozumně řešit.
Kombinace a Variace jsou základní pojmy pokud chceme spočítat počet možností jak něco vybrat. Blízké jsou i Permutace, které vyjadřují konkrétní způsob jak se prohází prvky pole.
Rychlé předpočítání kombinačních čísel lze udělat Pascalovým trojúhelníkem.
Kolik bude hodin za 15 hodin, když je teď 10? Odpověď není 25, ale 1. Důvod je ten, že hodnoty hodin se opakují stále dokola, po 23 je 0 a na hodnotu 24 se nikdy nedostaneme. Když si navíc zakážeme minuty a sekundy, dostaneme něco čím se zabývá Modulární aritmetika.
Pro náš příklad s hodinami je 24 tzv. Modulo. Základní operace (+,-,*) fungují stejně jako běžně, po nich musíme přičíst nebo odečíst násobek 24 a dostat výsledek do rozmezí 0 až 23, to budeme značit operací 'mod 24'. Pro dělení je potřeba více fantasie, protože 1/5 není 12 minut (minuty jsme si zakázali), chceme tedy najít hodinu H, pro kterou 5H=1 mod 24. Toto splňuje pětka, protože 5*5 je 25 a to je mod 24 přesně 1 hodina. Takovéto řešení existuje vždy, pokud je modulo prvočíslo, a umí ho najít Eukleidův algoritmus.
V mnoha programovacích jazycích budeme implementovat modulo jako zbytek po dělení M, které se často značí znakem procento (%), tj. 27%4 vyjde 3. Dávejme pozor, protože zbytek po dělení může vyjít záporný, tedy -13%5 bude -3, modulo je vždy nezáporné, -13 modulo 5 je 2.
Fiks úlohy: Toasty
Celá řada problémů se dá vyřešit chytrým uložením dat. Potom lze nad daty provádět nejrůznější operace rychle. Následující seznam popisuje jaká datová struktura se dá použít na jaké operace.
Implementaci takovýchto struktur často nemusíme dělat sami, protože ty základní už bývají ve standardní knihovně. Například v c++ jsou vector, queue, deque, priority_queue, set, map, které z vyššího seznamu pokrývají Pole, Haldy a Vyvažované vyhledávací stromy. Přesto je dobré si tyto struktury naimplementovat, protože knihovní struktury nemůžeme moc upravovat, a neupravené nám občas nestačí.
Pomocí grafů se dá dobře namodelovat celá řada běžných problémů. Jeden typický je hlednání nejkratší cesty. Grafy mají také mnoho vlastností, které umíme rychle detekovat a využít při tvorbě řešení.
Grafem lze jednoduše namodelovat mapa měst a cesty mezi nimi. Když cestám přidáme vzdálenost (tzv. váha hrany), dostáváme vážený graf, na kterém umíme rychle hledat nejkratší cestu.
Jednoduchým průchodem grafu lze zjistit celou řadu informací. Například artikulace a mosty jsou „slabá místa“ po jejichž odebrání se část grafu rozpadne.
Řešení problému hledání minimální kostry je více a každé z nich používá nějakou datovou strukturu ze sekce výše.
Vyhledávání v textu je nejtypičtější úloha pro toto téma. Lze řešit velice rychle a algoritmus není ani tak komplikovaný. Toto téma ale obsahuje i špeky jako hledání palindromů, hledání mnoha různých řetězců uvnitř textu a hledání nejdelšího společného podřetězce.
Z pohledu návrhu algoritmu není geometrie tak obtížné téma, lze jednoduše říct, že najdeme průnik úseček, kružnic, nebo třeba tečnu kružnice k bodu. Z pohledu implementace je ale geometrie nevděčné téma, protože všechny zmíněné operace není jednoduché naimplementovat a mají často mnoho speciálních případů.
Například průnik dvou kružnic zní jednoduše, ale může nastat 5 případů toho jak jsou kružnice vzájemně pozicované výsledek průniku mohou být 2 body, nebo také žádný bod. Dále, pokud póčítáme na reálných číslech, tak je počítač nedovede přesně reprezentovat, a vzniká chyba, která se výpočtem může zvětšit nad únosnou mez. Je tak potřeba vždy počítat s drobnou mírou nepřesnosti. I pro jednoduše znějící úlohy je implementace komplikovaná a proto je téma geometrie z pohledu implementace považované spíše za obtížnější.