24. 6. 2014 - Čepek

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Uživatelský avatar
CiTrus
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 22. 6. 2014 14:05
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

24. 6. 2014 - Čepek

Příspěvek od CiTrus »

Dnes bylo zadání celkem nezvyklé:
  1. Dokažte nebo vyvraťte tvrzení: Každý binární strom je možné převést na řetězec (tj. strom takový, že každý vrchol má nejvýše jednoho syna) pomocí O(n) rotací z operací insert a delete v červenočerném stromě, kde n je počet vrcholů stromu.
  2. Mějme hashovací funkci h(x): U\rightarrow \{0,1,\dots m-1\}, kde m je velikost hashovací tabulky a mocnina dvojky. Tabulka používá otevřené adresování pomocí níže uvedeného algoritmu.

    Kód: Vybrat vše

    (1) i := h(x)  // x je hledany klic
        j := 0
    (2) otestujeme pozici i v tabulce
        - pokud na ni je x -> koncime (success)
        - pokud na ni neni x a otestovali jsme m pozic -> koncime (fail)
        - jinak -> pokracujeme na dalsi krok
    (3) j := j + 1 (mod m)
        i := i + j (mod m)
        jump (2)
    
    Určete, o jaký druh otevřeného adresování se jedná. Dokažte, že algoritmus otestuje všechna políčka tabulky dříve, než otestuje jednu pozici podruhé. Důkaz proveďte dopočítáním konstant.
  3. Je dána ohodnocená silniční síť, kde váha každé silnice reprezentuje maximální výšku vozidla, které touto silnicí může projet. Rádi bychom ze startovního města S do každého města na mapě dopravili velkoobjemný náklad. Napište co nejrychlejší algoritmus, kterým zjistíme pro každé město největší výšku vozidla, kterým se tam dostaneme.
U ústní části jsem dostal Kruskala/Borůvku, spolužák vedle měl Dijkstru.

SPOILER ALERT: níže následují hinty k písemce!
  1. Tvrzení platí. V libovolném stromu se můžeme ponořit do minima a rotovat doleva, dokud má nějakého pravého syna. Jakmile pravý syn dojde, vyšplháme se do otce a celý postup opakujeme. Jakmile dojdeme až do kořene stromu, máme řetězec. Je tedy jen zapotřebí dokázat, že tento postup provede O(n) rotací. To ale přímo vyplývá z toho, že jakmile vrchol zrotujeme, už nám nikdy nebude překážet - máme n vrcholů, proto O(n).
  2. Pokud si proměnnou i rozepíšeme jako posloupnost jejích hodnot v jednotlivých iteracích, dostaneme h(x), h(x)+1, h(x)+1+2, h(x)+1+2+3, ... h(x)+aritmetická řada. Součet aritmetické řady je \frac{n}{2}(1+n), což je O(n^2) - proto je druhem otevřeného adresování kvadratické zkoušení (quadratic probing). Důkaz, že se tato strategie nezacyklí před prozkoumáním všech položek tabulky, je hodně ošklivý. Já se ve svém řešení odkázal na přednášku, kde to bylo dokázáno, a pak jsem to pro jistotu doplnil o stručné vyjádření myšlenky důkazu (zabralo půl strany). Zkoušející ale na to jen kouknul, zkontroloval slovo "kvadratický" a hodnoty konstant a vzal to bez větších problémů.
  3. Úlohu lze vyřešit jednoduchou modifikací Dijkstrova algoritmu. Inicializujeme výšky: d(S)=\infty,d(*)=0, v prioritní frontě otočíme pořadí na sestupné a relax hrany (u,v) vypadá takto: d(v)=\max\{d(v),\min\{d(u),\delta(u,v)\}\}, kde d(x) je počítaná výška a \delta(x,y) je váha hrany (silnice). Takto pozměněný algoritmus má úplně stejné vlastnosti jako původní Dijkstra (složitost, konečnost). Správnost vyplývá z toho, že prioritní fronta je maximová, takže před uzavřením vrcholu určitě projdeme všechny ostatní vrcholy, které by mohly jeho výšku ovlivnit. Maximum v relaxu používáme, protože chceme výšku jen vylepšovat. Minimum uvnitř relaxu reprezentuje cestu s-u-v, na které nás zajímá nejmenší výška hrany, protože ta omezuje projíždějící auta.
Návštěvník

Re: 24. 6. 2014 - Čepek

Příspěvek od Návštěvník »

Souhlasím s výše uvedeným, akorát v příkladě 2 za nedůkaz toho, že se nezacyklí, strhával 1/2b. U ústní - konstrukce universální množiny a Floyd-Warshall.
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“