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

5.házifeladatsor

Beadási határidõ: november 27. csütörtök !

1.feladat

(Exercise VI/12) (KONSTRUKTIV SHANNON KOD) Legyen X veletlen szimbolum , mely az {1,...,m} ertekeket veszi fel p1>=p2>=...>=pm valoszinuseggel. Legyenek a kodszavak rendre az F1,F2,...,Fm szamok binaris tort alakjai lecsonkitva rendre az elso l1,l2,...,lm jegyre, ahol
Fi = szumma_{j< i-re} pj es
li = [-log pi] (2-es alapu log, es [] felso egeszresz).

Bizonyitsuk be, hogy ez prefix kod es a varhato kodhosszusagra: H =< L < H+1. (Itt H-ban 2-es alapu a log.)

2.feladat

(Exercise VI/17) Legyen Mn az a (veletlen) szam, ahany reszre osztott egy n hosszusagu uzenetet a Lempel-Ziv algoritmus, es legyen K kulonbozo forrasszimbolum. Mutassuk meg, hogy

Mn =< Cn/log n

valamely C konstansra (determinisztikusan!). Ez mutatja a Lempel-Ziv kod optimalitasanak bizonyitasaban szukseges masodik allitast. Segitseg: Legfeljebb K^i fele i hosszusagu resz lehet.

3.feladat

(Exercise VI/20) Epitsunk binaris szofat a (0,1)-beli valos szamok binaris alakjat veve alapul. Legyen a szofanak csak ket eleme, X1 es X2 (n=2), fuggetlenek es azonos eloszlasuak f surusegfuggvennyel [0,1]-en. (Tehat most a szimbolumok a szoban nem fuggetlenek.) Nyilvan D1=D2. Talaljunk olyan f-et, hogy ED1=vegtelen. Segitseg: a fenti feladatok novekvo nehezsegi sorrendben vannak.

Vissza az AAVE lapra

Updated: Nov 24. 1997