TILDA, Ö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 15 är krypterat med en variant av bokchiffer där man använt uppgiftsnummer istället för sidnummer. Vad står det?

  5. Testning

    I labb 6 ska ni göra ett program som kontrollerar syntaxen för en molekylformel. Skriv upp en samling indata att testa programmet med!

  6. RSA-kryptering (ur kursboken, uppg 2 s. 125)

    Du vill hålla ditt turnummer (18) hemligt, och har därför bestämt dig för att kryptera det med RSA. Välj två primtal större än 500 och använd dom för att kryptera turnumret.

  7. Lempel-Ziv

    I denna uppgift ska du avkoda ett meddelande som komprimerats med Lempel-Zivs metod. Komprimeringen går till så att komprimeraren lagrar en lista med strängar som från början enbart innehåller tomma strängen. Komprimeraren läser tecken för tecken från intexten den längsta sträng som ligger i strängtabellen. Sedan skrivs index för denna sträng i tabellen ut, följt av nästa tecken i intexten. Strängtabellen utökas med strängen plus nästa tecken. Därefter läses åter tecken för tecken från intexten. Så fort en sträng inte finns i strängtabellen läggs den alltså till. Metoden kan i (icke-optimerad) kod beskrivas så här: 
    def lzw(text):
    table = Table()
    q=Queue()
    for c in text: # spara texten tecken för tecken i en kö
        q.put(c)
    s=""
    table.add(s)
    kodtext="" # här sparas den kodade texten
    while not q.isempty():
        c=q.get()
        if table.exists(s+c):
            s=s+c
        else:
            kodtext+=str(table.code(s))+c
            table.add(s+c)
            s=""
    if not s=="":
        kodtext+=str(table.code(s))
    return kodtext
    Klassen Table stöder inläggning av strängar, kontroll av om en sträng finns i tabellen och möjlighet att ta reda på index hos en speciell sträng. Index bestäms av ordningen strängarna lades in i, där den första strängen har index 1. Uppgiften är att avkoda följande text, där alfabetet består av versaler och mellanslag kodat som "_". 
    1S1T1O1R2T4C1K1H4L1M2_6O1L3A1_9O14M1A5
    Det vill säga: vad är t om 
      print lzw(t)
    ger ovanstående som utskrift? Ge också en tabell med strängar och index som motsvarar tabellen i koden!

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 kryptera

  5. Testning

    Tänk på att du ska testa både med giltiga och ogiltiga molekylformler!

  6. RSA-kryptering

    p = 503  
q = 601

n = p*q = 302303

f = (p-1)*(q-1) = 301200

Välj e så att gcd(e, f) = 1
301200 = 2*5*2*5*2*2*3*251
Faktorn 7 finns inte med, välj e = 7

Krypteringen:
18 upphöjt till 7 modulo 302303

  7. Lempel-Ziv

    Index   | sträng
--------------------
1       | ""
2       | "S"
3       | "T"
4       | "O"
5       | "R"
6       | "ST"
7       | "OC"
8       | "K"
9       | "H"
10      | "OL"
11      | "M"
12      | "S_"
13      | "STO"
14      | "L"
15      | "TA"
16      | "_"
17      | "HO"
18      | "LM"
19      | "A"