Zkouškové otázky z Algoritmů a datových struktur I
Otázky An se týkají přednesené látky, Bn jsou příklady k vymyšlení, C je nepovinná úloha jen tak pro radost.
20. 5. odpoledne
- A1. Algoritmus na násobení čísel metodou Rozděl a panuj.
- A2. Jarníkův algoritmus na hledání nejmenší kostry.
- B1. Navrhněte dynamickou strukturu pro reprezentaci prvků množiny, která bude umět přidat prvek, smazat prvek a zjistit medián.
- B2. 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í.
- C. Je dána posloupnost čísel v rozsahu 1 až 1000. Nalezněte v ní co nejdelší souvislý úsek, v němž jsou všechna čísla různá.
27. 5. odpoledne
- A1. AVL stromy: definice, hloubka, Insert nebo Delete.
- A2. Topologické uspořádání: definice, algoritmus.
- B1. Je dána množina prvků. Najděte první až n1/2-tý nejmenší prvek.
- B2. 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.
- C. Vymyslete co nejefektivnější algoritmus pro inverzi trojúhelníkové matice. (Nápověda: Rozděl a panuj.)
8. 6. dopoledne
- A1. Strassenův algoritmus a jeho aplikace na dosažitelnost v grafech.
- A2. Dijkstrův algoritmus.
- B1. Navrhněte datovou strukturu pro reprezentaci množiny, která umí efektivně operace Insert, Delete, Rank (kolikátý nejmenší je daný prvek?) a UnRank (vrať k-tý nejmenší prvek).
- B2. Vymyslete algoritmus, který v neorientovaném souvislém grafu se sudými stupni najde eulerovský tah.
- C. Navrhněte datovou strukturu, která bude reprezentovat posloupnost levých a pravých závorek s operacemi Insert (vloží na danou pozici danou závorku), Delete (smaže závorku na dané pozici) a Good (vrátí, zda je posloupnost dobře uzávorkovaná).
8. 6. odpoledne
- A1. Algoritmus na násobení čísel.
- A2. (a,b)-stromy: definice, důkaz logaritmické hloubky, Insert a Delete.
- B1. Mějme neorientovaný graf, chceme najít všechny jeho artikulace (tak říkáme vrcholu, jehož odstraněním se zvýší počet komponent souvislosti).
- B2. Vymyslete algoritmus pro třídění množiny řetězců v čase lineárním se součtem jejich délek.
15. 6. dopoledne
- A1. Komponenty silné souvislosti: definice a algoritmus pro jejich nalezení.
- A2. AVL stromy: definice, důkaz logaritmické hloubky.
- B1. Vymyslete algoritmus, který pro dva řetězce spočítá jejich překlepovou (editační) vzdálenost. To je minimální počet operací (vložení znaku, smazání znaku, změna znaku na jiný), kterými lze z jednoho řetězce vyrobit druhý.
- B2. Je dán souvislý neorientovaný graf. Nalezněte pořadí, v jakém můžeme mazat vrcholy tak, abychom postupně smazali všechny a graf byl v průběhu mazání stále souvislý.
- C. Vyřešte rekurenci T(n) = n1/2 T(n1/2) + Θ(n), T(1)=1.
15. 6. odpoledne
- A1. Lineární algoritmus na hledání k-tého nejmenšího prvku.
- A2. Universální hashování: definice, použití, příklad universálního systému.
- B1. Navrhněte datovou strukturu pro udržování neorientovaného grafu s ohodnocenými hranami, která bude umět operace Insert(u,v,váha) (vložení hrany uv) a Min(v) (nalezení nejlevnější hrany v komponentě souvislosti obsahující vrchol v).
- B2. Mějme dva roboty v bludišti s jedním východem. Pošleme-li robotům příkaz (jdi na sever/jih/východ/západ), provedou ho oba roboti; pokud by robot narazil do zdi, příkaz ignoruje. Sestrojte nejkratší možnou posloupnost příkazů, která oba roboty dostane z bludiště ven. (Jakmile robot opustí bludiště, je odchycen a už se do něj nevrátí.)
- C. stejná jako dopoledne
23. 6. dopoledne
- A1. Prohledávání do hloubky, klasifikace hran, detekce cyklů.
- A2. Věta o dolním odhadu složitosti třídění.
- B1. Mějme n šroubů a n matiček. Ke každému šroubu patří právě jedna matička a opačně. Chceme spárovat šrouby a matičky pomocí co nejmenšího počtu pokusů. Při každém pokusu zkusíme zašroubovat šroub do matičky a dozvíme se jeden ze tří možných výsledků: pasuje, šroub moc velký, šroub moc malý.
- B2. Je dán text rozdělený na slova, vypište frekvence všech slov, která se v něm vyskytují, setříděné od nejčetnějšího slova od nejméně četné.
- C. Sčítání čísel ve Fibonacciho soustavě.
23. 6. odpoledne
- A1. Kuchařková věta o řešení rekurencí.
- A2. Kruskalův algoritmus na hledání nejmenší kostry.
- B1. Mějme n lamp a n vypínačů. Každé světlo je ovládáno právě jedním vypínačem a opačně. Chceme zjistit přiřazení světel vypínačům pomocí co nejmenšího počtu následujících operací: zapni vypínač, vypni vypínač, zjisti, jestli světlo svítí.
- B2. Je dán text, chceme ho optimálním způsobem zalámat do odstavce. Známe délku každého slova, šířku S standardní mezery mezi slovy, šířku stránky W. Všechny řádky kromě posledního mají být roztažené na plnou šířku papíru, čehož docílíme roztažením mezer mezi slovy na šířku αS (α≥1). Takovému řádku pak přiřadíme míru ošklivosti α2-1. Nalezněte takové rozlámání textu na řádky, které bude minimalizovat celkovou ošklivost (součet ošklivostí řádků).
- C. Vymyslete datovou strukturu pro semipersistentní reprezentaci množiny. To je taková, která umí bězné operace Insert a Delete, ale hledat umí nejen v současném stavu množiny, nýbrž i v libovolném stavu v minulosti.
28. 6. dopoledne
- A1. Topologické uspořádání: definice, věta o existenci, algoritmus.
- A2. Deterministický lineární algoritmus na nalezení k-tého nejmenšího prvku.
- B1. 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í.
- B2. Mějme neorientovaný graf ohodnocený čísly z {1,2,3}. Jak najít jeho minimální kostru?
- C. Uvažujme šifrovací (a k němu příslušný dešifrovací) algoritmus s klíčem délky K. Algoritmus někdo použil dvakrát (se dvěma různými klíči). Známe originální a zašifrovanou zprávu, chceme zjistit dvojici klíčů. Ukažte, že na to stačí O(2K) kroků.
28. 6. odpoledne
- A1. Jarníkův algoritmus a řezové lemma.
- A2. Třídění n čísel z množiny {1, …, n4}.
- B1. Byla jednou jedna směnárna, která obchodovala s N měnami podle matice kursů K (Ki,j říká, kolik jednotek měny j získáme za jednotku měny i). Lze na směňování vydělat? (Tedy lze začít s jednotkou nějaké měny a skončit s větším částkou v téže měně?)
- B2. Jak setřídit posloupnost, víme-li, že každý prvek se nachází ve vzdálenosti nejvýše K od své správné polohy? (K je mnohem menší než počet prvků.)
- C. Najděte dvě funkce f, g takové, že neplatí ani f=O(g), ani g=O(f).
20. 9. dopoledne
- A1. Jarníkův algoritmus (s haldou) a řezové lemma.
- A2. Universální hashování: definice a příklad c-universálního systému.
- B1. Nejrychlejší cesta mezi dvěma políčky ve čtverečkovém bludišti. Přesun na volné políčko trvá 1, prokopání zdi trvá K.
- B2. Je dána posloupnost čísel a číslo K. Spočítejte maximum z mediánů úseků délky K.
- C. 2D verze předchozí úlohy: je dána matice a rozměry podmatice. Jaký je největší z mediánů podmatic zadané velikosti.
20. 9. odpoledne
- A1. (a,b)-stromy: definice, důkaz logaritmické hloubky, Insert.
- A2. Dijkstrův algoritmus s haldou.
- B1. Je dána po částech lineární funkce, najděte hodnotu, které tato funkce nabývá nejčastěji.
- B2. Mějme graf ohodnocený kladnými čísly s počátečním a koncovým vrcholem. Najděte tu z nejkratších cest mezi těmito vrcholy, která obsahuje největší možný počet hran.
- C. stejná jako dopoledne