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

Vše co není uvedeno jinde
wildgreen
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 23. 1. 2023 23:13
Typ studia: Informatika Bc.

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

Příspěvek od wildgreen »

Na celou zkoušku jsou 2 hodiny + 10 minut na odevzdání v Moodle. Před začátkem testu se rozebírá zadání každé úlohy a upřesnění podmínek, tento čas se do vyřešení nezapočítává. Důkazy a zdůvodnění nemusí být ryze matematické a formální s ohledem na to, že jde o první ročník studia, ale doporučuje se co největší přesnost a jednoznačnost v popisu řešení. Lze používat materiály z kurzu Moodle, tj. prezentace, kód a nahrávky přednášek.

Úloha 1.

1. (10 bodů) Na vstupu je zadána posloupnost kladných celých čísel délky n. Navrhněte efektivní algoritmus, který určí, zdali v posloupnosti existuje souvislý úsek takový, že součet čísel v tomto úseku je stejný, jako součet čísel, které v něm neleží. Výstupem jsou

index prvního a index posledního prvku v úseku (pozice čísel ve vstupní posloupnosti číslujeme od 0) a součet jeho prvků
či hodnota None, pokud takový neexistuje.

Má-li úloha více řešení, stačí nalézt jedno libovolné z nich. 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 (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říklad:
vstup: 5 2 2 6 12 11 7 10 2 5 2 8
výstup: 3 6 36

Úloha 2.

2. (10 bodů) Je zadán binární strom o n vrcholech, v nichž jsou uložena navzájem různá celá čísla, a dále celé číslo x. Navrhněte efektivní algoritmus, který vrátí seznam čísel uložených ve všech vrcholech, které leží v podstromu s kořenem obsahujícím číslo x.

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

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

(c) odvoďte časovou složitost (v nejhorším případě).

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      # číslo vrcholu
        self.levy = levy      # levé dítě 
        self.pravy = pravy    # pravé dítě

def podstrom(koren : VrcholBinStromu, x : int):
    """
    koren : kořen zadaného binárního stromu
    x     : celé čislo
    vrátí : seznam čísel uložených ve všech vrcholech, které leží v podstromu s kořenem obsahujícím číslo x
    """
Úloha 3.

3. Rozhodněte zda platí, své odpovědi vždy zdůvodněte.

(a) (5 bodů) Rozhodněte, zda platí: Pro libovolné dvě funkce f, g: N → R+ platí

f = O(g) právě tehdy, když log2 f = O( log2 g ).

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ů) V binárním vyhledávacím stromu chceme implementovat operaci odebrání prvku s danou hodnotou klíče x následovně:
Vyhledáme ve stromu vrchol v s hodnotou x (předpokládejme, že to umíme a že se x skutečně ve stromu nachází) a pak opakovaně provádíme následující kroky výpočtu:
  • je-li vrchol v listem, odebereme ho ze stromu a tím celá operace končí
  • není-li vrchol v listem, označíme symbolem s jeho jedno dítě (levé, má-li obě)
  • hodnotu z vrcholu s zkopírujeme do vrcholu v
  • symbolem v nyní označíme vrchol s .

Rozhodněte, zda výše popsaný postup korektně implementuje požadovanou operaci. Svoji odpověď zdůvodněte.
Odpovědět

Zpět na „Ostatní“