Övning 6

Komprimering, kryptering, dokumentering & testning




* Diagnostiskt prov med C-frågor
* 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

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



* 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!

¶
* Testning¶

Vad gör följande program? import unittestdef kvadrat1(n): return n^2def kvadrat2(n): return n**2class 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()
* 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.
* 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


* Se tentalösningar
* Smittskydd HANDTVÄTT
* "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
* 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.
* 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
* Testning