Zkouška

Úloha 1 (10 bodů)

Na vstupu obdržíme

vzestupně setříděné pole a celých čísel, v němž se čísla mohou libovolně opakovat
a celé číslo x.

V poli a určete a vraťte počet výskytů zadaného čísla x.

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 n vstupního pole a.

(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.

Příklady: vstup:

[-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200]
20

výstup:

vstup:

[-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200]
-1

výstup:

Poznámka: Za triviální řešení s časovou složitostí $O(n)$ bude udělen jen velmi nízký počet bodů!

Úloha 2 (10 bodů)

Je zadán binární strom o n vrcholech, v nichž jsou uložena celá čísla. Navrhněte efektivní algoritmus, který ve stromu určí počet listů bez sourozence. Dva různé vrcholy stromu jsou sourozenci, pokud mají stejného rodiče.

(a) Svoje řešení zapište jako funkci v Pythonu, využijte k tomu 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,

class VrcholBinStromu:

   """třída pro reprezentaci vrcholu binárního stromu"""  
   def  __init__(self, data =  None, levy =  None, pravy =  None):
      self.levy = levy    # levé dítě  
      self.pravy = pravy  # pravé dítě
      self.data = data    # hodnota uložená ve vrcholu (neměla by se měnit) 
  

def pocetListuBezSourozence(koren: VrcholBinStromu) -> int:

    """
    koren : kořen zadaného binárního stromu
    vrátí : počet listů bez sourozence
    """

Poznámka: Definici třídy ani hlavičku funkce prosím neměňte, můžete si ovšem definovat vlastní pomocnou funkci (funkce) dle potřeby.

Úloha 3

Odpovězte na otázky, své odpovědi vždy zdůvodněte.

(a) (5 bodů)

Uspořádejte funkce $n!, \ln (n!), e^n, n^2 \cdot \log n$ do posloupnosti $f_1, f_2, f_3, f_4$ tak, aby $f_1 = O(f_2), f_2 = O(f_3) a f_3 = O(f_4)$ .

Své odpovědi zdůvodněte.

Poznámka:

$\log n$ označuje $\log_2 n$ (tj. logaritmus při základu dva)
$\ln n$ označuje $\log_e n$ , kde $e \approx 2,71828182846$ je Eulerovo číslo.

(b) (5 bodů)

Vstup:

binární max-halda uložená v poli a (maximální prvek haldy je uložen v a[0])
index i
kladné číslo k.

Výstup:

binární halda, v níž byla hodnota prvku a[i] zvýšena o k, tj. nová hodnota je rovna a[i]+k, hodnoty ostatních prvků haldy zůstaly beze změny.

Poznámka: Dejte pozor na to, že operace zvýšení hodnoty může vyvolat nutnost změnit pořadí prvků v poli a tak, aby upravené pole opět představovalo binární haldu.

Dokažte nebo vyvraťte následující tvrzení, svoji odpověď zdůvodněte:

Existuje algoritmus, který výše uvedený problém vyřeší v čase $O(\log n)$ , kde $n$ je počet prvků haldy.

Časovou složitost měříme metodou nejhoršího případu.