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

4. 6. (předtermín)

1. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
2. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
3. Je dán neorientovaný graf s hranami ohodnocenými čísly z množiny {1,…,L} pro pevné, malé L. Najděte jeho minimální kostru.
4. Sestrojte vyhledávací strom, který bude navíc umět operaci Rank(x,y), která v logaritmickém čase spočte, kolik hodnot ve stromu leží v intervalu [x,y].

10. 6. dopoledne

1. Definujte AVL strom a dokažte, že má logaritmickou hloubku.
2. Komponenty silné souvislosti: definice, algoritmus na jejich hledání
3. Je dán neorientovaný graf, otestujte, zda je bipartitní.
4. Kdesi v bludišti se nachází robot. Vysíláme posloupnost příkazů (každý příkaz je nějaký pohyb o jedno políčko na sever/jih/východ/západ) pořád dokola, než robot vyleze z bludiště (pokud robot nemůže příkaz provést, protože by narazil do zdi, ignoruje ho). Zjistěte, zda pro danou mapu bludiště a danou posloupnost příkazů platí, že ať robot na počátku stojí kdekoliv, vždy je vysvobozen.

10. 6. odpoledne

1. Prohledávání do hloubky a klasifikace hran.
2. AVL stromy: definice, operace Insert (s celým rozborem případů).
3. Je dán strom, jehož hranám jsou přiřazeny celočíselné délky. Najděte nejdelší cestu.
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.

15. 6. dopoledne

1. Minimální kostra: definice a libovolný efektivní algoritmus.
2. Kuchařková věta o řešení rekurencí.
3. Je dána posloupnost celých čísel x₁, …, x_n a číslo A. Spočítejte, kolik existuje dvojic indexů (i,j) takových, že x_i + x_j = A.
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ý.

15. 6. odpoledne

1. Hledání k-tého nejmenšího prvku.
2. Dijkstrův algoritmus.
3. Vymyslete datovou strukturu pro hledání rýmů. Vybudujeme ji pro množinu slov. Pak chodí dotazy: pro zadané slovo najděte nejlepší rým (shodující se v co nejvíce písmenech od konce) různý od zadaného slova.
4. Mějme bludiště ve tvaru čtvercové sítě, jejíž políčka obsahují místnosti, zdi, klíče K₁ až K_k a odpovídající zamčené dveře D₁ až D_k. Dveřmi D_i je možno projít, pokud jste předtím alespoň jednou navštívili políčko s klíčem K_i. Vymyslete algoritmus, který najde (ne nutně nejkratší) cestu ven z bludiště.

17. 6. dopoledne

1. Hešování: princip hešovaní s přihrádkami, definice c-univerzálního systému funkcí a jeho použití, důkaz existence c-univerzálního systému.
2. Dijkstrův algoritmus.
3. Je dána posloupnost celých čísel. Úsek je vyvážený, pokud se v něm vyskytuje stejný počet kladných hodnot, jako záporných. Najděte co nejdelší vyvážený úsek.
4. Mějme šachovnici 3×N poliček. Spočítejte, kolika způsoby se dá vydláždit kostkami 1×2 políčka (rozmístit kostky tak, aby šachovnici vyplnily bez děr a překryvů; kostky jde otáčet).

17. 6. odpoledne

1. Algoritmus pro hledání mostů v neorientovaných grafech.
2. Definujte (a,b)-stromy, popište operaci Delete a rozeberte její složitost.
3. Vymyslete algoritmus pro třídění množiny řetězců v čase lineárním se součtem jejich délek.
4. 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.

24. 6. dopoledne

1. Definujte AVL strom. Vyslovte a dokažte větu o jeho hloubce.
2. Definujte komponenty silné souvislosti a popište algoritmus na jejich nalezení v lineárním čase.
3. Je dána posloupnost slov ze znaků anglické abecedy. Slova setřiďte podle toho, kolikrát se v poslopnosti vyskytují. Složitost analyzujte vzhledem k celkovému počtu znaků vstupu.
4. 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í.

24. 6. odpoledne

1. Vyslovte Bellmanův-Fordův algoritmus na hledání nejkratší cesty a rozeberte jeho správnost a časovou složitost.
2. Vyslovte a dokažte kuchařkovou větu o řešení rekurencí.
3. Vybudujte pro danou posloupnost celých čísel datovou strukturu, která umí rychle odpovídat na otázky „je úsek od i-tého do j-tého prvku rostoucí?“.
4. Je dán slovník. Sestrojte co nejdelší slovní žebřík. To je posloupnost slov ze slovníku taková, že (i+1)-ní slovo získáme z i-tého smazáním jednoho písmene. Například pro anglický slovník AGID-4 vychází žebřík glassiness, glassines, glassine, glassie, lassie, lassi, lass, ass, as, a.

2. 7. dopoledne

1. Definujte topologické uspořádání a ukažte, jak ho najít v lineárním čase.
2. Definujte AVL strom a popište jeho operaci Insert.
3. Labyrint má tvar čtvercové sítě, některá políčka jsou zdi. Archeolog se chce dostat z políčka A na políčko B. Projít na volné políčko mu trvá 1 minutu, prokopat se na políčko se zdí 20 minut. Najděte nejrychlejší cestu.
4. Inverze v číselné posloupnosti x₁, …, x_n je taková dvojice indexů (i,j), pro kterou platí i<j a současně x_i > x_j. 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}.

2. 7. odpoledne

1. Popište algoritmus prohledávání grafu do hloubky a klasifikaci hran v DFS stromu.
2. Vyslovte a dokažte kuchařkovou větu o řešení rekurencí.
3. Je dána posloupnost celých čísel x₁, …, x_n a číslo A. Spočítejte, kolik existuje dvojic indexů (i,j) takových, že x_i + x_j = A.
4. Chceme spočítat součin matic A₁, … A_n. Jelikož násobení matic je asociativní, můžeme posloupnost libovolně uzávorkovat. Chceme najít takové uzávorkování, při němž násobením strávíme co nejméně času. Předpokládáme, že vynásobit matici tvaru R×S maticí tvaru S×T trvá čas R*S*T. (Nápověda: představte si uzávorkování jako strom.)

8. 7. dopoledne

1. Definujte časovou a prostorovou složitost algoritmu.
2. Definujte komponenty silné souvislosti a popište algoritmus na jejich nalezení v lineárním čase.
3. Je dána posloupnost celých čísel a číslo X. Najděte úsek posloupnosti (souvislou podposloupnost), jehož součet je roven X.
4. Nalezněte v zadaném stromu největší párování: to je podmnožina hran taková, že žádné dvě hrany nemají společný vrchol.

8. 7. odpoledne

1. Červeno-černý strom: definice, důkaz logritmické hloubky.
2. Dijkstrův algoritmus: formulace a analýza.
3. Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy chceme vypsat 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.

15. 7.

1. Definujte c-univerzální systém funkcí a ukažte, jak ho použít při hešování.
2. Vyslovte Jarníkův algoritmus pro hledání minimální kostry, rozeberte jeho správnost a časovou složitost.
3. Je dána posloupnost celých čísel. Najděte co nejdelší úsek (souvislou podposloupnost), jehož součet je dělitelný 7.
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

• 2015
• 2013
• 2011
• 2009