Algoritmuselmélet pótgyakorlat a negyedik gyakorlathoz

1. Adjunk meg egy Huffman kódot a MISSISSIPPIT szó tárolására. Mekkora a helymegtakarítás a betűk uniform hosszúságú kódolásához képest?

2. Adott egy k pozitív egész. Adjunk meg egy olyan eloszlást, melyhez tartozó optimális kódban minden kódszó hossza nagyobb lesz k-nál.

3. Legfeljebb milyen hosszú lehet egy n-elemű ábécé feletti szó, amit a Lempel-Ziv-Welch algoritmus nem tömörít (tömörítésen itt az értendő, hogy az algoritmus egynél hosszabb betűsorozatot helyettesít a kódjával)?

4. Mutassuk meg, hogy (nyitott címzéses hashelés, lin. próbálkozás esetén) már két kulcshoz tartozó hash-fügvényérték megegyezése is okozhat "tetszőlegesen" nagy méretű csomósodást.

Algoritmuselmélet pótgyakorlat a negyedik gyakorlathoz

1. Adjunk meg egy Huffman kódot a MISSISSIPPIT szó tárolására. Mekkora a helymegtakarítás a betűk uniform hosszúságú kódolásához képest?

2. Adott egy k pozitív egész. Adjunk meg egy olyan eloszlást, melyhez tartozó optimális kódban minden kódszó hossza nagyobb lesz k-nál.

3. Legfeljebb milyen hosszú lehet egy n-elemű ábécé feletti szó, amit a Lempel-Ziv-Welch algoritmus nem tömörít (tömörítésen itt az értendő, hogy az algoritmus egynél hosszabb betűsorozatot helyettesít a kódjával)?

4. Mutassuk meg, hogy (nyitott címzéses hashelés, lin. próbálkozás esetén) már két kulcshoz tartozó hash-fügvényérték megegyezése is okozhat "tetszőlegesen" nagy méretű csomósodást.

Algoritmuselmélet pótgyakorlat a negyedik gyakorlathoz

1. Adjunk meg egy Huffman kódot a MISSISSIPPIT szó tárolására. Mekkora a helymegtakarítás a betűk uniform hosszúságú kódolásához képest?

2. Adott egy k pozitív egész. Adjunk meg egy olyan eloszlást, melyhez tartozó optimális kódban minden kódszó hossza nagyobb lesz k-nál.

3. Legfeljebb milyen hosszú lehet egy n-elemű ábécé feletti szó, amit a Lempel-Ziv-Welch algoritmus nem tömörít (tömörítésen itt az értendő, hogy az algoritmus egynél hosszabb betűsorozatot helyettesít a kódjával)?

4. Mutassuk meg, hogy (nyitott címzéses hashelés, lin. próbálkozás esetén) már két kulcshoz tartozó hash-fügvényérték megegyezése is okozhat "tetszőlegesen" nagy méretű csomósodást.