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.

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

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:

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

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