# Programování II pro matematiky ## Teoretické cvičení 04 **24. 3. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Poznámky k domácímu úkolu - Menší domácí úkol - Příklady - Řešení příkladů --- ## Opakování - Třídění - Pomalejší metody - složitost $\mathcal{O}(n^2)$ - [Selection sort](https://www.algoritmy.net/article/4/Selection-sort) - [Insert sort](https://www.algoritmy.net/article/8/Insertion-sort) - [Bubble sort](https://www.algoritmy.net/article/3/Bubble-sort) - Speciální data - CountingSort - BucketSort - RadixSort - Rychlejší metody - složitost $\mathcal{O}(n \cdot \log(n))$ - MergeSort - [QuickSort](https://www.algoritmy.net/article/10/Quicksort) - HeapSort ---  ---  [Animace](https://www.algoritmy.net/article/10/Quicksort) --- ### HeapSort Bylo na dnešní přednášce...  Zdroj obrázku: https://en.wikipedia.org/wiki/Heapsort --- ### Kontrolní otázka Nechť jsem dostal od nepřítele metodu `sort(List[int]) -> List[int]`. Jakou má moje metoda časovou složitost? -- *Záleží, jak jí nepřítel naprogramoval !!!* Jakou má časovou složitost `numpy.sort` ? -- *Podle dokumentace:* | kind | speed | worst case | work space | stable | | ------------------- | ----- | ----------- | ---------- | ------ | | quicksort (default) | 1 | O(n^2) | 0 | no | | heapsort | 3 | O(n*log(n)) | 0 | no | | mergesort | 2 | O(n*log(n)) | ~n/2 | yes | | timsort | 2 | O(n*log(n)) | ~n/2 | yes | --- ## Poznámky k domácímu úkolu - Novou proměnnou je vhodné nějak zavést (např. $t$ je počet řádků domácího úkolu, $t \in \N$) - Není dobré používat proměnné ze zadání k označování jiných věcí ve vlastním algoritmu - Před odevzdáním je dobré zkontrolovat, jestli algoritmus funguje na ukázkových datech a jestli byly zodpovězeny všechny otázky ze zadání - To, že příklad vyjde $4$, není většino tak důležité. Důležité je popsat, proč jsou to jsou zrovna ty $4$. - *PS: V neformátovaném textu se $x_0$ píše jako `x_0` a $y^2$ jako `y^2`. Obecně se pro proměnné nepoužívají zvláštní znaky `@`, `&` atd...* --- ### Popis algoritmu - ~~Rozdělím kuličky na co nejpodobnější hromádky~~ - ~~Rozdělím kuličky, tak aby se hromádky lišili maximálně o jedna~~ (v této úloze je to jednoznačné, ale tohle není dobrý popis algoritmu) - Použiji hromádky $ \lfloor n/3 \rfloor$, $\lfloor n/3 \rfloor$ a $n - 2 \cdot \lfloor n/3 \rfloor$ - nevede na optimální řešení - Nefunguje ani na testovacích datech... - Příklad hezkého popsání: - Nechť $n = 3k + z$, kde $k \in \N, z \in {0, 1, 2}$, podle zbytku $z$ rozdělím kuličky následovně - pro $z=0$ mám hromádky $k, k, k$ - pro $z=1$ mám hromádky $k, k, k + 1$, případně $ \lfloor n/3 \rfloor, \lfloor n/3 \rfloor, \lceil n/3 \rceil $ - pro $z=1$ mám hromádky $k + 1, k + 1, k$, případně $\lceil n/3 \rceil, \lceil n/3 \rceil, \lfloor n/3 \rfloor$ - Zvážím dvě hromádky se stejným počtem kuliček. Podle budou hromádky stejně těžké, tak je kulička ve třetí (nevážené) hromádce. Pokud bude jedna hromádka těžší, tak je kulička v této hromádce. Takto opakuji dokud mi nezůstane jen jedna kulička. --- ### Složitost problému První úlohou jsem se snažil mířit na složitost problému hledání nejmenší kuličky (za podmínek ze zadání). Takovou složitost nejde odvodit ze složitosti nějakého konkrétního algoritmu ani třeba všech běžně známých algoritmů, charakterizuje problém obecně (jaký nejlepší algoritmus řešící problém může v principu existovat). Všechny algoritmy (které generují správný výsledek) budou po každém vážení zmenšovat problém. Ať vymyslíš libovolný algoritmus, tak vždycky tam bude při vážení skupina kuliček alespoň $n/3$ velká (a v nejhorším případě bude kulička právě v této skupině). Pomocí toho spočítáš minimální počet vážení v nejhorším případě přes všechny strategie. Ve všech funkčních strategiích existuje případ, kdy algoritmus potřebuje alespoň $ \lceil \log_3 \rceil$ vážení. Nemůže existovat strategie s menším počtem vážení v nejhorším případě. A proč to tak je je potřeba zdůvodnit. --- ## Poznámky k domácímu úkolu ### Počet kroků algoritmu - Optimální strategie potřebuje $ \lceil \log_3 \rceil$ vážení v nejhorším případě - Jak víte, že jedna kulička ze zaokrouhlování nezpůsobí, že těch vážení bude nakonec více? - Hezká cesta je vyjádřit si matematicky počet kuliček v každém kroku algoritmu a pak se hledá kolikátý člen posloupnosti bude roven $1$. - Šlo to ale i indukcí, rozborem příkladů atd... --- ## Domácí úkol Od kamaráda ze cvičení dostanete (poštou) tabulku čokolády. Tabulka čokolády má $K \times L$ okýnek velikosti $1 \times 1$. Kolikrát budeme muset zlomit čokoládu, abyste měli okénka pouze velikosti $1 \times 1$. Můžeme lámat pouze souvislé úseky čokolády (nemůžeme tedy rozlomené kousky čokolády dávat na sebe nebo vedle sebe). Určete kolikrát budeme muset čokoládu zlomit a popište, proč to nejde udělat na méně zlomení (zdůvodnění klidně může být jen na pár vět). --- ## Příklady Najděte algoritmus a určete jeho časovou a prostorovou složitost v nejhorším případě. 1. Máme danou posloupnost $N$ čísel. Chceme spočítat součet prvků v souvislém uzavřeném intervalu $[x_0, x_1]$. 2. Máme dány dva velmi rozsáhlé soubory čísel (nevejdou se do vnitřní paměti počítače). Vypište čísla, která se nacházejí v obou těchto souborech. 3. Máme dán velmi rozsáhlý soubor s textem (nevejde se do vnitřní paměti počítače). Vypište sto nejčastějších slov, která se v textu nacházejí. --- ## Řešení Máme danou posloupnost $N$ čísel. Chceme spočítat součet prvků v souvislém uzavřeném intervalu $[k, l]$. -- Vstup: ``` 1 2 4 5 4 3 3 5 0 1 ``` -- Algoritmus (vstup neprázdné `pole`, indexy `k` a `l`): ``` suma = 0 for i in range(k, l+1): suma += pole[i] return suma ``` -- - Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(1)$ --- ## Řešení Máme dány dva velmi rozsáhlé soubory čísel (nevejdou se do vnitřní paměti počítače). Vypište čísla, která se nacházejí v obou těchto souborech. -- - Každé číslo z jednoho souboru hledat ve druhém souboru - Časová složitost $\mathcal{O}(n^2)$ - Prostorová složitost $\mathcal{O}(1)$ -- - Seřadím čísla v souborech podle velikosti vnějším tříděním. - Postupně seřadím úseky, co se vejdou do paměti. - Seřazené úseky spojím do jednoho souboru. - Procházím současně oba soubory, protože jsou seřazené, tak hned vidím, jestli v druhém souboru je odpovídající číslo. -- - Časová složitost $\mathcal{O}(n \log(n))$ - Prostorová složitost $\mathcal{O}(1)$ - program zabere paměť pro načtení úseku, velikost úseku ale nesouvisí s velikostí vstupu --- Proč nám tady tolik vadí složitost $n^2$? -- - soubory se nevejdou do paměti → $n$ řádově $10^9$ - časová složitost $\mathcal{O}(n^2)$ vstupně/výstupních operací → $10^{18}$ operací - rychlost procesoru $10^9$ op/s ve vnitřní paměti, ale jen $10^7$ op/s vstupně/výstupních operací - tedy doba výpočtu $10^{11}$ sekund = **3000 let** - časová složitost $\mathcal{O}(n \log(n))$ vstupně/výstupních operací → $6 \cdot 10^{10}$ operací - tedy doba výpočtu 6000 sekund = **2 hodiny** (Převzato ze [stránek doc. Töpfera](https://ksvi.mff.cuni.cz/~topfer/)) --- ## Řešení Máme dán velmi rozsáhlý soubor s textem (nevejde se do vnitřní paměti počítače). Vypište sto nejčastějších slov, která se v textu nacházejí. -- Obdobné řešení jako v předchozím případě. Jen je potřeba promyslet, že jako čísla můžu stejně řadit slova lexikograficky (podle abecedy). Pro určení složitosti budu předpokládat, že jsou slova omezená délkou - u některých jazyků je to komplikovanější, ale pro češtinu mám slovo: `nejzdevětadevadesáteronásobitelnějšího`, které má 38 písmen. --- - Seřadíme slova lexikograficky v obou souborech pomocí vnějšího třídění - Slejeme oba soubory dohromady a u každého slova si spočítáme počet výskytů - Např. místo více výskytů pro ``` martin martin tomáš ``` budeme mít ``` martin 2 tomáš 1 ``` - Seřadíme slova podle výskytů pomocí vnějšího třídění - Vypíšeme nejčastější slova -- - Časová složitost $\mathcal{O}(n \log(n))$ - Prostorová složitost $\mathcal{O}(1)$ - program zabere paměť pro načtení úseku, velikost úseku ale nesouvisí s velikostí vstupu