Till KTH:s startsida Till KTH:s startsida

Övning 6

Komprimering, kryptering, dokumentering & testning

  1. Smittskydd (Tildatenta 030828)

    Du har fått ett mail som innehåller tips mot spridning av virus. Informationen är komprimerad med ett Huffmanträd där nollor motsvarar vänster och ettor motsvarar höger (se figur, T kodas t.ex. som 11) Vad står det i meddelandet nedan? 
    010101011000110011001111


          o
         / \
        /   \
       /     \
      /       \
     o         \
    / \         o
   /   \       / \
  o     o     o   T
 / \   / \   / \
D   V H   N Ä   A

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

  3. Bäst komprimering

    Jämför Huffmanträden i uppgifterna ovan. Vilket ger bäst komprimering? Motivera ditt svar!

  4. 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!

  5. 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()

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

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

    HANDTVÄTT

  2. "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

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

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

  5. Testning