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

<{ForumPost(poster="kruchi", timestamp=2023-01-09 13:36:52)}>
**Úloha 1.**  
  
**(10 bodů**) Na vstupu je posloupnost *n* celých čísel. Určete celé číslo, které má ze všech celých čísel, které se ve vstupní posloupnosti **nevyskytují**, **nejmenší absolutní hodnotu**. Pokud existují dvě taková čísla, stačí vrátit libovolné z nich (ve vašem popisu řešení ale upřesněte, zdali v takovém případě vracíte číslo záporné či kladné).  
  
Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou a prostorovou složitostí (měřeno nejhorším případem) vzhledem k délce vstupní posloupnosti. Maximální počet bodů bude udělen jen za řešení s časovou i prostorovou složitostí O(*n*).  
  
(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 (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  0 -2000  2  1  20  100000  7  -15  20  -1   
výstup:   -2    
**Poznámka**: Úlohu lze vyřešit s časovou i prostorovou složitostí O(*n*). Netriviální počet bodů bude ovšem udělen i za méně efektivní řešení.  
  
  
**Úloha 2.**  
  
**(10 bodů)** Je zadán **binární strom** o *n* vrcholech, v nichž jsou uložena navzájem různá celá čísla. Navrhněte efektivní algoritmus, který pro zadané číslo ***x*** vrátí seznam čísel všech vrcholů, které leží **na stejné hladině** jako vrchol s číslem ***x***. Pokud hodnota ***x*** ve stromě není, bude vrácen prázdný seznam.  
  
*Hladinu* binárního stromu tvoří všechny vrcholy se stejnou vzdáleností od kořene.  
  
(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      # data
            self.levy = levy      # levé dítě 
            self.pravy = pravy    # pravé dítě
    
    def hladina(koren : VrcholBinStromu, x : int):
        """
        koren : kořen zadaného binárního stromu
        x     : zadané ohodnocení hledaného vrcholu
        vrátí : seznam čísel vrcholů na hladině obsahující x
        """

  
**Úloha 3.**  
  
Odpovězte na otázky.  
  
(a) **(5 bodů)** Uvažte následující problém.  
  
Vstup: Setříděné pole a délky *n* , hodnoty x,y takové, že  x≤y  
Výstup: (libovolný) index i takový, že x ≤ a\[i] ≤ y  
              False pokud žádný takový neexistuje  
  
Dokažte nebo vyvraťte následující tvrzení, svoji **odpověď zdůvodněte**:  
  
Časová složitost řešení výše uvedeného problému porovnávacím algoritmem je Θ(log *n*).  
  
*Porovnávací algoritmus* přistupuje k prvkům zadaným na vstupu prostřednictvím operace porovnání dvou prvků  
*p < q , p > q , p ≤ q , p ≥ q , p = q ,*  
hodnoty prvků jinak nevyužívá.  
  
(b)  **(5 bodů)** Jsou zadány dva aritmetické výrazy v různých notacích:  
  
    (b1)   1 2 - 3 + 4 5 - / 6 7 - *  
    (b2)  - 1 - * - 2 + * 3 4 5 6 7  
  
Ke každému z výrazů

* určete, o jakou notaci se jedná (infix, prefix, postfix),
* sestrojte příslušný **strom aritmetického výrazu**
* a vypište hodnoty (operátory i operandy) v něm uložené v pořadí, v němž budou navštíveny při **průchodu stromem do šířky** (děti každého vrcholu navštěvujeme v pořadí levé, pravé).

Ve vaší odpovědi stačí vypsat hodnoty v požadovaném pořadí, nemusíte uvádět strom ani zdůvodnění.
<{/ForumPost}>