Övning 5: Komprimering, hashning

3. Underklädesreformen

Kampen för kvinnors rättigheter startade med klädreformen på 1850-talet, som hade syftet att minska komprimeringen av kvinnokroppar genom att byta den hårda korsetten mot mjukare ylleunderkläder.

a) Kan följdlängdskodning (RLE) användas vid komprimering av bilden ovan? Motivera ditt svar. 

b) Tabellen nedan visar bokstäver med förekomst i procent. Rita
upp ett Huffmanträd för bokstäverna, och koda ordet ”LIBERTY” med din
huffmankod.

c) Förklara principerna bakom LZ-metoder för komprimering och demonstrera LZW med ordet ”VALBENSSKENA”. 

Hashning

Genomgång Labb 7 

Hashfunktioner på högstadiet (Tildatenta 181022)

Redan andra dagen på ditt nya jobb på en högstadieskola blir du uppkallad till rektorn. Det går rykten om att du sprider drogpropaganda. Du förklarar att du undervisat om ”bra hashfunktioner”, inte ”bra funktioner hos hasch”. För att rektorn (som är geografilärare) ska förstå tar du följande exempel:
Vi har befolkningsdata för 250 000 orter, och vill snabbt kunna slå upp ett ortsnamn, t ex ”Korpilombolo” och få ut folkmängden (522).
Vilka av följande hashfunktioner skulle fungera för detta exempel? Vilka skulle fungera dåligt?

a) summan av bokstävernas nummer, dvs 65+66+67 för ’ABC’

b) produkten av bokstävernas nummer, dvs 65*66*67 för ’ABC’

c) bokstävernas nummer skrivna efter varann som ett tal, dvs 656667 för ’ABC’

Motivera dina svar för rektorn!

lösning Links to an external site.

Skriv en hashfunktion

Implementera den bästa av de tre hashfunktionerna ovan.

hashfunktion181022.py Download hashfunktion181022.py

Hasha pappor (Tildatenta 171020)

BVC ordnar pappagrupper för nyblivna fäder. Papporna ska hashas in i en hashtabell på följande vis:
– Hashtabellen har 13 platser
– Vid krock används krocklistor
– Hashfunktionen är summan av siffrorna i pappans födelsedag och månad.
Den som är född 23/10 får alltså hashvärdet 2 + 3 + 1 + 0 = 6.
Rita upp hashtabellen, med eventuella krocklistor, för följande åtta pappor:
– Amir 28/10
– Bedrich 1/6
– Calvin 15/5
– Dubaku 11/11
– Ejvind 21/12
– Filip 23/2
– Gus 2/5
– Henrik 19/1

Perfekt hashfunktion

Hitta på en perfekt hashfunktion för atomer. Hur stor blir hashtabellen?

lösning

Håll reda på media  (Tildatenta 030308)

Under gulfkriget var det väldigt svårt för armestaben att hålla reda på alla TV-bolag som for omkring och rapporterade i öknen. För att hålla reda på dem användes en hashvektor. Koden fungerade inte som avsett och man har nu gett i uppdrag åt en f.d. tildastudent att titta på en misstänkt del av koden:

p = 100
hashvektor = [0] * p
alfabet = "abcdefghijklmnopqrstuvxyz"

def put(tvbolagsnamn, tvbolag):
    hashcode = 0
    for i in range(len(tvbolagsnamn)):
        alfanum = alfabet.find(tvbolagsnamn[i]) + 1
        hashcode += alfanum
    hashcode = hashcode % p
    hashvektor[hashcode] = tvbolag

Vad är det för fel på koden? Beskriv hur man kan förbättra den. Namnen på TV-bolagen kan antas bestå av högst tre bokstäver. Det kommer inte att förekomma mer än 75 TV-bolag.

lösning

Nix till telefonförsäljning (Tilda-tenta 000603)

Föreningen för konsumentskydd vid marknadsföring per telefon har startat ett register dit den som inte vill bli uppringd av telefonförsäljare kan anmäla sig.

Till att börja kommer kontrollen att ske genom att företaget sänder sin telefonlista till nix och får tillbaka en lista där de nixade numren markerats.

Vilka av följande metoder kan föreningen använda sig av? Vilken är bäst? Binärträd, bloomfilter, hashtabell.

Ett framtida mål är att kontroll också skall kunna ske över internet. Då måste kontrollen ske snabbt men man vill också försäkra sig om att ingen ska kunna få ut en lista över alla nixade telefonnummer.

Vilken metod passar bäst för internet-kontrollen?

lösning