# Programování II pro matematiky ## Teoretické cvičení 06 **7. 4. 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í - Spojový seznam - Jednosměrný  - Obousměrný  ```python class Prvek: def __init__(self, hodnota): self.hodnota = hodnota self.dalsi = None self.predchozi = None ``` ---  ---  --- ## Poznámky k Počet jedniček ve 2D - [2D prefixové součty](https://ksp.mff.cuni.cz/kucharky/zakladni-algoritmy/) byly za plný počet bodů - Časová složitost $\mathcal{O}(R \cdot S + K)$ - Nedává smysl používat $N$, když není v zadání - Paměťová složitost 2D prefixů $\mathcal{O}(R \cdot S)$ - $(R+1) \cdot (S+1) = R \cdot S + R + S + 1$ - `np.reshape`, `np.vstack` a `np.concatenate` nejsou vhodné pro teoretické domácí úkoly - 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] ``` - Používání proměnných `a`, `b`, `c`, `d` nepomáhá čitelnosti --- ## Příklady Najděte algoritmus a určete jeho časovou a prostorovou složitost v nejhorším případě. 1. 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. 2. Vymyslete algoritmus, který v haldě nalezne $k$-tý nejmenší prvek (najděte výsledek v čase $\mathcal{O}(k \log(k))$) __Na vstupu máme lineární spojový seznam.__ 1. Najděte v něm největší prvek. 2. Chceme z něj odebrat všechny hodnoty o danné hodnotě. 3. Chceme slít dva uspořádané seznamů do jednoho (merge) 4. Chceme obrátit pořadí prvků v jednosměrném seznamu. --- ### Řešení 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. -- Standardní halda z definice splňuje požadavek na časovou složitost. Halda ale není stabilní, tak jí musíme udělat stabilní. **Vstup: **` {1, 5, 2a, 3, 2b, 6, 2c}`, **Výstup HeapSortu:** `{1, 2c, 2b, 2a, 3, 5, 6}` -- Vložím do haldy `(klič, čas_vložení)` a řadím nejprve podle klíče a pak podle času (ošklivé řešení). -- Nechť máme vstup délky maximálně $N$. Časová složitost přidání a odebrání $\mathcal{O}(\log(N))$, paměťová složitost $\mathcal{O}(N)$ --- ### Řešení Vymyslete algoritmus, který v haldě nalezne $k$-tý nejmenší prvek (najděte výsledek v čase $\mathcal{O}(k \log(k))$) -- Standardní halda z definice odebere $k$ prvků v čase $\mathcal{O}(k \log(N))$) --  --- **Algoritmus:** (Vstup: minimální halda uložena v `vstup`): ```python UkazatelHaldovy = namedtuple('UkazatelHaldovy', ['hodnota', 'levy_index', 'pravy_index']) def pridej(index): levy = 2*index+1 pravy = 2*index+2 heappush(pomocna_halda, UkazatelHaldový(vstup[idnex], levy if levy < len(vstup) else None, pravy if pravy < len(vstup) else None)) pomocna_halda = [UkazatelHaldovy(vstup[0], 1, 2)] for i in range(k-1): # i-ty nejmenší prvek ukazatel = heappop(pomocna_halda) if ukazatel.levy_index: pridej(ukazatel.levy_index) if ukazatel.pravy_index: pridej(ukazatel.pravy_index) return pomocna_halda[0].hodnota ``` --- ### Řešení Na vstupu máme lineární spojový seznam. Najděte v něm největší prvek. ```python class Prvek: def __init__(self, hodnota): self.hodnota = hodnota self.dalsi = None self.predchozi = None ``` -- **Algoritmus:** (Vstup: Odkaz na první prvek spojového seznamu `seznam`): ```python iterator = seznam maximalni_prvek = seznam while iterator is not None: if maximalni_prvek.hodnota < iterator.hodnota: maximalni_prvek = iterator iterator = iterator.dalsi return maximalni_prvek ``` -- Nechť máme seznam délky $N$. Časová složitost hledání $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- ## Řešení Na vstupu máme lineární spojový seznam. Chceme z něj odebrat všechny hodnoty o danné hodnotě. --- **Algoritmus:** (Vstup: Odkaz na první prvek spojového seznamu `seznam`, hodnota k odebrání `x`): ```python iterator = seznam pred_intervalem = None v_intervalu = False while iterator is not None: if iterator.hodnota == iterator.hodnota: pred_intervalem = iterator.predchozi v_intervalu = True elif v_intervalu: if pred_intervalem pred_intervalem.dalsi = iterator iterator.predchozi = pred_intervalem else seznam = iterator iterator.predchozi = None v_intervalu = False iterator = iterator.dalsi ``` -- Nechť máme seznam délky $N$. Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- **Algoritmus:** (Vstup: Odkaz na první prvek spojového seznamu `seznam`, hodnota k odebrání `x`): ```python iterator = seznam pred_intervalem = None posledni = None v_intervalu = False while iterator is not None: if iterator.hodnota == iterator.hodnota: pred_intervalem = posledni v_intervalu = True elif v_intervalu: if pred_intervalem pred_intervalem.dalsi = iterator else seznam = iterator v_intervalu = False posledni = iterator iterator = iterator.dalsi ``` -- Nechť máme seznam délky $N$. Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- ### Řešení Na vstupu máme lineární spojový seznam. Chceme slít dva uspořádané seznamů do jednoho (merge). --- **Algoritmus:** (Vstup: Odkaz na první prvek spojového seznamu `A`, `B`): ```python def spoj(prvni: Prvek, druhy: Prvek) -> None: prvni.dalsi = druhy druhy.predchozi = prvni it_a = A it_b = B vystup = None konec = None while it_a is not None and it_b is not None: # Najdi naximalni prvek if it_a.hodnota > it_b.hodnota: maximum = it_a it_a = it_a.dalsi else maximum = it_b it_b = it_b.dalsi # Připoj maximum na výsledek if konec spoj(konec, maximum) else: vystup = maximum konec = maximum ``` --- ```python assert it_a is None or it_b is None # Invariant (co by mělo platit) if it_a is not None: it = it_a else it = it_b while it is not None: spoj(konec, it) it = it.dalsi return vystup ``` -- Nechť máme seznam délky $N$ a $M$. Časová složitost hledání $\mathcal{O}(N + M)$, paměťová složitost $\mathcal{O}(N + M)$ --- ### Řešení Na vstupu máme lineární spojový seznam. Chceme obrátit pořadí prvků v jednosměrném seznamu. -- **Algoritmus:** (Vstup: Odkaz na první prvek spojového seznamu `seznam`): ```python iterator = seznam konec = None # Vytvoříme obousměrný seznam while iterator is not None: if not konec: konec = PrvekObousmerny(iterator.hodnota) else: konec.dalsi = PrvekObousmerny(iterator.hodnota) konec.dalsi.predchozi = konec konec = konec.dalsi iterator = iterator.dalsi ``` --- ```python # Vytvoříme jednostranný seznam iterator = konec vysledek = None konec = None while iterator is not None: if not konec: vysledek = Prvek(iterator.hodnota) konec = vysledek else konec.dalsi = Prvek(iterator.hodnota) konec = konec.dalsi iterator = iterator.predchozi return vysledek ``` -- Nechť máme seznam délky $N$. Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$