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