Cvičení z ADS I, letní semestr 2017/18

Petr Kučera, KTIML MFF UK

Základní informace

V pondělí 19. března 2018 bude místo mne učit kolega Majerech. Vzhledem k jeho povinnostem, které má před cvičením, je pravděpodobné, že se opozdí.

Podmínky zápočtu

Na každém cvičení zadám domácí úkol. Termín odevzdání bude vždy do začátku dalšího cvičení. K udělení zápočtu bude nutné úspěšně vyřešit alespoň 2/3 celkového počtu bodů (za každý úkol bude bod).

Domácí úkoly můžete odevzdávat dvěma způsoby:

Elektronicky e-mailem
V tomto případě napište řešení do těla mejlu, přiložte textový dokument, případně pdf. Nepřijímám skenované ručně psané úkoly.
Ručně psané řešení na papíře.
V tomto případě mi odevzdejte úkol na cvičení, nebo předejte jiným způsobem fyzicky na papíře. Opravený úkol vám dám k nahlédnutí na cvičení (nebo kdykoli jindy po dohodě), ale originál pak uschovám u sebe pro archivní účely. V tomto případě je také možné mi současně s ručně psaným řešením psaným na papíře poslat i jeho sken, pak vám opravené řešení na papíře vrátím.

Obsah cvičení

1. cvičení (19. února 2018)

  1. Implementace operací member, insert, delete, min, max, succ, pred v jednoduše vázaném seznamu a ve dvojitě vázaném seznamu.
  2. Implementace zásobníku a fronty pomocí jednoduše vázaného seznamu.
  3. Implementace zásobníku a fronty pomocí dvojitě vázaného seznamu.

Domácí úkol k 1. cvičení

K tomuto cvičení není zadán domácí úkol, neboť podmínky zápočtu byly specifikované až po prvním cvičení.

2. cvičení (26. února 2018)

  1. Zavedena asymptotická notace \(O\), \(o\), \(\Omega\), \(\omega\), \(\Theta\).
  2. K následujícím dvojicím funkcí \(f(n)\) a \(g(n)\) doplňte, jaký je mezi nimi vztah (tj. zda \(f(n)=o(g(n))\), \(f(n)=\omega(g(n))\), nebo \(f(n)=\Theta(g(n))\)).
    \(\mathbf{f(n)}\)\(\mathbf{g(n)}\)
    \(3n^2+2n-4\)\(12n^2+1000n+50\)
    \(50n^3+6n-4\)\(12n^2+1000n+50\)
    \(7n-4\)\(12n^2+1000n+50\)
    \(n\log_2 n\)\(n\sqrt{n}\)
    \(\log_2 n\)\(\ln n\)
    \((\log_2 n)^5\)\(\sqrt[5]{n}\)
    \(2^n\)\(2^{n+1}\)
    \(2^n\)\(2^2n\)
    \(e^n\)\(2^n\)
    \(2^n\)\(n!\)
    \(n^{20}\)\({1{,}01}^{n}\)
    \(n^{n/2}\)\(2^{n\log_2 n}\)
    \(n^{\log_2 n}\)\(2^{(\log_2 n)^2}\)
  3. Napište pseudokód algoritmu třídění vkládáním („insertion sort“) a zdůvodněte jeho složitost v nejhorším případě (zdola i shora).

Domácí úkol k 2. cvičení

Popište algoritmus binárního vyhledávání v setříděném poli (napište jeho pseudokód), odhadněte a zdůvodněte shora i zdola jeho složitost v nejhorším případě.

3. cvičení (5. března 2018)

  1. Popište co nejefektivnější algoritmus, který v zadané matici s \(n\) sloupci a \(m\) řádky nalezne maximální souvislou nulovou podmatici (tedy nulovou podmatici s co největší plochou).
    1. Triviální řešení vede na čas \(O(n^2m^2)\) (to, které jsme zmiňovali na cvičení, ve skutečnosti vede na čas \(O(n^3m^3)\), ale lze jednoduše upravit na kvadratický čas).
    2. Pro každý prvek v matici si můžeme předpočítat, kolik je napravo něj nul — výpočet tohoto počtu pro všechny prvky v matici lze provést v čase \(O(nm)\).
    3. S využitím této informace můžeme popsat algoritmus, který pracuje v čase \(O(nm^2)\). Vzhledem k symetrii tak dostaneme algoritmus, který pracuje v čase \(O(nm\cdot\min(n, m))\).
    4. Dále můžeme uvážit, že každá maximální nulová podmatice je zleva, zprava, shora i zdola ohraničena nenulovým prvkem. Pokud si ke každému prvku předpočítáme počty nul nad a pod tímto prvkem, můžeme toho využít ke konstrukci algoritmu, který pracuje v čase \(O(nm)\).
  2. Na vstupu očekáváme čísla v trojúhelníku následujícího tvaru:
       3
      7 4
     2 4 6
    8 5 9 3
          
    Cílem je najít cestu v trojúhelníku od jeho vrcholu k podstavě po číslech s největším součtem. Cesta má postupovat vždy jen dolů, přičemž na následující řádce vybíráme pokračování ze dvou sousedních číslic (po úhlopříčce, např. 7 má dole sousedy 2 a 4). V uvedeném trojúhelníku je takovou cestou posloupnost 3+7+4+9=23, což je největší součet, jehož lze dosáhnout. Vaším úkolem je popsat algoritmus, který takovou cestu najde pro daný trojúhelník v co nejrychlejším čase (ideálně lineárně v počtu čísel v trojúhelníku).
  3. Chceme implementovat asociativní pole s použitím přímého adresování ve velkém poli \(A\). Na začátku není pole \(A\) nijak inicializované a může tedy obsahovat cokoli. Inicializaci na začátku nemůžeme vzhledem k jeho velikosti provést, trvala by moc dlouho. Popište, jak implementovat přímo adresované asociativní pole v \(A\). Každý uložený objekt by měl zabrat paměť velikosti \(O(1)\). Operace vyhledávání, vložení i vymazání prvku by měla zabrat konstantní čas, stejně jako inicializace.

Domácí úkol k 3. cvičení

Napište pseudokód algoritmu pro dělení (na papíře, který znáte ze školy). Vstupem jsou čísla \(A\), \(B\) daná jako pole číslic (můžete si vybrat, zda půjde o čísla ve dvojkové nebo desítkové soustavě). Výstupem pak má být dvojice čísel \(Q\) a \(R\), kde \(Q\) je celočíselný podíl čísel \(A\) a \(B\) je zbytek po celočíselném dělení (tj. \(A=QB+R\) a \(R\lt B\)). Můžete předpokládat, že další aritmetické operace, jako sčítání, odčítání, násobení a porovnávání máte k dispozici. Jaká je složitost vašeho algoritmu v závislosti na počtu číslic v číslech \(A\) a \(B\)?

4. cvičení (12. března 2018)

  1. Reprezentace grafu:
    • Matice sousednosti \(A\). Význam \(A^k, k=1, \ldots, n\).
    • Seznam sousedů
    • Seznam hran
    • Matice incidence \(I\). Význam \(I^{T}I\) a \(I{I}^T\).
  2. Prohledávání grafu do šířky.
  3. Test toho, zda je graf bipartitní.
  4. Je dán neorientovaný graf \(G=(V, E)\), popište algoritmus, který (v lineárním čase), určí posloupnost vrcholů (vrcholy se opakují), v kterém je potřeba vrcholy projít tak, abychom použili každou hranu právě dvakrát, jednou v každém směru. Čistící vůz má za úkol vyčistit všechny silnice ve městě, každou silnici mezi dvěma křižovatkami musí projet jednou v každém směru, ale z úsporných důvodů by neměl jezdit po již vyčištěném kusu silnice.

Domácí úkol k 4. cvičení

Popište algoritmus, který pro orientovaný graf \(G=(V, E)\) zadaný pomocí matice sousednosti zjistí, zda v něm existuje vrchol \(v\in V\), který má výstupní stupeň nulový a vstupní stupeň roven \(|V|-1\), jde tedy o univerzální stok. Algoritmus by měl pracovat v čase \(O(|V|\).

5. cvičení (19. března 2018)

V pondělí 19. března 2018 bude místo mne učit kolega Majerech. Vzhledem k jeho povinnostem, které má před cvičením, je pravděpodobné, že se opozdí.

6. cvičení (26. března 2018)

  1. Ukázka DFS na příkladu orientovaného grafu, probrána klasifikace hran
  2. Je dán orientovaný acyklický graf \(G=(V, E)\) a vrchol \(s\in V\). Popište algoritmus, která určí v lineárním čase pro každý vrchol \(v\in V\) hodnotu \(D(v)\), která je rovna délce nejdelší cesty z vrcholu \(s\) do vrcholu \(v\).
  3. Je dán orientovaný graf \(G=(V, E)\) a vrcholy \(s, t\in V\). Popište algoritmus, který v lineárním čase určí počet různých nejkratších cest z vrcholu \(s\) do vrcholu \(t\).
  4. Popište algoritmus pro konstrukci seznamu sousedů transponovaného grafu \(G^T\), je-li dán seznam sousedů orientovaného grafu \(G\).
  5. Ukázka běhu algoritmu pro konstrukci SSK na příkladu.

Domácí úkol k 6. cvičení

Řekneme, že orientovaný graf \(G=(V, E)\) je polosouvislý, pokud pro každé dva vrcholy \(u, v\in V\) platí, že existuje cesta z \(u\) do \(v\) nebo cesta z \(v\) do \(u\). Popište algoritmus, který v lineárním čase (\(O(|V|+|E|)\)) otestuje, zda je daný graf \(G\) polosouvislý.

7. cvičení (9. dubna 2018)

  1. Ukažte graf se zápornými vahami, ale bez záporných cyklů, na němž Dijkstrův algoritmus selže.
  2. Rozmyslete si, proč se nelze negativních hran v \(G\) zbavit přičtením dostatečně elké konstanty ke všem vahám hran.
  3. Předpokládejme, že v grafu \(G=(V, E)\) jsou nezáporné váhy přidělené jak hranám, tak vrcholům. Popište způsob, který umožní hledat nejkratší cesty v takto ohodnoceném grafu.
  4. Uvažme orientovaný graf \(G=(V, E)\), kde každá hrana má přiřazenou nezápornou váhu, jež reprezentuje její propustnost \(h(u, v)\). Například může jít o situaci, kdy hrany reprezentují silnice a váha hrany pak minimální světlou výšku mostu, který silnici překlenuje. Pro danou cestu \(P\) definujeme její propustnost jako minimální propustnost hrany na této cestě. Popište efektivní algoritmus, který pro daný vrchol \(s\in V\) určí maximální propustnost cesty z \(s\) do každého vrcholu v grafu \(G\).
  5. Nechť \(G=(V, E)\) je vážený orientovaný graf s nezápornou váhovou funkcí \(w: E\to\{0, \ldots, k\}\), kde \(k\) je celé kladné číslo (ne moc velké). Upravte Dijkstrův algoritmus tak, aby ze zadaného vrcholu \(s\) nalezl nejkratší cesty v čase \(\Theta(k|V|+|E|)\).
  6. Popište jednoduchou úpravu Dijkstrova algoritmu, která nám umožní zrekonstruovat nejkratší cesty z daného počátečního vrcholu \(s\) (tj. ne jen jejich délky).
  7. Pokud je v grafu \(G=(V, E)\) z daného vrcholu \(s\) dosažitelný záporný cyklus, pak tuto situaci v Bellman-Fordově algoritmu můžeme detekovat. Jak v tom případě nalezneme nějaký konkrétní záporný cyklus?

Domácí úkol k 7. cvičení

Máme orientovaný graf \(G=(V, E)\) v němž je s každou hranou \((u, v)\in E\) asociované reálné číslo \(r(u, v)\), pro něž platí \(0\leq r(u, v)\leq 1\). Tato hodnota reprezentuje spolehlivost komunikačního kanálu z vrcholu \(u\) do vrcholu \(v\), kterou interpretujeme jako pravděpodobnost toho, že tímto kanálem dojde k úspěšnému přenosu signálu z \(u\) do \(v\). Předpokládáme, že tyto pravděpodobnosti jsou nezávislé. Popište efektivní algoritmus, který pro dva zadané vrcholy \(s\) a \(t\) nalezne nejspolehlivější spojení z \(s\) do \(t\).

8. cvičení (16. dubna 2018)

  1. Nechť \(G=(V, E)\) je orientovaný graf. Tranzitivní uzávěr grafu \(G\) definujeme jako orientovaný graf \(G^+=(V, E^+)\), kde \((u, v)\in E^+\), právě když v grafu \(G\) existuje cesta z \(u\) do \(v\). Graf \(G^-=(V, E^-)\) je tranzitivní redukcí grafu \(G\), pokud \((G^-)^+=G^+\) a počet hran v \(E^-\) je minimální možný. Popište efektivní algoritmus, který ke grafu \(G\) zkonstruuje nějakou jeho tranzitivní redukci.
  2. Floydův-Warshallův algoritmus pro hledání cest mezi všemi dvojicemi vrcholů.
  3. Jak efektivně nalézt nejkratší cyklus v grafu?
  4. Uvažme neorientovaný graf \(G=(V, E)\) s váhami hran určenými funkcí \(w:E\to {\mathcal R}\) a jeho minimální kostru \(T=(V, E_T)\).
    1. Nechť \(\{u, v\}\in E_T\) je hrana a položme \(w'\) nové váhy, které se od \(w\) liší jen tím, že váha hrany \(\{u, v\}\) je snížena. Ukažte, že \(T\) je minimální kostrou i pro upravené váhy.
    2. Nechť \(\{u, v\}\in E\setminus E_T\) je hrana a položme \(w'\) nové váhy, které se od \(w\) liší jen tím, že váha hrany \(\{u, v\}\) je snížena. Ukažte, jak z \(T\) získat minimální kostru pro upravené váhy.
    3. Ke grafu \(G\) přidáme vrchol \(v\) a připojíme jej váženými hranami k některým vrcholům v \(V\). Popište, jak upravit \(T\) na minimální kostru nového grafu.
  5. Uvažme neorientovaný graf \(G=(V, E)\) s váhami hran určenými funkcí \(w:E\to{\mathcal R}\).
    1. Rozmyslete si, že pokud je hrana \(\{u, v\}\in E\) nejtěžší hranou nějakého cyklu v \(G\), pak tato hrana není v žádné minimální kostře. (Kromě případu, kdy jsou všechny ostatní hrany v cyklech s \(\{u, v\}\) stejně těžké, i pak ale platí, že existuje kostra, která \(\{u, v\}\) neobsahuje.).
    2. Ukažte, že následující algoritmus určí nejmenší kostru grafu \(G\) a popište jeho efektivní implementaci.
      1. Setřiď hrany sestupně podle vah.
      2. Pro každou hranu \(\{u, v\}\) v pořadí sestupně dle vah postupně proveď následující krok: Pokud je hrana součástí cyklu, odstraň ji.
  6. Ukažte, že druhá nejmenší kostra není nutně jednoznačně určena ani v případě, že váhy hran jsou po dvou různé.

Domácí úkol k 8. cvičení

Je dán graf $G=(V,E)$ s váhami na hranách a množina vrcholů $S\subseteq V$, popište algoritmus, který najde minimální kostru grafu $G$, v níž jsou vrcholy z $S$ listy (pokud je to možné).