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

<{ForumPost(poster="wildgreen", timestamp=2023-01-23 23:26:23)}>
Na celou zkoušku jsou 2 hodiny + 10 minut na odevzdání v Moodle. Před začátkem testu se rozebírá zadání každé úlohy a upřesnění podmínek, tento čas se do vyřešení nezapočítává. Důkazy a zdůvodnění nemusí být ryze matematické a formální s ohledem na to, že jde o první ročník studia, ale doporučuje se co největší přesnost a jednoznačnost v popisu řešení. Lze používat materiály z kurzu Moodle, tj. prezentace, kód a nahrávky přednášek.  

**Úloha 1 (10 bodů)** Na vstupu je zadána posloupnost **kladných celých čísel** délky n. Navrhněte efektivní algoritmus, který určí,  zdali v posloupnosti existuje **souvislý úsek** takový, že součet čísel v tomto úseku je **stejný**, jako součet čísel, které v něm neleží. Výstupem jsou  
  
    index prvního a index posledního prvku v  úseku (pozice čísel ve vstupní posloupnosti číslujeme od 0) a součet jeho prvků  
    či hodnota None, pokud takový neexistuje.  
  
Má-li úloha více řešení, stačí nalézt jedno libovolné z nich. 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 (včetně datových struktur, které případně budete používat). Programový kód není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Nepoužívejte prosím žádné netriviální datové struktury (jako jsou např. datové typy dictionary či set v jazyce Python), 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:     5  2  2  6  12  11  7  10  2  5  2  8  
výstup:   3  6  36  

---
  
**Úloha 2.**
  
**2. (10 bodů)** Je zadán **binární strom** o *n* vrcholech, v nichž jsou uložena navzájem různá celá čísla, a dále **celé číslo x**. Navrhněte efektivní algoritmus, který vrátí seznam čísel uložených ve všech vrcholech, které leží v podstromu s kořenem obsahujícím číslo x.  
  
(a) Svoje řešení zapište jako **funkci v Pythonu**, využijte **definici třídy** pro vrchol binárního stromu i **hlavičku funkce** uvedené níže a váš kód prosím opatřete **komentáři**,  
  
(b) zdůvodněte **správnost**,  
  
(c) odvoďte **časovou složitost** (v nejhorším případě).  

    class VrcholBinStromu:
        """třída pro reprezentaci vrcholu binárního stromu""" 
        def __init__(self, info = None, levy = None, pravy = None):
            self.info = info      # číslo vrcholu
            self.levy = levy      # levé dítě 
            self.pravy = pravy    # pravé dítě
    
    def podstrom(koren : VrcholBinStromu, x : int):
        """
        koren : kořen zadaného binárního stromu
        x     : celé čislo
        vrátí : seznam čísel uložených ve všech vrcholech, které leží v podstromu s kořenem obsahujícím číslo x
        """

---

**Úloha 3.**
  
3. Rozhodněte zda platí, své odpovědi vždy **zdůvodněte**.  
  
**(a) (5 bodů)** Rozhodněte, zda platí: Pro libovolné dvě funkce $f, g: \natnums \rightarrow \reals^+$ platí  
  
 * $f  = O(g)$   **právě tehdy, když** *$\log_2 f = O( \log_2 g )$.*  
  
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.  

<{Details(Spoiler: řešení)}>

Otázka tedy zní:

$f(n) \in O(g(n)) \iff \log_2(f(n)) \in O(\log_2 g(n))$

To neplatí, protipříklad:

$n_0 = 1$ třeba, pro obě strany.

$f(n) = n^2$, $g(n) = n$

Pravá strana:

$\log_2(f(n)) \in O(\log_2 g(n))$

$\log_2(n^2) \in O(\log_2 n)$

$\log_2(n^2) \le c \cdot \log_2 n$

$2 \cdot \log_2(n) \le c \cdot \log_2 n$ platí, př. $c = 4$.

Levá strana:

$f(n) \in O(g(n))$

$f(n) \le g(n)$

$n^2 \le c_2 \cdot n$

$n \cdot n \le c_2 \cdot n$ pro rostoucí $n$ taková konstanta $c_2$ neexistuje.

Takže pro tyto dvě zvolené funkce levá strana neplatí, pravá ano, pro stejná $n$ (pro všechna $n > n_0$), tedy tvrzení neplatí (pokud by platilo, mělo by platit pro libovolné dvě funkce $f, g: \natnums \rightarrow \reals^+$).

<{/Details}>

**(b) (5 bodů)** V binárním vyhledávacím stromu chceme implementovat operaci **odebrání prvku** s danou hodnotou klíče *x* následovně:   
Vyhledáme ve stromu vrchol *v* s hodnotou *x* (předpokládejme, že to umíme a že se *x* skutečně ve stromu nachází) a pak opakovaně provádíme následující kroky výpočtu:  


* je-li vrchol *v* listem, odebereme ho ze stromu a tím celá operace ***končí***

    
* není-li vrchol *v* listem, označíme symbolem *s* jeho jedno dítě (levé, má-li obě)

    
* hodnotu z vrcholu *s* zkopírujeme do vrcholu *v*

    
* symbolem *v* nyní označíme vrchol *s* .
 
Rozhodněte, zda výše popsaný postup korektně implementuje požadovanou operaci. Svoji odpověď zdůvodněte.**
<{/ForumPost}>