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


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

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
    aantos NOSPAMkukacNOSPAM gmail pont com