Övning 6

Komprimering, kryptering, dokumentering & testning

1. Diagnostiskt prov med C-frågor 

2. Felkorrektion

   Vill man gardera sig mot fel kan man lägga till redundans (motsatsen till komprimering). Det finns många olika sätt att göra det på, här följer några exempel:

   • Kontrollsiffra (t ex sista siffran i ett personnummer).
   • Skicka kopior av hela meddelandet, minst tre behövs om man ska kunna korrigera.
   • Paritetsbitar, att man lägger till en etta eller nolla till ett binärt tal för att göra det udda. Ett jämnt tal innebär att nån bit är fel.
   • Hammingavstånd: Lägg till så många extrabitar till koden så att varje enbitsfel ger ett kodord som skiljer sig i en bit från det korrumperade kodordet, men i flera bitar från alla övriga kodord. Två kodord har Hammingavstånd d om dom skiljer sig åt i d bitar.
     En kod har Hammingavstånd d om alla kodord är minst d ifrån varann. Givet koderna nedan - hur ska vi tolka meddelandet  10010 01110 10101 ?

   	A	01011
   	F	10010
   	I	01100
   	N	10101

   ---

3. man är mans gamman

   "man är mans gamman" kan man läsa i Havamal. Konstruera en huffmankod för tecknen i detta uttryck (rita trädet) och skriv sedan upp det i kodad form.

1. Enkel kryptering

   a) Kryptera SIMSALABIM med rot13

   b) Visa med ett exempel hur man går till väga för att dechiffrera transpositionschiffer. T ex GKNTAAKN ESEL

   c) 1 1 2 5 6 22 är krypterat med en variant av bokchiffer där man använt uppgiftsnummer istället för sidnummer (bortse från rubriken). Vad står det?

   d) Meddelandet 0b1100010 är krypterat med one-time pad med nyckeln 0b0110011. Dekryptera!

   ---

2. Testning

   Vad gör följande program?

   import unittest
   
   def kvadrat1(n):
    return n^2
   
   def kvadrat2(n):
    return n**2
   
   class Min_testklass(unittest.TestCase):
    
    def testa_kvadrat1(self):
    """Testar kvadrat med "^" """
    self.assertEqual(kvadrat1(5), 25)
   
    def testa_kvadrat2(self):
    """Testar kvadrat med "**" """
    self.assertEqual(kvadrat2(5), 25)
   
   if __name__ == '__main__':
    unittest.main()

   
   

   ---

3. Aliententan 2015-03-20, uppgift 1 (betyg E)

   Rymdvarelser har uppmärksammat jordens existens och vill ta kontakt med en tildastudent på KTH. Rymdvarelserna är oroliga för att NSA ska avlyssna eller på annat sätt blanda sig i kommunikationen, men har läst att RSA-konceptet med publika och privata nycklar kan lösa kommunikationsproblematiken. Förklara vilka problem som kan lösas med hjälp av asymmetrisk kryptering med publika och privata nycklar, och berätta för rymdvarelserna hur det ska gå till.

4. ---

   Cykeltentan 2014-10-24, uppgift 7 (betyg C)

   Följande tre uppsättningar av koder är tänkta att använda för komprimering. Vilka fungerar för komprimering? Vilken är effektivast? Motivera ditt svar!

   	kod1	kod2	kod3
   E	11	111	10
   A	10	101	11
   N	011	100	110
   R	010	011	101
   T	001	010	111
   S	0001	001	0100
   I	0000	000	0111

LÖSNINGAR

1. Se tentalösningar

2. Smittskydd

   HANDTVÄTT

   ---

3. "man är mans gamman"

   
    
   Totalt är det 18 tecken. Andelen av respektive tecken:

   Tecken | antal | andel
   ----------------------
   m   | 4 | 2/9
   a   | 4 | 2/9
   n   | 3 | 3/18
   " " | 3 | 3/18
   ä   | 1 | 1/18
   r   | 1 | 1/18
   s   | 1 | 1/18
   g   | 1 | 1/18
   
   

   Detta ger efter trädskapande till exempel följande huffmankoder:

   Tecken | Huffmankod
   -------------------
   m   | 10
   a   | 11
   n   | 010
   " " | 011
   ä   | 0000
   r   | 0001
   s   | 0010
   g   | 0011
   
   Vilket ger följande kodning av texten:
   10 11 010 011 0000 0001 011 10 11 010 0010 011 0011 11 10 10 11 010
   

   ---

   ---

4. Bäst komprimering

   Det vi strävar efter är att mer frekventa tecken ska få kortare koder. Därför ger det andra huffmanträdet (som inte är balanserat) bäst komprimering.

   ---

5. Enkel kryptering

   a) FVZFNYNOVZ
   b) Låt programmet byta rad efter 2, sen efter 3, sen efter 4 ... tills meddelandet framträder.
   c) Du kan avlyssna
   d) Q

6. Testning