# Zkouška Töpfer 27.1.2025 #### **Hodnocení:** Budou zadány 3 úlohy, celkem ohodnocené 30 body. - 25 - 30 bodů : výborně - 20 - 24 bodů : velmi dobře - 15 - 19 bodů : dobře - jinak : neúspěch Čas: 2h 15 min --- __Uloha 1__ ### (10 bodů) Hledání bezprostředního následníka v setříděném seznamu #### __Na vstupu obdržíme:__ - **Vzestupně setříděný (Pythonovský) seznam** \( a \) celých čísel, v němž se čísla mohou libovolně opakovat. - **Celé číslo** \( x \). V seznamu \( a \) určete: 1. **Číslo \( y \)**, které je **bezprostředním následníkem** čísla \( x \) (tj. **nejmenší prvek seznamu**, který je **větší než \( x \)**). 2. **Počet výskytů** tohoto čísla v seznamu. Pokud se takový **bezprostřední následník** v seznamu **nevyskytuje**, vraťte místo něj hodnotu `None`. Pozor na to, že číslo \( x \) **v seznamu ležet nemusí**! 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ího pole. __(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říklady vstupů a výstupů** **Vstup 1:** ```plaintext a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200] x = 10 ``` **Výstup 1:** ```plaintext 20 3 ``` **Vstup 2:** ```plaintext a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200] x = -50 ``` **Výstup 2:** ```plaintext -22 1 ``` **Vstup 3:** ```plaintext a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200] x = 200 ``` **Výstup 3:** ```plaintext None ``` <{Details(Spoiler: řešení)}> Následovníka lze nalézt v $O(\log n)$, počet též. ```python # najde index pred ktery prvek vlozit, aby bylo pole dal serazene # pokud prvek v poli neni, tak je to index naslednika # pokud prvek v poli je, tak taky (= nejpravejsi index, pred ktery vlozit) # funguje stejne jako # from bisect import bisect_right # return bisect_right(pole, cislo) def find_insertion_index_right(pole, cislo): l = 0 r = len(pole) - 1 while l <= r: mid = (l + r) // 2 if pole[mid] <= cislo: l = mid + 1 else: r = mid - 1 return l a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200] def find_naslednik(a,x): index_naslednika = find_insertion_index_right(a,x) #x je shodou nahod nejvetsi prvek v a, zadneho naslednika nema if index_naslednika == len(a): return None naslednik = a[index_naslednika] pocet_nasledniku = find_insertion_index_right(a, naslednik) - index_naslednika return f"{naslednik} {pocet_nasledniku}" print(find_naslednik(a, 200)) ``` <{/Details}> --- **Úloha 2** ### (10 bodů) Maximální počet operátorů v podvýrazu bez dělení Je zadán **strom aritmetického výrazu**, tj. binární strom, v jehož **vnitřních vrcholech** jsou uloženy operátory (`+`, `-`, `*`, `/`) a v listech čísla. Navrhněte efektivní algoritmus, který vrátí **maximální počet operátorů** v podvýrazu, který **neobsahuje dělení** (tj. neobsahuje operátor `/`). Připomeňme, že **podvýraz** je vždy reprezentován podstromem, který obsahuje všechny následníky svého kořene. #### **(a) Implementace** - Svoje řešení zapište jako **funkci v Pythonu**. - Využijte k tomu definici **třídy pro vrchol binárního stromu**. - Použijte **hlavičku funkce uvedenou níže**. - Váš kód **opatřete komentáři**. - Můžete předpokládat, že vstup je **zadán korektně**. #### **(b) Zdůvodnění správnosti** - Vysvětlete, proč algoritmus správně počítá maximální počet operátorů v podvýrazu bez dělení. #### **(c) Analýza časové složitosti** - Odvoďte **časovou složitost** algoritmu jako **funkci počtu vrcholů** \( n \) ve stromu. - Použijte metodu **nejhoršího případu**. #### Definice třídy pro vrchol binárního stromu: ```python class VrcholBinStromu: """Třída pro reprezentaci vrcholu binárního stromu""" def __init__(self, hodnota=None, levy=None, pravy=None): self.hodnota = hodnota # Hodnoty (operátory či operandy) uložené ve vrcholech self.levy = levy # Levé dítě self.pravy = pravy # Pravé dítě def pocetOp(koren: VrcholBinStromu) -> int: """ koren : kořen zadaného binárního stromu vrátí : maximální počet operátorů v podvýrazu bez dělení """ ``` #### **Příklad vstupu a výstupu** **Vstup:** '![](/NPRG062/Zkouška Töpfer 27.1.2025-strom) **Výstup:** ```plaintext 3 ``` **Zdůvodnění:** Podstrom zakořeněný v pravém dítěti kořene obsahuje celkem 3 operátory a všechny jsou různé od /. Naopak žádný podvýraz bez dělení s alespoň 4 operátory neexistuje. <{Details(Spoiler: Studentské řešení)}> Bez a), b) c) zdůvodnění, ale snad pomůže v učení :) ```python class VrcholBinStromu: """Třída pro reprezentaci vrcholu binárního stromu""" def __init__(self, hodnota=None, levy=None, pravy=None): self.hodnota = hodnota # Hodnoty (operátory či operandy) uložené ve vrcholech self.levy = levy # Levé dítě self.pravy = pravy # Pravé dítě def pocetOp(koren: VrcholBinStromu) -> int: """ koren : kořen zadaného binárního stromu vrátí : maximální počet operátorů v podvýrazu bez dělení """ dosavadni_maximum = 0 def pocitej(koren: VrcholBinStromu): nonlocal dosavadni_maximum # je list if not koren.levy and not koren.pravy: return 0 # pocitam pocet operatoru podstromu zakoreneneho v aktualnim vrcholu # jestli podstrom obsahuje "/" tak pocet nastavim na -1 a tim poslu nahoru zpravu, ze s timhle uz podstrom bez "/" nepostavi # pokud neobsahuje, tak poslu nahoru pocet operatoru ve svem levem a pravem podstromu + sebe (to je to + 1) # pomoci dosavadni_maximum si trackuju nejvyssi dosazeny pocet operatoru pocet_levy_podstrom = 0 pocet_pravy_podstrom = 0 if koren.levy: pocet_levy_podstrom = pocitej(koren.levy) if koren.pravy: pocet_pravy_podstrom = pocitej(koren.pravy) #nejsem "/" if koren.hodnota != "/": pocet = max(pocet_levy_podstrom, pocet_pravy_podstrom) # pokud navic neni ani v levem ani v pravem podstromu "/", # tak muzu z nich a sebe slepit podstrom s o 1 vic operatory if min(pocet_levy_podstrom, pocet_pravy_podstrom) != -1: if pocet + 1 > dosavadni_maximum: dosavadni_maximum = pocet + 1 return pocet + 1 else: #pokud v levem nebo pravem podstromu je "/", tak poslu nahoru zpravu ze s timhle vrcholem ne return -1 else: #pokud jsem "/", tak poslu nahoru zpravu return -1 pocitej(koren) return dosavadni_maximum ``` <{/Details}> --- **Úloha 3** Odpovězte na následující otázky a své odpovědi vždy zdůvodněte. ### **(a) (5 bodů) Asymptotická analýza funkcí** Dokážte nebo vyvraťte každé z následujících tvrzení: **(a1)** Pro libovolné tři funkce $f, g, h: \mathbb{N} \to \mathbb{R}^+$ platí: > Jestliže $f = O(h)$ a $g = \Omega(h)$, potom $f = O(g)$. <{Details(Spoiler: řešení)}> $f \in O(h) \land g \in \Omega(h) \implies f \in O(g)$ $f(n) \in O(h(n)) \land g(n) \in \Omega(h(n)) \implies f(n) \in O(g(n))$ Podle definice: $$f(n) \in O(h(n)) \iff \exists c_1 \in \reals^+ \ \exists n_{0_1} \in \natnums \ \forall n \ge n_{0_1}: \boxed{f(n) \le c_1 \cdot h(n)}$$ $$g(n) \in \Omega(h(n)) \iff \exists c_2 \in \reals^+ \ \exists n_{0_2} \in \natnums \ \forall n \ge n_{0_2}: \boxed{g(n) \ge c_2 \cdot h(n)}$$ Vyjádříme z obou nerovnic $h(n)$: $f(n) \le c_1 \cdot h(n)$ $c_1 \cdot h(n) \ge f(n)$ $\boxed{\frac{1}{c_1} \cdot f(n) \le h(n)}$ $g(n) \ge c_2 \cdot h(n)$ $\boxed{h(n) \le \frac{1}{c_2} \cdot g(n)}$ Když to poté složíme do jednoho, máme pro $n_0 = \max\{n_{0_1}, n_{0_2}\}$: $\frac{1}{c_1} \cdot f(n) \le h(n) \le \frac{1}{c_2} \cdot g(n)$ U toho můžeme vynechat prostřední člen: $\frac{1}{c_1} \cdot f(n) \le \frac{1}{c_2} \cdot g(n)$ A poté vyjádřit $f(n)$: $f(n) \le \frac{c_1}{c_2} \cdot g(n)$ To se shoduje s pravou stranou $f(n) \in O(g(n))$, která též platí pro $n_0 = \max\{n_{0_1}, n_{0_2}\}$: $f(n) \le c \cdot g(n)$ Existuje $c$ takové, že se rovná $\frac{c_1}{c_2}$. Tvrzení platí. <{/Details}> **(a2)** Pro libovolné tři funkce $f, g, h: \mathbb{N} \to \mathbb{R}^+$ platí: > Jestliže $f = O(h)$ a $g = \Omega(h)$, potom $f \cdot g = \Omega(h)$. 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ů) QuickSort s pseudomediánem** V této úloze pracujeme s posloupnostmi prvků, které lze porovnávat a které se **neopakují**. Prvek takové posloupnosti délky $n$ nazveme *pseudomediánem* pokud leží v uspořádané posloupnosti na **k-tém místě**, kde $\frac{n}{10} \leq k \leq \frac{9n}{10}$ Profesor Hammerstein se na přednášce otázal studentů: Kdyby se nám v algoritmu QuickSort podařilo v každém kroku vybrat v čase O(1) jako pivota pseudomedián, v jakém čase (měřeno nejhorším případem) algoritmus setřídí zadanou posloupnost délky n ? > Kdybychom v algoritmu **QuickSort** dokázali v **každém kroku** vybrat v čase \( O(1) \) **pseudomedián** jako pivota, v jakém čase (v nejhorším případě) by algoritmus setřídil vstupní posloupnost délky \( n \)? - **John** se domnívá, že algoritmus bude pracovat v čase $\Theta(n^2)$. - **Donald** soudí, že časová složitost bude $ \Theta(n \log n) $. - **Bill** si myslí, že půjde o čas $\Theta(n)$. Kteří studenti mají pravdu a kteří nikoliv (John - ANO / NE, Donald - ANO / NE, Bill - ANO / NE) ? **Svoji odpověď zdůvodněte !** - Pozor, že v zadání máme **$ \Theta $** (nikoliv jen $O$), takže je nutné zdůvodnit jak **horní**, tak **dolní** odhad složitosti algoritmu.