Sziasztok! A mai órára kevés feladatot hoztam, de még beszéltünk a múltkori gyakorlat nyolcas és tizes feladatáról is, ezekről még lesz szó a rendes gyakorlatokon is. Az alábbi feladtokhoz egy kis értelmezési útmutató: a második feladatnál te határozod meg az ábécé elemszámát is és a valószínűségeket is. Az optimális kod a Huffman-féle optimálisat jelenti. A hármas feladat igazából két feladat: mi az a korlát ami biztosan nem léphető túl és mutasd meg, hogy ez viszont elérhető. A négyes meg nagyon egyszerű. Tehát: 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. Megoldások