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

6.házifeladatsor

Beadási határidõ: december 11. csütörtök !

1.feladat

(Exercise V/3) Vegyunk egy veletlen 0-1 fat. Tudjuk, hogy a p>1/2 esetben az n. szinten levo optimalis csomopont ertekere, Cn*-ra

lim_{n->vegtelen} P{Cn* >= hn} = 1

valamilyen h-ra. Ezt felhasznalva adjon bizonyitast arra, hogyha N a sucker kereses altal "kiterjesztett" csomopontok szama az n. szintig, akkor

EN >= 2^{dn}

valamilyen d-re.

2.feladat

(Exercise V/5) Vegyunk egy veletlen 0-1 fat p>1/2-del. Adja meg a pontos kifejezest EN-re, azaz a 0 vagy 1 erteku csomopontok varhato szamara.

3.feladat

(Exercise IX/1) Tegyuk fel, hogy Gnp-ben pn^2=o(gyok{n}). Mutassuk meg, hogy 1-hez tarto valoszinuseggel nincs olyan komponens, aminek 3 vagy tobb pontja lenne.

4.feladat

(Exercise IX/2.C) Vegyunk egy Gnp veletlen grafot o(n) varhato elszammal. Mutassuk meg, hogy 0-hoz tart annak a valoszinusege, hogy Gnp-ben van kor.

Vissza az AAVE lapra

Updated: Dec 1. 1997