Lösningsförslag tentamen 23 okt 2015

1

3
 \
  4
   \
    5
     \
      9
       \
        13
         \
          17

3, 4, 9, 13, 17

17, 13, 9, 4, 3

2

3

Binärsökningen jämför 17 med mittersta talet i vektorn, dvs 28.
Eftersom 17 är mindre än 28 sökes 17 i vänsterdelen av vektorn | 12 | 3 |. (Redan här kan man konstatera att det blir fel eftersom 17 finns i högra delen av vektorn. Det står dock i uppgiften att vi ska visa steg-för-steg vad som händer och algoritmen är inte klar.)

17 jämförs nu med det mittersta talet i vektorn | 12 | 3 | vilket är 12 (men kan vara 3 beroende på implementation). Eftersom 17 är större än 12 görs en ny sökning i högerdelen av kvarvarande vektorn (som bara innehåller siffran 3).

Då kvarvarande vektor är tom rapporteras att talet 17 inte finns i vektorn.

Felet beror på att vektorn inte är sorterad. Binärsökning förutsätter en sorterad vektor!

4

Vid breddenförstsökning är det lämpligt att använda en kö
Vid djupetförstsökning är det lämpligt att använda en stack
Vid bästaförstsökning är det lämpligt att använda en prioritetskö

5

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

6

se en svart katt  OK
gå under på golvet NEJ
lägga salt på vägen OK

7

Med linjär probning kommer orden att ligga efter varandra

0	prova
1	kliva
2	ramla
3	gråta
4	snyta

Orden ligger klustrade i vektorn. Enbokstaviga h(1)=2 och tvåbokstaviga h(2)=4 ord kommer att krocka och bidra till klustringen. Det är lite klurigt att ta bort ett element, man måste skilja på en tom plats och en plats som varit upptagen.

Med kvadratisk probning hamnar de första orden

0	prova
1
2
3
4	ramla
5	kliva

Det tredje ordet kommer att "slå runt", vektorn är bara tio stor, och hamna på plats 4 (14%10). Det 4:e ordet probas först till plats 0 (30%10) men där är det upptaget, därefter plats 5 (55 % 10) där det också är upptaget. Enligt uppgiften behöver vi inte proba vidare med värden utanför givna tabellen (55+36 = 91 -> plats 1).

Klustringen är inte like påtaglig som med linjär probning. Enbokstaviga ord krockar inte längre. Tvåbokstaviga ord krockar men probningen är inte densamma som ordet det krockar med. Det är fortfarande lika klurigt att ta bort element.

8

• Att använda xor är snabbt. Mycket snabbare än RSA.
• xor-nyckeln är en engångsnycker och behöver genereras om för varje meddelande. RSA nycklarna behöver inte genereras om.
• Engångsnycklarna måste distribueras på ett säkert sätt. Den publika RSA nyckeln är lättare att distribuera eftersom den innehållet inte är hemligt.
• xor-nyckeln garanterar inte autentisering, om någon kommit över nyckeln kan man skicka ett falskt meddelande (men endast ett ty engångsnyckel). RSA medger både autentisering och kryptering.

9

Ett första försök

1. Plocka ut två element ur kön, a och b.
2. Börja därefter en loop tills kön är tom.
3. Plocka ut ett element ur kön, c, och kontrollera att elementet är summan av de två föregående.
4. Spara de två föregående elementen b och c inför nästa jämförelse.

a = q.dequeue()
b = q.dequeue()
while (! q.isEmpty()):
   c = q.dequeue()
   if c != a + b:
     print("TURTAL HITTAD")
     break
   else:
     a = b
     b = c

Slutlig algoritm

1. Plocka ut ett element ur kön, a, med dequeue
2. Spara första elementet, first = a
3. Stoppa tillbaka a i kön med enqueue
4. Plocka ut ett element ur kön, b, med dequeue
5. Börja därefter en loop:
   • Plocka ut ett element ur kön, c,
   • Bryt loopen om c == first (då har vi gått ett helt varv)
   • Annars: Kontrollera att c är summan av de två föregående (a och b)
   • Spara de två föregående elementen b och c inför nästa jämförelse.

10

Vilken typ av problem är det här?
Vi kan modifiera kodorden på olika sätt och får då en massa olika förslag på koduppsättningar. Grafproblem - startnoden är den ursprungliga koduppsättningen, ett steg bort i grafen har vi noder där koduppsättningen modifierats med en bit.
Vi söker en koduppsättning som uppfyller ett visst villkor, men inte vilken som helst. Så få bitar som möjligt ska läggas till. Det här går att göra med breddenförstsökning!

Vi låter en nod innehålla en hel uppsättning med n stycken m-bitars kodord. Ett exempel på en koduppsättning för n=3 och m=4 är:

1001
1101
1111

Algoritm:

1. Skapa en lista bin med de binära talen från 0 upp till 2ⁿ-1.
2. Skapa en tom kö.
3. Skapa ursprungsnoden. Den ska innehålla en lista koder med de n ursprungliga kodorden.
4. Lägg ursprungsnoden i kön.
5. Upprepa följande tills Hamming(koder) == d, eller kön är tom:
   • Ta ut första noden ur kön.
   • Gå igenom listan bin. För varje binärt tal:
     • Skapa en ny nod genom att lägga till de binära siffrorna till koder
     • Lägg in den nya noden i kön.

Datastrukturer:

• Noder med en lista koder där aktuella uppsättningen kodord lagras.
• Inga föräldra-pekare. Om vi hittar en nod som uppfyller kravet Hamming(koder) == d så är koder lösningen.
• Ingen dumbarnstruktur. Algoritmen ger inga identiska noder som behöver sållas bort.