Algoritmizace: přednášky: kartičky | algoritmizace-programovani1

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

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

Algoritmus

správnost Eukleidova algoritmu

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ý
parciální správnost

Algoritmus

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)$ $O (N^{2})$
- symbol "velké O"
- $f\in O(g)$ $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 Θ (g)$
- $f \in \Theta(g) \iff f \in O(g)\land f \in \Omega(g)$

Algoritmus

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í

Algoritmus

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)$

Algoritmus

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})$

Algoritmus

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})$ $N \to O (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

Algoritmus

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}})$

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

Vyhodnocení polynomu v bodě

operace s polynomy

nejdříve polynom uložíme do pole – index v poli odpovídá mocnině (první prvek v poli je absolutní člen)

Vyhodnocení polynomu v bodě

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)$ $Θ (n lo g_{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$

Řadicí algoritmy

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$ $lo g n! = n lo g n$
- Stirlingova formule
- $(\frac{n}{2})^\frac{n}{2} < n! < n^n$ (logaritmujeme)

Řadicí algoritmy

třídění počítáním (counting sort)

O(n + R)
- R … rozsah hodnot

Řadicí algoritmy

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

Řadicí algoritmy

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í

Řadicí algoritmy

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

Ukládání dat

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í

Ukládání dat

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

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í)

Rekurze

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

Rekurze

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í

Rekurze

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

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

Binární stromy

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í stromy

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