Sziasztok! Az alábbi feladatokból nem beszéltük meg, de mindenképpen visszatérünk a 9. feladatra. Gondolkozzatok rajta!!!
Algoritmuselmélet gyakorlat (4)
Alapvetők 1. A hash-függvény legyen f(K)=K, a táblaméret M=7, és ![]() (a) lineáris (b) kvadratikus maradék próbálást használva az ütközések feloldására. 2. Határozzuk meg a BARBARÁNAK szó egy lehetséges Huffman-kódját és Lempel-Ziv-Welch-kódját. Az utóbbinál tegye fel, hogy a szótár a kezdőhelyzetben az A, Á, B, K, N, R betűket tartalmazza, és ezek kódjai rendre 1, 2, 3, 4, 5, 6. Átlagos feladatok 3. Mi a baja az ![]() 4. Legyen T egy olyan bináris fa, melyben minden nem-levél csúcsnak pontosan 2 fia van. Igaz-e, hogy van olyan eloszlás, amelyhez tartozó Huffman-fa éppen T? 5. Az ![]() 6. A T[0:M] táblában 2n elemet helyeztünk el az első 3n helyen (3n<M) egy ismeretlen hash-függvény segítségével. A táblában minden 3i indexű hely üresen maradt ( ![]() a) lineáris próbálást b) kvadratikus maradék próbálást használtunk? 7. A ![]() 8. A ![]() 9. A T[0:M-1] táblában rekordokat tárolunk nyitott címzésű hashelt szervezéssel. Az ütközések feloldására lineáris próbálást alkalmazunk. Tehát ha a h(K) sorszámú cella foglalt, akkor a K kulcsú rekordot a ![]() (a) Igaz-e, hogy a hibás törlés helye mindig megtalálható? (b) Adjunk hatékony (lineáris időigényű) algoritmust a tábla megjavítására. (Módosítsuk úgy a táblát, hogy megszűnjenek a hibás törlés negatív következményei.) 10. Egy S szöveg tömörítésére a Lempel-Ziv-Welch módszert alkalmaztuk. Azt tapasztaltuk, hogy a kódolás során használt szótárban előfordult 100 betűből álló szó. Adjunk minél jobb alsó becslést az S szöveg hosszára! Nehézke 11. A ![]() ![]() |