Zkouškové otázky z Algoritmů a datových struktur I

23. 5. (předtermín)

  1. Formulujte Mergesort a analyzujte jeho složitost.
  2. Definujte komponenty silné souvislosti orientovaného grafu. Popište a analyzujte algoritmus na jejich nalezení.
  3. Čtverečkovou sítí s překážkami stěhujeme gauč tvaru "L" ze tří políček. Najděte cestu na co nejméně kroků (posun o 1 políčko, případně otočení na volném čtverci 2×2 pole).
  4. Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšeme minimum z posledních K čísel.

27. 5. dopoledne

  1. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
  2. Formulujte a dokažte Kuchařkovou větu o rekurencích.
  3. Je dáno čtverečkové bludiště. Najděte cestu ze startu do cíle, která projde co nejméně zdmi.
  4. Je dána posloupnost celých čísel. Chceme najít nejdelší souvislý úsek, který obsahuje stejný počet kladných čísel jako záporných.

27. 5. odpoledne

  1. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
  2. Definujte AVL strom a popište operaci Insert.
  3. Je dán neorientovaný graf. Zjistěte, zda je bipartitní.
  4. Inverze v číselné posloupnosti x1, …, xn je taková dvojice indexů (i,j), pro kterou platí i<j a současně xi > xj. Vymyslete algoritmus, který co nejefektivněji spočte, kolik je v posloupnosti inverzí. Můžete předpokládat, že posloupnost je permutací na množině {1,…n}.

29. 5. dopoledne

  1. Popište a analyzujte algoritmus Quickselect, rozeberte vliv volby pivota na složitost.
  2. Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
  3. Je dán strom, jehož hranám jsou přiřazeny celočíselné délky. Najděte nejdelší cestu.
  4. Je dána posloupnost přirozených čísel. Spočítejte, kolik má vybraných podposloupností, jejichž součet je dělitelný 7.

29. 5. odpoledne

  1. Definujte (a,b)-strom a dokažte lemma o jeho hloubce.
  2. Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
  3. Je dána posloupnost celých čísel a číslo S. Najděte trojici (ne nutně různých) prvků posloupnosti, jejichž součet je roven S.
  4. Je dána nějaká permutace π, která propojuje n levých konců kabelů s n pravými. Chceme tuto permutaci najít pomocí co nejmenšího počtu operací "nastav i-tý levý konec na hodnotu 0 nebo 1" a "zjisti hodnotu na j-tém pravém konci".

3. 6. dopoledne

  1. Popište a analyzujte Floydův-Warshallův algoritmus na výpočet matice vzdáleností.
  2. Definujte (a,b)-strom a popište operaci Insert.
  3. Na vstupu je posloupnost znaků. Spočítejte, kolikrát se v něm vyskytuje vybraná podposloupnost KOCKA.
  4. Je dán strom, jehož vrcholy jsou ohodnocené celočíselnými cenami. Najděte co nejlevnější podmnožinu vrcholů, která protíná každou hranu.

3. 6. odpoledne

  1. Popište a analyzujte algoritmus pro hledání mostů v neorientovaných grafech.
  2. Formulujte a dokažte Kuchařkovou větu o rekurencích.
  3. Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšte medián z posledních K čísel.
  4. Je dán neorientovaný graf. Jak množinu jeho hran rozložit na hranově disjunktní cesty délky 2? (Tedy tak, aby každá hrana ležela v právě jedné cestě.) Pokud si nevíte rady s obecným grafem, zkuste to nejdřív pro strom.

5. 6. odpoledne

  1. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
  2. Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
  3. Je dána posloupnost čísel x1, …, xn a číslo s. Spočítejte, kolik existuje dvojic indexů (i,j) takových, že xi + xj = s.
  4. Je dán orientovaný graf s určeným počátečním a cílovým vrcholem, v některých vrcholech se prodává zmrzlina. Najděte sled z počátečního do koncového vrcholu, který navštíví co nejvíce různých vrcholů se zmrzlinou.

11. 6. dopoledne

  1. Popište a analyzujte algoritmus Quickselect, rozeberte vliv volby pivota na složitost.
  2. Definujte AVL strom a popište operaci Insert.
  3. Lagrangeova věta říka, že každé přirozené číslo x jde rozložit na součet čtyř čtverců (druhých mocnin celých čísel). Navrhněte algoritmus, který pro všechna x=1,…,n tyto rozklady najde.
  4. Je dán neorientovaný graf s hranami ohodnocenými čísly z množiny {1,…,5}. Najděte jeho minimální kostru.

11. 6. odpoledne

  1. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
  2. Definujte c-univerzální systém hešovacích funkcí. Ukažte, jak ho použít. Předveďte konstrukci nějakého takového systému.
  3. Uvažujme posloupnost, která je setříděná až na K prvků, které jsou zatříděny chybně (knížky v knihovně hojně navštěvované čtenáři). Navrhněte co nejefektivnější algoritmus (vzhledem k počtu prvků a K), který posloupnost dotřídí.
  4. Mějme orientovaný graf, jehož hrany jsou ohodnocené pravděpodobnostmi. Najděte nejpravděpodobnější cestu mezi dvěma vrcholy, tj. takovou, na níž je součin pravděpodobností hran největší možný.

19. 6. odpoledne

  1. Popište a analyzujte datovou strukturu Union-Find.
  2. Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
  3. Hledáme nejkratší cestu čtverečkovým bludištěm, která se vyhne strážím. Každá stráž chodí po cyklu délky nejvýše 10.
  4. Vymyslete co nejefektivnější algoritmus pro K-cestné slévání: slití K setříděných posloupností o celkové délce N. Jak se změní časová složitost Mergesortu, když budeme dělit na K částí a slévat K-cestně?

Minulé roky

Stránku spravuje Martin Mareš