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

2.házifeladatsor

Beadási határidõ: október 20. hétfõ !

1.feladat

(Exercise 1) Ismételje meg a legközelebbi pár problémát R^d-ben. Azaz, gondolja át hány eltolt négyzetháló kell, hogy kell delta-t választani, hogy kell a cellákat definiálni és hogyan kell a cellákat továbbosztani, hogy a bizonyítás mûködjön. Adja meg az ``1875'' és a ``900'' helyén álló konstansokat.

2.feladat

(Exercise 2) Tekintsük az n alatt a 2 db (i,j) indexpár halmazát, ahol 1<=i < j<=n. Ebbõl egy n elemû véletlen minta (visszatevés nélküli) kiválasztására tekintsük a következõ algoritmust:

[set-up]
define n empty linked lists L(i), 1<=i<=n
[algorithm]
repeat

generate (i,j) uniformly at random from {1,...,n}x{1,...,n}
if i>j then interchange i and j
if i<>j and j is not in L(i) then
insert j in linked list L(i)
N <- N+1
output (i,j)
until N=n

Egy véletlen pár generálása konstans idõt, azonban a listába való beszúrás a lista hosszával arányos idõt vesz igénybe. Mutassa meg, hogy az fenti algoritmus várható ideje O(n).

3.feladat

(Exercise 3) Tekintsük a bináris térpartició problémát. Adott n nemmetszõ szakasz. A szakaszok sorrendje véletlenszerû. Egy fát konstruálunk a következõképpen: az elsõ területet (a síkot, ami a gyökérnek felel meg) négy részre osztjuk az elsõ szakasz végpontjain áthaladó függõleges egyenesek és maga a szakasz által. Minden sorrakerülõ területet újra négy (esetleg csak három vagy kettõ) részre osztunk a területet metszõ elsõ szakasz végpontjain áthaladó függõleges egyenesek és maga a szakasz által. A jegyzetbeli példa mutatja a keletkezõ particiót és a hozzátartozó fát. Az egyes csomópontoknak lehet kettõ, három vagy négy gyerekük. Vezessen le egy felsõ korlátot a fa belsõ (nem levél) csomópontjainak a számára - a BSP fákra vonatkozó bizonyítás mintájára.

Vissza az AAVE lapra

Updated: Nov 24. 1997