# Programování II pro matematiky ## Teoretické cvičení 05 **31. 3. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Poznámky k domácímu úkolu - Příklady - Řešení příkladů - Domácí úkol --- ## Opakování - Zásobník - Fronta  *Zdroj obrázku: https://gohighbrow.com/stacks-and-queues/* --- ## Opakování - Halda - *Tvar haldy:* Všechny hladiny kromě poslední jsou plně obsazené. Poslední hladina je zaplněna zleva. - *Haldové uspořádání:* Je-li $v$ vrchol a $s$ jeho syn, platí $k(v)≤k(s)$.  --- ## Opakování - Reprezentace haldy v listu  - Nechť nás zajímají potomci prvku na indexu $i$. Potoky nalezneme na indexech $2i+1$ a $2i+2$. *Zdroj obrázku: https://cs.wikipedia.org/wiki/Halda_(datov%C3%A1_struktura)* -- ### Poznámka - [Každá datová struktura má své výhody](https://medium.com/omarelgabrys-blog/data-structures-a-quick-comparison-6689d725b3b0) --- ## Poznámky k domácímu úkolu - Optimální řešení vyžadovalo vybudovat 2D prefixové součty. - V zadání byly proměnné $K$ a $L$, takže vyjádřit složitost by měla tyto proměnné používat. Nedává smysl napsat, že $K \cdot L = N^2 $ a považovat řešení za $\mathcal{O}(N ^ 2)$. - Následující řádek má složitost $\mathcal{O}(R)$ v nejhorším případě ```python for k in range(x1,x2+1): vysledek += prefix[k,y2+1]-prefix[k,y1] ``` --- ## Příklady Najděte algoritmus a určete jeho časovou a prostorovou složitost v nejhorším případě. 1. Navrhněte reprezentaci fronty v poli, která bude pracovat v konstantním čase. Můžete předpokládat, že předem znáte horní odhad počtu prvků ve frontě. 2. Navrhněte algoritmus, který zkontroluje správné uzávorkování aritmetického výrazu s více druhy závorek. ``` 1 * [ 5 + ( 3 ] * 2 } # Špatně ``` 3. Program dostává dlouhou sérii měření (délky $N$), pro každé měření odpoví údajem o minimu z posledních $K$ měření 4. Prioritní fronta se někdy definuje tak, že prvky se stejnou prioritou vrací v pořadí, v jakém byly do fronty vloženy. Ukažte, jak takovou frontu realizovat pomocí haldy. Dosáhněte časové složitosti $\mathcal{O}(\log(N))$ na operaci. 5. Vymyslete algoritmus, který v haldě nalezne $k$-tý nejmenší prvek (najděte výsledek v čase $\mathcal{O}(k \log(k))$) --- ### Řešení Navrhněte reprezentaci fronty v poli, která bude pracovat v konstantním čase. Můžete předpokládat, že předem znáte horní odhad počtu prvků ve frontě. -- Bez chytřejšího přístupu se aplikace chová takto: ``` [0, 1, 2] # Základní pole [0, 1, 2, 3] # Přidám nový prvek [1, 2, 3] # Odeberu prvek [2, 3] # Odeberu prvek ``` Operační systém bude muset najít nový úsek v paměti pro $N+1$ (případně $N - 1$) prvků a všechny původní prvky tam překopírovat. To bude trvat $\mathcal{O}(N)$. --- Algoritmus (vstup maximální délka `max`): ```python pole = [0] * max zacatek = 0 konec = 0 def delka() -> int: return (konec - zacatek) % max def append(prvek: int) -> None: pole[konec] = prvek konec = (konec + 1) % max def popleft() -> int: prvek = pole[zacatek] zacatek = (zacatek + 1) % max return prvek ``` -- | 0. | 1. | 2. | 3. | 4. | 5. | 6. | 7. | 8. | 9. | | ---- | ---- | ----- | ----- | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | 1 | **2** | **3** | 0 | 0 | 0 | 0 | 0 | 0 | -- Nechť máme vstup délky maximálně $L$. Časová složitost přidání a odebrání $\mathcal{O}(1)$, paměťová složitost $\mathcal{O}(L)$ --- ### Řešení Navrhněte algoritmus, který zkontroluje správné uzávorkování aritmetického výrazu s více druhy závorek. ``` ["1", "*", "[", "5", "+", "(", "3", "]", "*", "2", "}"] ``` -- Algoritmus (vstup neprázdné `pole`): ```python otevrene = collections.deque() for prvek in pole: if je_oteviraci(prvek): otevrene.append(prvek) elif je_uzaviraci(prvek): posledni_otevreny = otevrene.pop() if not spravna_dvojice(posledni_otevreny, prvek): return False # Špatné uzávorkování # Aritmetiku kontrolovat nebudeme if len(otevrene) == 0: return True else: return False ``` -- Nechť máme vstup délky $N$. Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- ### Řešení Program dostává dlouhou sérii měření (délky $N$), pro každé měření odpoví údajem o minimu z posledních $K$ měření. -- Budu ukládat pouze posledních $K$ měření (budu mít haldu velikosti $K$). Pro každý prvek si vytvořím objekt, kde bude jeho hodnota a jeho pozice v haldě (index v poli haldy). 1. Pro každé nové číslo: 1. Vytvořím pomocný objekt a uložím do něj načtené číslo 2. Vložím objekt do fronty 3. Pokud je délka fronty < K 1. Přidám objekt do haldy (u všech přesunutých prvků v haldě opravím uloženou pozici v objektu) 4. Jinak: 1. Odeberu nejstarší prvek z fronty 2. Vložím nový objekt na pozici nejstaršího prvku v haldě 3. Opravím halu (u všech přesunutých prvků v haldě opravím uloženou pozici v objektu) 5. Vypíšu nejmenší prvek z haldy Časová složitost $\mathcal{O}(N \cdot \log(K))$, paměťová složitost $\mathcal{O}(K)$ --- ## Domácí úkol Máme rozsáhlý soubor s textem délky $N$ slov, který se nám nevejde do paměti počítače. Máme pak druhá rozsáhlý soubor, kde na každém řádku máme všechny gramatické tvary téhož slova („synonyma“). Tyto skupiny (tzn. řádky) jsou navzájem disjunktní, soubor obsahuje celkem $M$ slov. První slovo na každém řádku = základní tvar (vypisuje se na výstup). Ani tento soubor se nevejde do do vnitřní paměti počítače. Najděte algoritmus, který nalezne nejčastějších 100 slov (bez ohledu na gramatický tvar použitý v textu). Nalezená slova vypište v základním tvaru. Určete časovou složitost v závislosti na $M$ a $N$. Zapište váš algoritmus v nějakém pseudokódu a krátce popište svoje řešení. --- ### Příklad První soubor ``` ahoj auty auto hodiny auta hodin aut ahoj bota ``` Druhý soubor ``` ahoj auto auta aut auty hodiny hodin hodinám ``` Výstup ``` auto hodiny ahoj bota ```