# 1. (10 bodů)
Hřiště pro trénink bojových sportů obsahuje několik sloupků částečně zapuštěných do země. Adept má za úkol provést sérii přeskoků tak, aby se dostal od počátečního sloupku k cílovému s co nejmenším počtem přeskoků. Aby udržel rovnováhu, může přeskakovat jen mezi sloupky, jejichž (euklidovská) vzdálenost činí alespoň 1 m a nejvýše 2 m.

![sloupky](./sloupky.png)

V jazyce Python lze sloupky na obrázku výše reprezentovat jako **seznam** (tj. hodnotu datového typu `list`) **dvojic**, které reprezentují **souřadnice sloupků** v metrech: `[(-1,2),(2,2),(-2,1),(1,1),(0,0),(3,0),(0,-1),(1,-1),(2,-2),(3,-2)]`

Na vstupu je zadán
- **seznam** pozic **sloupků** (v libovolném pořadí) 
- **indexy** **počátečního** a **cílového** sloupku v seznamu.

Na výstupu bude vydán **seznam** pozic **sloupků**, po nichž bude adept přeskakovat tak, aby cestu z počátečního do cílového zdolal s co **nejmenším počtem přeskoků**. Pokud řešení neexistuje, bude vrácena hodnota `None`.

Navrhněte postup, jak správně vyřešit úlohu **s co nejlepší časovou a prostorovou složitostí** vzhledem k délce vstupního seznamu.

(a) **Popište algoritmus**: programový kód v Pythonu není povinný, **slovní vysvětlení** zvoleného postupu řešení naopak **povinné** je. Nepoužívejte žádné netriviální datové struktury (např. datové typy `dictionary` či `set` v Pythonu), 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ě). Do prostorové složitosti započítejte jen paměť, do niž se zapisuje (pokud ze vstupního seznamu jen čtete, není ho tedy třeba do prostorové složitosti zahrnovat).



## **Příklady:**

**Poznámka:** V příkladech jsou pro jednoduchost souřadnice všech sloupků celočíselné (obrázek výše), obecně tomu tak být nemusí.

**Vstup:** `[(-1,2),(2,2),(-2,1),(1,1),(0,0),(3,0),(0,-1),(1,-1),(2,-2),(3,-2)]  4  5`

**Výstup:** `[(0,0),(1,-1),(2,-2),(3,-2),(3,0)]`

**Vstup:** `[(-1,2),(2,2),(-2,1),(1,1),(0,0),(3,0),(0,-1),(1,-1),(2,-2),(3,-2)]  2  5`

**Výstup:** `None`

# 2. (10 bodů)

Je zadán binární strom, v jehož vrcholech jsou uložena čísla. Navrhněte efektivní algoritmus, který zjistí **cenu stromu**, definovanou jako
- součet cen všech jeho listů,
- kde cena listu je rovna součinu hloubky listu a hodnoty v něm uložené,
- přičemž hloubka listu je rovna počtu hran na cestě z kořene do tohoto listu.

(a) Svoje řešení zapište jako **funkci v Pythonu** (která obdrží kořen binárního stromu a vrátí jeho cenu), přitom využijte definici třídy pro vrchol binárního stromu níže a kód opatřete **komentáři,**

(b) zdůvodněte **správnost**,

(c) odvoďte **časovou a prostorovou složitost** (měřeno nejhorším případem).

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

def cena(koren: VrcholBinStromu) -> int:
    """
    koren : kořen zadaného binárního stromu
    vrátí : cenu zadaného stromu

    """
```

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

## Příklad:
**Vstup:** ![](./strom.png)

**Výstup:** 205
 (zdůvodnění: 2·40 + 3·10 + 3·5 + 2·20 + 2·20 = 205)

<{Details(Spoiler: reseni)}>

```python
# Je zadán binární strom, v jehož vrcholech jsou uložena čísla. 
# Navrhněte efektivní algoritmus, který zjistí cenu stromu, 
# definovanou jako součet cen všech jeho listů,

# kde cena listu je rovna součinu hloubky listu a hodnoty v něm uložené,

# přičemž hloubka listu je rovna počtu hran na cestě z kořene do tohoto listu. => čiže ta standardní definice

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

def cena(koren: VrcholBinStromu) -> int:
    """
    koren : kořen zadaného binárního stromu
    vrátí : cenu zadaného stromu

    """
    def rekurze(vrchol: VrcholBinStromu, hloubka):
        # list
        if not vrchol.levy and not vrchol.pravy:
            return vrchol.data * hloubka
        # vnitrni vrchol (= cokoliv co ma potomky)
        a = 0
        b = 0
        if vrchol.levy:
            a = rekurze(vrchol.levy, hloubka + 1)
            
        if vrchol.pravy:
            b = rekurze(vrchol.pravy, hloubka + 1)
    
        return a + b
        
    return rekurze(koren, 0)


vstup = VrcholBinStromu(
    "",
    VrcholBinStromu(
        "",
        VrcholBinStromu(40),
        VrcholBinStromu(
            "",
            VrcholBinStromu(10),
            VrcholBinStromu(5)
        )
    ),
    VrcholBinStromu(
        "",
        VrcholBinStromu(20),
        VrcholBinStromu(20)
    )
)

print(cena(vstup))
```
<{/Details}>

# 3.

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

## (a) (5 bodů)
Prvek posloupnosti délky *n* nazveme *pseudomediánem*, pokud leží v uspořádané posloupnosti na *k*-tém místě, kde *n/2 - 1 ≤ k ≤ n/2 + 1* . Dokažte nebo vyvraťte následující tvrzení:

`Kdyby se nám v algoritmu QuickSort podařilo v každém kroku vybrat v čase O(1) jako pivota pseudomedián, algoritmus bude pracovat v nejhorším případě v čase O(n log n).`

Svoji odpověď zdůvodněte, tj. tvrzení dokažte (pokud platí) či vyvraťte (pokud neplatí).

Poznámka: Ve vaší analýze složitosti můžete předpokládat, že prvky na vstupu jsou po dvou různé.

## (b) (5 bodů)

Předpokládejme, že se **minimaxovým algoritmem** podařilo ohodnotit celý **strom hry** šachy. Připomeňme, že listy byly ohodnoceny hodnotami
- **1** (pokud vyhrál bílý), 
- **-1** (vyhrál černý) a
- **0** (remíza).

Dokažte nebo vyvraťte: `Je-li kořen stromu hry ohodnocen hodnotou nula, pak si černý hráč (který táhne jako druhý) může vynutit alespoň remízu.`