Algoritmizace 1 - Zkouška - Töpfer, 24.1.2022

Vše co není uvedeno jinde
Návštěvník

Algoritmizace 1 - Zkouška - Töpfer, 24.1.2022

Příspěvek od Návštěvník »

90 minut na vypracování řešení

1. (10 bodů) Na vstupu je posloupnost n celých čísel. Zjistěte, zdali existuje dvojice celých čísel ab taková, že jak a-1 tak b+1 v posloupnosti leží, zatímco žádné z čísel v (uzavřeném) intervalu ‹a,b› nikoliv. Pokud taková "souvislá mezera" v posloupnosti existuje, vraťte dvojici a,b takovou, že a i b jsou minimální hodnoty, splňující uvedenou podmínku. Pokud neexistuje, vraťte hodnotu None.

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

(a) Popište algoritmus: programový kód v Pythonu je vítán, ale není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Nepoužívejte žádné netriviální datové struktury (typu zásobník, fronta, halda, slovník), 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říklad:
vstup: 22 8 5 2000 6 5 20 100000 7 15 20 6
výstup: 9 14

Poznámka: Úlohu lze vyřešit s časovou i prostorovou složitostí 0(n). Netriviální počet bodů bude ovšem udělen i za méně efektivní řešení.

2. (10 bodů) Na vstupu je zadán

binární vyhledávací strom (BVS), v jehož vrcholech jsou uložena celá čísla
a dvě celá čísla dh .
Navrhněte efektivní algoritmus, který ze zadaného BVS
  • odstraní všechny vrcholy s hodnotami < d nebo > h
  • a vrátí odkaz na kořen výsledného BVS.
Na výstupu tedy bude BVS, v němž jsou uloženy právě ty hodnoty ze vstupního BVS, které leží v uzavřeném intervalu ‹d,h›.

Poznámka: Ani BVS na vstupu, ani BVS na výstupu nemusí být nutně vyvážený.

(a) Svoje řešení zapište jako funkci v Pythonu, využijte definici třídy pro vrchol binárního stromu uvedenou níže a váš kód opatřete komentáři,

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

(c) odvoďte časovou složitost.

Kód: Vybrat vše

class VrcholBinStromu:
    """třída pro reprezentaci vrcholu binárního stromu""" 
    def __init__(self, info = None, levy = None, pravy = None):
        self.info = info # data
 
        self.levy = levy # levé dítě 
        self.pravy = pravy # pravé dítě 

def zuzeniBVS(koren: VrcholBinStromu, d: int, h: int) -> VrcholBinStromu:
    """
    koren : kořen zadaného binárního vyhledávacího stromu
    vrátí : kořen zúženého binárního vyhledávacího stromu
    """

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

(a) (5 bodů) Dokažte nebo vyvraťte každé z následujících tvrzení:
  • pro libovolné tři funkce f, g, h: N → R+ platí

    jestliže f = O( g ) a g = O( h ) , potom f · g = O( h )
  • pro libovolné tři funkce f, g, h: N → R+ platí

    jestliže f = O( g ) a g = O( h ) , potom f · g = O( h2 )
  • pro libovolné tři funkce f, g, h: N → R+ platí

    jestliže f = O( g ) a g = O( h ) , potom f · g = O( h3 )
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ů) Budeme pracovat s minimalistickou binární haldou (v kořeni je minimum). Potřebujeme implementovat operaci zrušení zadaného prvku z haldy:
  • vstupem algoritmu bude halda a odkaz na jeden její vrchol x, jehož hodnotu chceme zrušit
  • výstupem bude patřičně změněná halda.
V následujícím popisu si haldu představujeme v podobě binárního stromu. Požadovaný algoritmus jsme implementovali takto:
  1. Odebereme z haldy její poslední vrchol, tzn. vrchol ležící v poslední vrstvě haldy co nejvíce vpravo.
  • Hodnotou tohoto odebraného vrcholu nahradíme hodnotu ve vrcholu x.
  • Dále postupujeme stejně, jako při standardní operaci odebrání minima z haldy:
    • novou hodnotu vrcholu x porovnáme s hodnotami v obou jeho dětech
    • v případě potřeby vyměníme s menším z obou dětí
    • a obdobným způsobem postupujeme dále haldou směrem dolů, dokud je zapotřebí vyměňovat hodnoty.
Rozhodněte, zda je popsaná implementace požadovaného algoritmu korektní. Svoje tvrzení zdůvodněte.
Odpovědět

Zpět na „Ostatní“