Budapesti Mûszaki Egyetem, Budapest
Számítástudományi és Információelméleti Tanszék


Algorimusok és adatstruktúrák valószínûségi elemzése

1.házifeladatsor


Beadási határidõ: október 9. csütörtök !

1.feladat
(Exercise 3) Vegyünk egy véletlen bináris keresõfát n csomóponttal. Legyen Z_i az i globális rangú (i. legnagyobb) elem mélysége.
  • Adjon pontos kifejezést E{Z_1}-re
  • Adjon pontos kifejezést E{Z_i}-re minden 1<=i<=n-re.
  • Hogyan függ E{Z_i} n-tõl, ha i~gyök{n} ?
  • 2.feladat
    (Exercise 6) DIREKT DOMINANCIA GRÁF. Legyenek X_1,...,X_n független, az egységnégyzeten egyenletes eloszlású pontok. A dominancia gráfot úgy konstruáljuk, hogy (X_i,X_j) pontosan akkor él, ha abban a koordinátatengelyekkel párhuzamos állású téglalapban, melynek X_i és X_j szemközti csúcsai, nincs másik a pontok közül. Legyen E_n a dominancia gráf éleinek száma. Adjon elsõrendû aszimptotikus becslést E{E_n}-re.

    3.feladat
    (Exercise 7) UNIÓ-HOLVAN SZÜLÕMUTATÓS FÁK. Egy véletlen unió-holvan szülõmutatós fa a következõképpen áll elõ. Kiindulunk n darab egy pontú fából, ahol a pontok 1-tõl n-ig sorszámozottak. Egy tipikus lépésben veszünk két egyenletesen választott véletlen pontot és az õket tartalmazó fákat - ha azok különbözõk - összefûzzük, azaz az elsõ fa gyökere a második gyökerének a gyereke lesz. n-1 összefûzés után egy n pontú fát kapunk.
  • Mennyi a végsõ gyökér várható fokszáma ?
  • Mennyi a várható távolság az 1-es pont és a gyökér között ?
  • A T_1 és a T_2 fa összefûzésének ideje: 1 plusz a T_1-bõl választott pont távolsága a gyökerétõl plusz a T_2-bõl választott pont távolsága a gyökerétõl. Az utóbbi két komponens reprezentálja azt az idõt, amely annak meghatározásához kell, hogy egy véletlenül választott pont melyik fában van. Mutassa meg, hogy a teljes faépítés várható ideje O(n).
  • Vissza az AAVE lapra


    Updated: Nov 24. 1997
    aantos NOSPAMkukacNOSPAM gmail pont com