Računalništvo 2

1) V zgoščevalno tabelo velikosti 11 (n = 11) vstavimo ključe iz seznama [23, 1, 13, 11, 24, 33, 18, 42, 31] z zgoščevalno funkcijo h(x) = x mod n

Kakšna izgleda tabela glede na različne pristope reševanja trkov. Uporabi veriženje ter linearno in kvadratično iskanje(probing). Do kakšnih problemov lahko pridemo pri teh pristopih? Kaj bi bilo, če bi uporabili kakšno drugo zgoščevalno funkcijo oblike h(x) = ax mod n za nek a različen od 0 in manjši od n? Bi lahko za poljuben a našel zaporedje ključev, ki bi ustvaril veliko trkov? Naštej še kakšne standardne zgoščevalne funkcije.

2) Univerzalno zgoščevanje

U (univerzalna)  in V naj bosta množici, kjer je velikost U ogromno večja kot velikost V. Družini preslikav H iz U v V rečemo univerzalna, če za vsak x != y iz U velja Pr[h(x) = h(y)] <= 1/n, kjer preslikavo h vzamemo naključno iz družine H ter n = IVI.

2.1) Pokaži, da je H = {ax mod n : a iz Z_n} univerzalna družina.

2.2) Naj bo h zgoščevalna funkcija iz univerzalne družine (izbrana naključno). Recimo, da želimo v tabelo shranit m ključev. Definiramo "load factor" alpha = m/n. Koliko je povprečno število trkov? Kaj lahko poveš o dolžini najdaljše verige? Namig: Indikatorji, linearnost pričakovane vrednosti

Od tu naprej nalog ni potrebno vključevati v poročilo! -------------------------------

2.3) Razvij zgoščevalno tabelo/funkcijo, kjer bodo vse poizvedbe konstantne. Konstrukcija mora biti narejena v linearnem času. Namig: Kaj se zgodi, če vzamemo alpha = 1/n + točka 2.2)

3) Kako bi zgoščevanje posplošili na druge tipe podatkov:

• vektorji v R^k
• nizi
• sestavljeni objekti

4) V točki 3) smo za nize omenili "rolling hash" funkcijo. Recimo, da imamo niz s[1...n] dolžine n. Razvij algoritem, ki hitro odgovarja na poizvedbe oblike "kakšna je hash vrednost pod niza s[i...j]" za neka 0 < i < j < n

5) Imamo niz s[1...n] dolžine n in množico nizov P = {p_1, ..., p_k} in recimo, da so vsi p_i dolžine m. Razvij algoritem, ki odgovori koliko nizov iz P se kot podniz pojavi v s. Za vsak p iz P povej kolikokrat se pojavi v s.