# Algoritmizace 1 - Zkouška - Töpfer, 24.1.2022

<{ForumPost(poster="Anonymous", timestamp=2022-01-24 12:14:49)}>
**90 minut** na vypracování řešení  
  
**1. (10 bodů)** Na vstupu je posloupnost *n* celých čísel.  Zjistěte, zdali existuje dvojice celých čísel a ≤ b taková, že jak a-1 tak b+1 v posloupnosti leží, zatímco žádné z čísel v (uzavřeném) intervalu ‹a,b› nikoliv. Pokud taková  "souvislá mezera" v posloupnosti existuje, vraťte dvojici a,b takovou, že a i b jsou minimální hodnoty, splňující uvedenou podmínku. Pokud neexistuje, vraťte hodnotu *None*.  
  
Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou a prostorovou složitostí vzhledem k délce vstupní posloupnosti.   
  
(a)**Popište algoritmus:** programový kód v Pythonu je vítán, ale není povinný, **slovní vysvětlení** zvoleného postupu řešení naopak povinné je. Nepoužívejte žádné netriviální datové struktury (typu zásobník, fronta, halda, slovník), jejichž algoritmus sami nepopíšete a neodvodíte jeho časovou složitost.  
  
(b) Zdůvodněte **správnost** algoritmu.   
  
(c) Odvoďte **časovou a prostorovou složitost** (v nejhorším případě).  
  
Příklad:   
vstup:    22  8  5  2000  6  5  20  100000  7  15  20  6   
výstup:   9  14     
  
Poznámka: Úlohu lze vyřešit s časovou i prostorovou složitostí 0(n). Netriviální počet bodů bude ovšem udělen i za méně efektivní řešení.  

----

**2. (10 bodů)** Na vstupu je zadán   
  
**binární vyhledávací strom** (BVS), v jehož vrcholech jsou uložena celá čísla  
a dvě celá čísla d ≤ h .   
Navrhněte efektivní algoritmus, který ze zadaného BVS  

* **odstraní** všechny **vrcholy** s hodnotami < d nebo > h

* a **vrátí odkaz na kořen** výsledného BVS.

Na výstupu tedy bude BVS, v němž jsou uloženy právě ty hodnoty ze vstupního BVS, které leží v uzavřeném intervalu ‹d,h›.   
  
Poznámka: Ani BVS na vstupu, ani BVS na výstupu nemusí být nutně vyvážený.  
  
(a) Svoje řešení zapište jako **funkci v Pythonu**, využijte **definici třídy** pro vrchol binárního stromu uvedenou **níže** a váš kód opatřete **komentáři**,  
  
(b) zdůvodněte **správnost**,  
  
(c) odvoďte **časovou složitost**.  

    class VrcholBinStromu:
        """třída pro reprezentaci vrcholu binárního stromu""" 
        def __init__(self, info = None, levy = None, pravy = None):
            self.info = info # data
 
            self.levy = levy # levé dítě 
            self.pravy = pravy # pravé dítě 
    
    def zuzeniBVS(koren: VrcholBinStromu, d: int, h: int) -> VrcholBinStromu:
        """
        koren : kořen zadaného binárního vyhledávacího stromu
        vrátí : kořen zúženého binárního vyhledávacího stromu
        """
    

----

**3.** Odpovězte na otázky, své odpovědi vždy **zdůvodněte**.  
  
(a) **(5 bodů)** Dokažte nebo vyvraťte každé z následujících tvrzení:   

* pro libovolné tři funkce $f, g, h: \mathbb{N} \to \mathbb{R}^{+}$ platí  
  
jestliže $f \in  \mathcal{O}(g), \; g \in  \mathcal{O}(h)$ , potom  $f \cdot g  \in  \mathcal{O}(h)$

* pro libovolné tři funkce $f, g, h: \mathbb{N} \to \mathbb{R}^{+}$ platí  
  
jestliže  $f  \in  \mathcal{O}(g), \; g  \in  \mathcal{O}( h )$ , potom $f \cdot g  \in  \mathcal{O}(h^2)$

* pro libovolné tři funkce $f, g, h: \mathbb{N} \to \mathbb{R}^{+}$ platí  
  
jestliže  $f  \in  \mathcal{O}(g), \; g  \in   \mathcal{O}(h)$, potom $f \cdot g  \in \mathcal{O}(h^3)$

Svoji odpověď **zdůvodněte**, tj. tvrzení dokažte (pokud platí) či sestrojte protipříklad (pokud neplatí). Nestačí jen napsat, že je to triviální či že to bylo na přednášce / cvičeních apod.  
  
(b) **(5 bodů)** Budeme pracovat s minimalistickou binární haldou (v kořeni je minimum). Potřebujeme implementovat operaci **zrušení zadaného prvku** z haldy:  

* vstupem algoritmu bude halda a odkaz na jeden její vrchol x, jehož hodnotu chceme zrušit

* výstupem bude patřičně změněná halda.

V následujícím popisu si haldu představujeme v podobě binárního stromu. Požadovaný algoritmus jsme implementovali takto:  

1. Odebereme z haldy její poslední vrchol, tzn. vrchol ležící v poslední vrstvě haldy co nejvíce vpravo.{: style="list-style-type:decimal"}

* Hodnotou tohoto odebraného vrcholu nahradíme hodnotu ve vrcholu x.{: style="list-style-type:2"}

* Dále postupujeme stejně, jako při standardní operaci odebrání minima z haldy:

    * novou hodnotu vrcholu x porovnáme s hodnotami v obou jeho dětech
    * v případě potřeby vyměníme  s menším z obou dětí

    * a obdobným způsobem postupujeme dále haldou směrem dolů, dokud je zapotřebí vyměňovat hodnoty.{: style="list-style-type:3"}

**Rozhodněte, zda je** popsaná implementace požadovaného algoritmu **korektní**. Svoje tvrzení **zdůvodněte**.
<{/ForumPost}>