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

3.házifeladatsor

1.feladat: (Exercise IV/4) Legyen T egy olyan determinisztikus gyokeres - esetleg vegtelen - fa, amelyben minden csomopontnak veges szamu gyereke van es minden csomopontnak van olyan leszarmazottja, ami level. Egy tetszoleges u csomopontbol indulva Garfield bolyongani kezd a fan ugy, hogy mindig minden gyereket azonos valoszinuseggel valaszt. Mutassa meg, hogy tetszoleges h>0-ra lehet ilyen tulajdonsagu T fat konstrualni ugy, hogy barmely nem level csomopontbol indulva Garfield legalabb 1-h valoszinuseggel orokke bolyong, anelkul, hogy egy levelhez erne.
A. Eloszor oldja meg a feladatot ugy, ha a gyerekek szama nem korlatozott.
B. Oldja meg ugy, ha a gyerekek maximalis szama legfeljebb 2, es Garfield a gyokerbol indul.
C. Hogy neznek ki a fak h=3/4-re ?
2.feladat: (Exercise IV/11) Legyen Hn a veletlen binaris keresofa magassaga.
A. Bizonyitsa be, hogy P{Hn> gamma log n} -> 0, ha n->vegtelen.
B. Bizonyitsa be, hogy minden p>0-ra E{Hn^p}/log^p n =< gamma^p + o(1).
(Segitseg B-hez: Ha Hn^p/log^p n = X, akkor EX = integral(0-vegtelenig) P{X>t} dt. Helyettesitsunk t=u^p -t, es bontsuk fel az integralt pl. a (0,gamma+h) , (gamma+h,4e) es (4e,vegtelen) szakaszokra, mindenhol maskepp becsulve, majd h->0 hataratmenet.)

Vissza az AAVE lapra

Updated: Nov 24. 1997