• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Prioritet och associativitet hos operatorerna i C

Scenario

Fig. 1. En teckning av några militärer som sitter och lyssnar. Personerna på bilden har inget med textens innehåll att göra.

Försvarets Radioanstalt, FRA, ska som bekant börja avlyssna Internet-trafiken. Eftersom alla terrorister och kriminella krypterar sin trafik, är det inte så meningsfullt att avlyssna innehållet, utan man tittar mer på trafikmönster, dvs vem som kommunicerat med vem.

FRA:s hemliga högkvarter, som nyss flyttat till Bryssel för att underlätta informationsutbyte med andra EU-länder, samlar varje dag ihop en fil som heter avlyssnat.txt. Den innehåller dagens avlyssning:

130.243.105.246 74.125.45.100 130.243.105.246 192.71.238.76 130.243.105.201 192.71.238.76 130.243.105.246 74.208.78.7 och så vidare

Varje rad i filen beskriver ett meddelande som skickats mellan två datorer. Raden innehåller IP-numret för avsändaren och IP-numret för mottagaren. Ett IP-nummer är Internet-adressen till en dator, och kan antingen skrivas som här, med fyra tal mellan 0 och 255 med punkter emellan, eller som ett 32-bitars heltal.

Filen innehåller flera miljarder rader, med flera miljoner unika IP-adresser.

Uppgiften (30 p)

Man måste alltså på något sätt räkna antalet skickade och mottagna meddelanden för varje IP-nummer, och sen välja ut de IP-nummer som har högst antal.

Om det är flera IP-nummer som delar på förstaplatsen, dvs har samma antal skickade respektive mottagna meddelanden, spelar det ingen roll vilket av dem man skriver ut.

Om man väljer olämpliga datastrukturer, till exempel osorterade länkade listor, kan det ta mycket lång tid att köra programmet med de stora datamängder som det handlar om. Välj därför datastrukturer så att programmet går att köra på en normal, modern dator utan att det tar orimligt lång tid, och utan att det kraschar på grund av minnesbrist.

För att ett program ska vara lätt att förstå och arbeta vidare med, bör man dela upp det i mindre delar, så kallad modularisering. Modularisera programmet så det består av flera filer (.c- och .h-filer). Modulariseringen gäller främst de viktigaste datatyperna i programmet, där man bör använda abstrakta datatyper. En abstrakt datatyp är gjord så att implementationsdetaljerna är dolda, och därför går att ändra utan att man behöver ändra i resten av programmet.

Poängbedömning:

• Ett korrekt program som ger rätt svar, ger 10 poäng på uppgiften, även om det skulle ta mycket lång tid att köra programmet.
• Lämpligt valda, och korrekt implementerade, datastrukturer ger ytterligare 10 poäng.
• Lämpligt vald och väl genomförd programkonstruktion, med filer och abstrakta datatyper, ger ytterligare 10 poäng.