Till KTH:s startsida Till KTH:s startsida

Visa version

Version skapad av Linda Kann 2016-09-20 22:55

Visa < föregående | nästa >
Jämför < föregående | nästa >

Övning 4

Mål: Hashning, sortering, prioritetskö, bästaförstsökning

Tabell över ungefärliga tvåpotenser:

-----------------------------------------------------------------------
1 2 3  4  5  6   7   8   9   10   11   12   13    14    15    16     17
-----------------------------------------------------------------------
2 4 8 16 32 64 128 250 500 1000 2000 4000 8000 16000 32000 64000 130000 ...
-----------------------------------------------------------------------

  1. PERFEKT HASHFUNKTION

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

  2. 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: 
    from string import find

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

def put(tvbolagsnamn, tvbolag):
    hashcode = 0
    for i in range(len(tvbolagsnamn)):
        alfanum = find(alfabet, 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

  3. 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

  4. LÖNAR SEJ SORTERING (Tildatenta 4 april 1997)

    En miljon dumbolotter säljs var månad. För varje lott sparas lottnumret och köparen i ett objekt. En lista med en miljon objekt finns alltså i datorn vid dragningen, då tusen vinstnummer slumpas fram, ett efter ett.

    För varje nummer måste hela listan letas igenom, eftersom den är osorterad. Hur många jämförelser får man räkna med totalt? Lönar det sej att först sortera listan, en gång för alla?

    lösning

  5. HOPPFULL SORTERING

    Höjdhoppsfederationens databas över världens alla höjdhoppstävlingsresultat består av objekt med bland annat fälten datum, plats, höjd (cm), hoppare och rivit/klarat. På skivminnet ligger objekten i datumordning, men man vill sortera om dom i resultatordning, nämligen klarade hopp före rivna och höga hopp före låga.

    Vilken sorteringsmetod är bäst? Motivera utförligt.

    lösning

  6. TJUGONDAG KNUT KASTAS JULEN UT (Tildtenta 16 januari 2001)

    För att kontrollera sanningen i detta talesätt har man i en fil samlat tre miljoner datum för svenska julgranars utkastning. Man vill veta mediandatum, alltså det datum då hälften av granarna slängts ut, ut, ut och hälften ännu står gröna och granna i stugan.

    Rangordna följande sex föreslagna metoder efter deras effektivitet. Binärsökning, hashning, insättningssortering, distributionsräkning, djupet-först-sökning, trappsortering (heap sort).

    lösning

  7. SKATTEREGISTRET

    Riksskatteverkets databas med nio miljoner svenskar finns sorterad på efternamn. Man vill sortera om den på personnummer. Hur många jämförelser krävs med quicksort? Hur många med den bästa metoden?
    lösning

  8. BÅTFLYTT (Tildatenta 6 april 2002)

    Under en seglingstävling vill varje båt hitta den snabbaste vägen till målet. Problemet är att en segelbåt inte kan segla hur som helst och att den seglar olika snabbt beroende på vindriktning och styrka. Antag att havet förenklat består av en massa jämnt fördelade punkter med information om vindstyrka, vindriktning och vilka punkter som finns runt om. Beskriv en algoritm som på ett så effektivt sätt som möjligt tar reda på vilka punkter som ligger utefter den snabbaste seglingsvägen givet en startpunkt och en slutpunkt. Båtägaren är orolig att hans miljövänliga bottenfärg ska nötas bort och vill därför istället ta den väg som är kortast (dvs minst antal steg). Förklara vad som behöver ändras i din föregående algoritm.
    Använd bästaförstsökning med en prioritetskö som prioriterar på lägsta seglade totaltiden. Låt varje nod innehålla total seglingstid samt ha en faderspekare (för rekursiv utskrift av vägen då lösning hittats). Princip för genomgång av problemträdet:
    1. Lägg startpunktsnoden med totaltiden noll och tom faderspekare i prioritetskön.
    2. Upprepa punkterna 3-4 så länge kön inte är tom.
    3. Plocka ut en fadersnod ur kön. Om detta är slutpunkten, skriv ut vägen rekursivt och avsluta.
    4. Generera en son i taget genom att för varje punkt runt omkring fadersnoden skapa en sonnod med seglingstiden ökad beroende på vindstyrka, vindriktning och placering i förhållande till fadersnoden. Lägg in sonnoden i prioritetskön.
    Om dumbarnskoll ska utnyttjas måste det ta hänsyn till både punkten och totala seglingstiden till den punkten. Alla söner med sämre tider till samma punkt är då dumsöner. På det viset slipper algoritmen besöka samma punkt flera gånger - den blir effektivare.

    Eventuellt krävs någon snabb uppslagning av punkternas information, t ex med en hashtabell som hashar på punkternas nummer eller position. Noderna kan innehålla lägsta tid som uppnåtts för att tillåta dumbarnkoll utan att kräva extra minne.

    För kortaste vägen, använd istället bredden först med en vanlig kö och blanda inte in totala seglingstiden i varje nod. I detta fall måste vi göra dumbarns koll för att sökningen ska bli effektiv.

    Datastrukturer:
    Prioritetskö / kö
    Hashtabell
    Noder med seglingsdata

  9. Cykel-tentan 2014-10-24, uppgift 3 (betyg E)

    Nu när det blir mörkare om kvällarna känns det extra viktigt att ha lysen till cykeln. Du har lagt in lamporna med priset som prioritet i en min-heap. På vektorform ser heapen ut så här: 
    10 40 30 42 41 48 50 49
    Rita upp heapen på trädform och visa sen hur det ser ut när man plockar ut två element (du vill ju inte köpa de allra billigaste). Visa minst fem steg. Skriv slutligen upp heapen på vektorform igen.