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:

Číslo ( y ), které je bezprostředním následníkem čísla ( x ) (tj. nejmenší prvek seznamu, který je větší než ( x )).
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:

Defaulting to plain text due to invalid arguments: "#!highlight plaintext"

a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200]
x = 10

Výstup 1:

Defaulting to plain text due to invalid arguments: "#!highlight plaintext"

20 3

Vstup 2:

Defaulting to plain text due to invalid arguments: "#!highlight plaintext"

a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200]
x = -50

Výstup 2:

Defaulting to plain text due to invalid arguments: "#!highlight plaintext"

-22 1

Vstup 3:

Defaulting to plain text due to invalid arguments: "#!highlight plaintext"

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

Výstup 3:

Defaulting to plain text due to invalid arguments: "#!highlight plaintext"

None

Spoiler: řešení

Následovníka lze nalézt v $O(\log n)$ , počet též.

# 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))

Ú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:

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:
'

Item 'NPRG062/Zkouška Töpfer 27.1.2025-strom' does not exist, click to create

Výstup:

Defaulting to plain text due to invalid arguments: "#!highlight plaintext"

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.

Spoiler: Studentské řešení

Bez a), b) c) zdůvodnění, ale snad pomůže v učení :)

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

Ú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)$ .

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

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