1. (10 bodů) Na vstupu je posloupnost n celých čísel. Zjistěte, zdali existuje dvojice celých čísel a ≤ b 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 d ≤ h .
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.
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 )
(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.
- 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.