# Algoritmizace: přednášky - https://ksvi.mff.cuni.cz/~topfer/ - prezentaci budeme mít k dispozici online, často bude rozšířená oproti přednášce, budou tam ukázkové programy - [kurz v Moodlu](https://dl1.cuni.cz/course/view.php?id=8186#section-3) - zkouška - společné pořadavky a zkušební termíny pro obě paralelky - přihlašování přes SIS - je nutné mít zápočet - povinná písemná část, nepovinná ústní - materiály - Pavel Töpfer: Algoritmy a programovací techniky - programátorské kuchařky KSP - https://pruvodce.ucw.cz - https://www.algovision.org ## Algoritmus - Konečná posloupnost elementárních příkazů, jejichž provádění umožňuje pro každá přípustná vstupní data mechanickým způsobem získat po konečném počtu kroků příslušná výstupní data. - vlastnosti algoritmu – konečnost, hromadnost, resultativnost, jednoznačnost, determinismus (nebude na zkoušce :) - determinismus – po provedení každého kroku je jednoznačně určeno, který krok se bude provádět dále - formální modely algoritmu – rekurzivní funkce, Turingův stroj, lambda kalkul, RAM počítač - popis a zápis algoritmu – slovní popis v přirozeném jazyce, pseudokód, program (zjednodušená konstrukce programovacího jazyka) - největší společný dělitel - správnost Eukleidova algoritmu 1. konečnost = výpočet pro jakákoliv vstupní data skončí - na začátku výpočtu i stále v jeho průběhu je x > 0, y > 0 - v každém kroku výpočtu se hodnota x+y sníží alespoň o 1 -> nejpozději po x+y krocích výpočet skončí, je tedy konečný 2. parciální správnost - problém stabilních manželství - složitost – časová a prostorová ### Efektivita algoritmu - efektivita algoritmu – funkce velikosti vstupních dat - přesné vyjádření časové složitosti je obtížné a zbytečné, podstatná je řádová rychlost růstu této funkce pro rostoucí N - zanedbáním pomaleji rostoucích členů a konstant získáme **asymptotickou časovou složitost**, např. $O(N^2)$ - symbol "velké O" - $f\in O(g)$ - funkce f se dá shora odhadnout funkcí g (až na multiplikativní konstantu a pro dostatečně velká n) - $f,g: \mathbb{N}→\mathbb{R}^+$ - $f\in O(g) \iff (\exists c > 0)(\exists n_0)(\forall n>n_0): 0\leq f(n) \leq c \cdot g(n)$ - jde o odhad shora - opačný odhad zdola $f \in \Omega(g)$ - přesný odhad $f \in \Theta(g)$ - $f \in \Theta(g) \iff f \in O(g)\land f \in \Omega(g)$ - asymptotická časová složitost - typické třídy asymptotické časové složitosti algoritmů $\Theta(1), \Theta(\log{N}), \Theta(n), \Theta(N \cdot \log{N}), \Theta(N^2), \Theta(N^3), \dots, \Theta(2^N), \Theta(N!)$ - problém batohu - někdy se používá f = O(g), což není formálně zcela správné, protože O(g) je třída funkcí - složitost algoritmu v různých případech – v nejlepším (prakticky se nepoužívá), nejhorším (používá se nejčastěji) a průměrném (je obtížné odvodit tuto složitost) - algoritmus problému stabilních manželství – v nejhorším případě $\Theta(n)$, v nejlepším případě $\Theta(n^2)$ - složitost problému – složitost nejlepšího algoritmu (z hlediska časové složitosti), kterým lze řešit daný problém; odvození bývá často obtížné, pro řadu problémů neznáme - složitost problému vnitřního třídění – $O(n \cdot \log{n})$ - rozklad čísla na cifry - test prvočíselnosti - zkouším všechny dělitele od 2 do $N-1 → O(N)$ - zkouším všechny dělitele od 2 do $N/2 → O(N)$ - zkouším všechny dělitele od 2 do $\sqrt{N} → O(\sqrt{N}) = O(N^\frac{1}{2})$ – asymptoticky lepší - nepoužíváme odmocninu, ale druhou mocninu (násobení) - přestanu při nalezení prvního dělitele – také $O(\sqrt{N})$ - stačí zkusit číslo 2 a pak jen liché dělitele lichých čísel - hledání všech prvočísel od 2 do N - pomalý způsob $O(N^\frac{3}{2})$ – pro každé číslo zkouším, jestli je prvočíslo (viz výše) - Eratosthenovo síto – vyškrtáváme násobky prvočísel - složitost $O(N\cdot \log{\log{N}})$ ## Dlouá čísla - Python to umí sám - číslo uložíme po cifrách – seznam cifer (uložíme jako pole čísel) - operace po cifrách jako na základní škole - lze ukládat cifry po trojicích apod. - desetinné číslo – evidujeme polohu desetinné čárky ## Vyhodnocení polynomu v bodě - úloha: vyhodnocení polynomu v bodě x (dosazení konkrétního x do polynomu) - přímý výpočet podle uvedeného předpisu – kvadratická složitost (cca n^2 násobení, n sčítání) - Hornerovo schéma – n násobení, n sčítání → lineární složitost - příklad použití algoritmu – vstup čísla po znacích, konverze číselného stringu na integer - operace s polynomy - nejdříve polynom uložíme do pole – index v poli odpovídá mocnině (první prvek v poli je absolutní člen) - číselné soustavy - rychlé umocňování - vyhledávání v seznamu - sekvenční průchod - binární vyhledávání ## Řadicí algoritmy - třídění sléváním (merge sort) - časová složitost $\Theta(n \log_2 n)$ - počet porovnání v každé hladině – n - počet hladin – log n - prostorová složitost – potřebuju další pole délky $n$ - k dokázání přesného odhadu složitosti lze dokázat, že to jde udělat s danou složitostí a že to nejde lépe - problém třídění n dat – musíme udělat $\log_2 n!$ porovnání - https://www.itnetwork.cz/algoritmy/razeni/dolni-odhad-casove-slozitosti-problemu-trideni - $\log n! = n \log n$ - Stirlingova formule - $(\frac{n}{2})^\frac{n}{2} < n! < n^n$ (logaritmujeme) - třídění počítáním (counting sort) - O(n + R) - R … rozsah hodnot - přihrádkové třídění (bucket sort) - pythonovský i klasický způsob - u klasického způsobu mám v poli uložené indexy, kam umístit prvek s danou hodnotou - je stabilní – zachovává pořadí prvků se stejnou hodnotou klíče - víceprůchodové přihrádkové třídění (radix sort) - u velkého R (rozsahu hodnot) - rozdělíme klíč na části – nejprve třídíme podle dolní (méně významné) části klíče, poté podle horní (významnější) části - díky stabilitě třídění se zachová uspořádání z předchozích fází třídění - vnější třídění = třídění dat, která se nevejdou do paměti (tedy je máme uložená v souborech) - lze použít merge sort - u merge sortu má smysl slučovat tři nebo čtyři úseky - použitím vnitřního třídění k prvotnímu roztřídění pole snížím počet vstupně výstupních operací - tim sort – kombinuje insertion sort a merge sort (merge sort se používá až na větší úseky) ## Ukládání dat - int – ve dvojkové soustavě - 32bit nebo 64bit ### Datové struktury - seznam vs. pole - rychlejší je práce s polem, seznamy mají více možností (i když často zbytečných) - pole v Pythonu – knihovny array, numpy - operace na seznamu - úpravy středu seznamu – lineární složitost - úpravy konce – lineární (pokud chybí paměť), ale průměrně konstantní časová složitost - pokud na konci seznamu chybí paměť, tak není možné provést append – Python tedy seznam přesune jinam (realokuje), přidá mu víc místa (aby se tam vešlo ještě x dalších prvků) - realokace s přidělením dvojnásobku paměti - takhle to Python nedělá, ale je to názorné - pro 1000 appendů 9 realokací - amortizovaná složitost konstantní - spojové seznamy – poměrně pracné pro programátora, někdy fungují rychleji, v Pythonu se implementuje ručně (v programu mám uložený odkaz na první prvek seznamu, ten odkazuje na další prvek atd., na konci je uzemnění – v Pythonu None) - abstraktní datové typy - zásobník (stack) - řada dat, na jedné straně dno, na druhé vrchol - data se přidávají na vrchol a odebírají se také jediné z vrcholu - v Pythonu lze implementovat na seznamu nebo na spojovém seznamu - fronta (queue) - z jedné strany se prvky přidávají, z druhé odebírají - jak řešit odebírání prvků z paměti - při odebrání posouvám prvky – lineární složitost - při odebrání většího množství prvků posouvám prkvy - posouvám až ve chvíli, kdy nemám volné místo - kruhová fronta – při přetečení se přidává na začátek paměti (v programu ukládám začátek a konec fronty, ty modulím kapacitou) - deque – knihovní implementace fronty (double-ended queue), umožňuje přidávat i odebírat zprava i zleva - při implementaci fronty pomocí spojového seznamu je na konci seznamu příchod, na začátku odchod, ukládám dvojici odkazů (na první a poslední prvek) - halda (heap) - nepamatuje si pořadí příchodu prvků - prvky musí být porovnatelné (definováno vzájemné uspořádání) - odebírá se nejmenší prvek - typické operace – přidat prvek, určit hodnotu minimálního prvku, odebrat minimální prvek - požadujeme časovou složitost všech operací $O(\log N)$ - haldu si představujeme jako binární strom, který ovšem typicky implementujeme v poli (pokud nultý prvek pole necháme prázdný, tak bude počítání indexů trochu jednodušší) - pro každý uzel musí platit, že jeho hodnota je menší (nebo rovna) než hodnota obou synů - výška binárního stromu - pro nevyvážený (degenerovaný) strom – až $n$ - pro vyvážený strom – $\log_2 n$ - průměrně $2\log_{2} n$ - výška haldy = horní celá část z $\log_2 N$ - při přidávání prvku přidáváme na konec a bubláme nahoru - při odebírání prvku odebereme nejmenší (ze začátku), poslední přesuneme místo něj a bubláme dolů (prohazujeme s menším ze synů) - haldování v lineárním čase - vytvářím malé haldy na konci seznamu, postupuju nahoru a probublávám prvky směrem dolů - idea spočívá v tom, že u původního postupu má před sebou hodně prvků dlouhou bublací cestu (halduje se shora), zatímco u tohoto rychlého postupu má před sebou málo prvků dlouhou bublací cestu (halduje se zespoda) - prioritní fronta - prvky se předbíhají podle priority - typická je implementace pomocí haldy - pokud záleží na pořadí prvků téže priority, řeší se pomocí front uvnitř haldy - slovník - dvojice klíč – hodnota - operace: vyhledej, vlož, vymaž - někdy se označuje jako asociativní pole nebo mapa - typicky implementace pomocí hešování - časová složitost přístupu k prvku je v průměru konstantní, ale v nejhorším případě lineární vzhledem k počtu prvků ## Rekurze - objekt je definován pomocí sebe sama - rekurzivní algoritmus - rekurzivní volání funkce - implementace rekurzivního algoritmu bez použití rekurzivní funkce může být výhodnější - ukončení rekurze - v Pythonu maximální povolená hloubka rekurze 1012 - v jiných jazycích může nastat chyba stack overflow (přetečení zásobníku volání funkcí) - Fibonacciho posloupnost - řešení pomocí čisté rekurze je neefektivní (exponenciální složitost) - chytrá rekurze - kešování hodnot, memoizace – mezivýsledky ukládám do pole - dynamické programování – jdu zespodu - doplnění znamének - rekurzivně generujeme binární strom - ořezávání stromu se může vyplatit – u téhle konkrétní úlohy nelze (jednoduše) určit algoritmus ořezávání - rozklad čísla na součet kladných celých sčítanců - vybereme z nich ty nerostoucí, abychom tam neměli několik permutací jednoho rozkladu - není to binární strom, ale je prořezaný, jak se dá ## Binární stromy - hodí se nám „spojákové“ ukládání (tedy pomocí pointerů v objektu) - „haldové“ ukládání v poli je neefektivní, protože nám můžou vznikat prázdná místa - průchod do hloubky - v každém vrcholu provedeme zvolenou akci - varianty průchodu - preorder – nejprve zpracuje vrchol, pak jde postupně do obou jeho podstromů - inorder – nejprve jde do levého podstromu, pak zpracuje vrchol, nakonec jde do pravého podstromu - postorder – nejprve jde postupně do obou podstromů vrcholu, pak zpracuje vrchol samotný - lze procházet bez rekurze pomocí zásobníku - průchod do šířky - stačí použít algoritmus se zásobníkem a místo zásobníku v něm použít frontu - složitost (viz prezentace) - binární strom bude u zkoušky - binární vyhledávací strom - datová struktura pro ukládání a vyhledávání dat podle klíče - pro každý vrchol platí - všechny záznamy uložené v levém podstromu mají menší klíč - všechny záznamy uložené v pravém podstromu mají větší klíč - musí platit pro všechny záznamy v podstromu – nestačí bezprostředně mezi uzly - časová složitost algoritmu vyhledávání je v nejhorším případě určena výškou stromu (u degenerovaného stromu až N) - v průměrném případě výška O(log N) - vyvažování stromu – je algoritmicky náročné - přidávání hodnoty – algoritmem vyhledávání dojdu k odkazu None a tam hodnotu přidám - odebrání hodnoty - pokud nemá syny – triviální - pokud má jednoho syna – triviální - pokud má dva syny – najdu maximum v levém podstromu nebo minimum v pravém podstromu - tohle maximum/minimum má nejvýše jednoho syna, takže ho umíme smazat - existuje binární vyhledávací strom se zarážkou - používali jsme seznam se zarážkou – hledané x jsme dali na konec, takže jsme nemuseli řešit vytečení ze seznamu - u stromu se zarážkou nasměrujeme všechny listy (které by normálně směřovaly na None) na zarážku - vyvážené stromy - dokonale vyvážený binární strom - pro každý uzel platí, že počet uzlů v jeho levém a pravém podstromu se liší nejvýše o 1 - nejlepší možné vyvážený, výška stromu s N uzly je $\lceil\log{N}\rceil$ - lze snadno postavit z předem známé množiny hodnot - je obtížné ho udržovat - proto se používají slabší definice vyváženosti - výškově vyvážený strom (AVL) - na začátku sestavím dokonale vyvážený, poté ho udržuju ve stavu výškové vyváženosti - stavění stromu – viz prezentace - balance - rotace pro zajímavost v prezentaci, ale nebude zkoušeno ## Prohledávání stavového prostoru - hledání pokladu v bludišti - zkouším postupně všechny cesty - bludiště obecně není strom (procházím typicky nějaký spojitý graf) - může vzniknout situace, že dojdu na křižovatku, na které už jsem byl - název algoritmu - prohledávání do hloubky, prohledávání s návratem - DFS (depth-first search), backtracking - proskákání šachovnice koněm – příliš časově náročné - urychlení prohledávání do hloubky - ořezávání – v průběhu vyhodnocuji, jestli má smysl postupovat ve stromu dál - osm dam na šachovnici (aby se dvě navzájem neohrožovaly) - bez ořezávání – zkoušet všechny výběry 8 polí z 64 - základní ořezávání – na každém řádku právě jedna dáma, po umístění všech osmi dam otestovat kolize - lepší ořezávání – hned při umišťování každé dámy testovat kolize s dámami umístěnými na předchozích řádcích - magické čtverce - heuristika – odhad, kde je asi větší šance na nalezení řešení (u úloh, kde hledám jedno řešení) → podle toho určím pořadí procházení variant možných pokračování - u koně volím ty umístění, z nichž mám nejmenší počet možných dalších kroků - prohledávání stavového prostoru do šířky – breadth-first search (BFS), algoritmus „vlny“ - souběžně zkoušíme všechny možné varianty pokračování výpočtu až do nalezení řešení úlohy – v každé vrstvě zkoušíme všechny možnosti zleva doprava - může být paměťově velmi náročné, až nepoužitelné - vždy najde nejkratší možné řešení co do počtu kroků - k nalezení samotné cesty je potřeba „zpětný chod“ - zkouška - ve zkouškovém období - informace na moodlu, ukázka úloh z minulého ročníku - velká písemka každý týden ve zkouškovém v pondělí dopoledne, termíny společné pro obě paralelky v N1 - potřebujeme zápočet - termíny budou vypsány kolem Vánoc - povinná písemná a nepovinná ústní část - v písemné části asi 4 příklady - úlohy vyřešíme, součástí některých úloh je i napsat funkci v Pythonu, ale není naší povinností ji odladit, nebudou se kontrolovat detaily syntaxe, jde hlavně o princip - zkoušku budeme řešit v Moodlu, budeme moct používat vlastní notebook s Moodlem (takže můžeme používat prezentace z přednášek) - je možná i papírová varianta - kdo dostane 2 nebo 3 a bude si chtít zlepšit známku, bude moct přijít na ústní část zkoušky – výsledná známka se bude skládat ze dvou známek (může být lepší nebo i horší) - minimax - na tahu bílého se hledá maximum, na tahu černého minimum - u malých her se dá postavit celý strom - řeší se průchodem do hloubky (klasický backtracking), v listech se výsledek ohodnotí (výhra = 1, prohra = 0, remíza = –1) - někdy se používá negamax – prohazuje se znaménko, protože $\text{min}(a,b) = -\text{max}(-a,-b)$ - u velkých her rozvíjím hru do určité hloubky, pak to zaříznu (čím větší hloubka, tím chytřejší tahy) - v té hloubce se na pozice zavolá statická ohodnocovací funkce, která každou z nich ohodnotí - často se ohodnocení vylepšuje tak, že pokud je koncová pozice „živá“ (nastávají výrazné změny na herním poli), tak se strom počítá ještě o úroveň níž - ořezávání stromu - ztrátové - provedu statické ohodnocení po několika málo vrstvách - část nejhorších pozic odmítnu, zbytek rozvíjím dál - bezztrátové – alfa-beta-prořezávání - využívá principu minimaxu – jeden hráč hledá minimum, druhý maximum, tedy v některých situacích není potřeba dopočítávat další varianty hry - dá se přidat heuristika – procházím postupně do uzlů, které mají lepší (nebo naopak horší) výsledek statického ohodnocení - rozděl a panuj (divide et impera) - metoda rekurzivního návrhu algoritmu (programu) - problém se rozdělí na dva podproblémy, které se obvykle řeší lépe, z jejich řešení se dá sestavit řešení původního problému - je problematické použít tuto metodu u úloh, kdy jednotlivé podúlohy jsou na sobě závislé (mají společné části) – viz Fibonacci - vyhodnocení aritmetického výrazu - hanojské věže - abych přenesl celou věž z A na B, musím nejdřív dostat horní část na C, potom přesunout spodní kotouč z A na B a pak na něj přenést horní část - mergesort - rozdělujeme na půl - sléváme - quicksort - vyberu číslo (pivot) – typicky náhodně nebo uprostřed pole - prvky rozdělím na menší, rovné a větší než pivot - dá se třídit na místě – jdu zleva a zprava, hledám větší/menší, až najdu, tak prohodím a jedu dál - v průměru počítá nejrychleji ze všech algoritmů – O(N log N) - v nejhorším případě kvadratický (když volím špatné pivoty) - pokud chci garantovanou složitost, tak quicksort není dobrá volba - volba pivota - jeden náhodně vybraný prvek - vzorkování – medián ze tří náhodně zvolených prvků - náhodný výběr + ověření, zda je alespoň 1/4 prvků menších a 1/4 prvků větších - nalezení mediánu tříděného úseku (existuje algoritmus, který hledá v lineárním čase) – zajistí složitost O(N log N), ale v průměru bude pomalejší, protože vzroste multiplikativní konstanta - nalezení K-tého nejmenšího prvku z N čísel - speciální případ – medián - způsoby - setřídit čísla v poli – spousta zbytečné práce - modifikace heapsortu – K-krát odeberu minimum - akademická hříčka: postavit v poli haldu z prvních N–K+2 prvků - modifikace quicksortu – quickselect - lineární algoritmus - quickselect - po rozdělení seznamu podle pivota pracujeme dál jen s tou částí, ve které je hledaný prvek (poznáme ji podle délky – známe délky jednotlivých částí) - v průměru má lineární složitost, v nejhorším případě kvadratickou - lineární algoritmus - seznam rozdělím po pěti prvcích - z každé pětice vezmu medián (práce n) - z nalezených mediánů najdu medián (práce n/5) - ten zvolím jako pivot - v nejhorším případě bude v menší části 3/10 n prvků - tento algoritmus nemusíme umět - vyhodnocení aritmetického výrazu reprezentovaného binárním stromem - průchod preorder → prefix - průchod inorder → infix (bez závorek) - průchod postorder → postfix - vyhodnocení postfixu – pomocí zásobníku (vytáhnu dvě čísla ze zásobníku, provedu operaci, výsledek vrátím do zásobníku) - vyhodnocení výrazu v prefixové notaci - průchod odzadu a zpracování jako u postfixu - průchod zepředu a ukládání operací do zásobníku – při přidávání čísla do zásobníku kontrola, zda je na vrcholu zásobníku číslo, pokud ano, tak ho vyzvednu a rovnou taky operaci pod ním, tu provedu - rekurze - převod infix → postfix – pomocí zásobníku během jednoho průchodu ## Grafy - reprezentace grafu v programu - matice sousednosti - neorientovaný graf – symetrická matice - ohodnocený graf – matice délek (ohodnocení) hran - vhodné použití – malé grafy s velkým počtem hran - není vhodná u grafů s velkým počtem vrcholů a relativně málo hranami (např. silniční síť) - seznamy následníků - u každého vrcholu je uložen seznam čísel vrcholů, do nichž odsud vede hrana - primárně určeno pro orientované grafy – u neorientovaných ukládám obě orientované hrany - u ohodnocených grafů ukládám i hodnocení hrany - realizace - pole N seznamů - matice N×N–1 (z každého vrcholu může vést až $N - 1$ hran) - matice N×R, když víme, že z každého vrcholu vede maximálně R hran - nemáme omezení R, ale víme, že celkově graf obsahuje nejvýše M hran - princip „vzájemné solidarity“ vrcholů – čísla následníků všech vrcholů se ukládají do jednoho společného pole E délky M - v samostatném poli jsou uloženy indexy, na kterých začínají seznamy jednotlivých vrcholů - špatně se modifikuje, ale ve většině grafových úloh není potřeba graf modifikovat - seznam hran - jednorozměrné pole délky M nebo spojový seznam - každý záznam odpovídá jedné hraně grafu - matice incidence - matice velikosti M×N - 1, pokud vrchol leží na hraně - dynamická reprezentace – pomocí objektů - základní grafové problémy - při procházení musím nastavovat příznak „navštíven“, abych se nezacyklil - je potřeba rozlišovat implementaci DFS rekurzí/zásobníkem – liší se v pořadí zpracování vrcholů - časová složitost – záleží na reprezentaci grafu ke zkoušce: zdůvodnit, proč má algoritmus takovou časovou složitost - obecný strom - známe maximální stupeň větvení M – lze reprezentovat podobně jako binární strom (místo dvou mám M odkazů na syny) - obecné řešení – seznam odkazů na syny - kanonická reprezentace – reprezentace obecného stromu binárním stromem - levý ukazatel ukazuje na nejstaršího syna - pravý ukazatel ukazuje na mladšího bratra - akorát neobsahuje klasický průchod do hloubky/šířky – pouze jakýsi průchod všech vrcholů - příklad použití obecného stromu – trie - hešování – hešovací funkce mi z klíče vyrobí index - jak řešit kolize? - kolidující prvky můžu ukládat do seznamu na daném indexu - pomocí sekundární hešovací funkce můžu vygenerovat náhradní index - metody návrhu algoritmů - předvýpočet - místo přímého výpočtu provedeme nejdříve předvýpočet a až pak výsledný výpočet - typické způsoby předvýpočtu – setřídit data, překódovat data, přepočítat data - příklad – prefixové součty - hladové algoritmy - v každém kroku vybírá lokální maximum (minimum) s cílem dojít ke globálnímu maximu (minimu) - často nefunguje, musíme ověřit a dokázat správnost - příklad – platidla (platím co největší mincí) - pro sadu 1, 2, 5 funguje (ale nutné dokázat) - pro sadu 1, 4, 5 nefunguje - pro sadu 3, 8 a částku 9 nenajde řešení, ačkoliv existuje - příklad – minimální kostra v ohodnoceném grafu - příklad – přidělení pracovních úkolů - dynamické programování