Örebro universitet
Institutionen för teknik
Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se)



Tentamen i

Programmeringsmetodik

för D2, SDU2 m fl

torsdag 5 november 2009

Gäller som tentamen för:
DT2010 Datateknik B, Programmeringsmetodik, provkod 0100
DT2006 Datateknik B, Tillämpad datavetenskap B, provkod 0110


Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 30.
För godkänt betyg (3 respektive G) krävs 15 poäng.
Resultat: Meddelas på kursens hemsida eller via e-post senast torsdag 26 november 2009.
Återlämning av tentor: Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-73 47 013.



LYCKA TILL!

Prioritet och associativitet hos operatorerna i C

Den fullständiga tabellen, med alla operatorer som finns i C:

Prioritet Kategori Operator Associativitet
Högsta Unära postfixoperatorer (), [], ->, ., ++, -- vänster
  Unära prefixoperatorer !, ~, ++, --, +, -, *, &, sizeof, (typ) höger
  Multiplikation mm *, /, % vänster
  Addition mm +, - vänster
  Bitvis skift <<, >> vänster
  Jämförelser <, <=, >=, > vänster
  Likhetsjämförelser ==, != vänster
  Bitvis OCH & vänster
  Bitvis XOR ^ vänster
  Bitvis ELLER | vänster
  Logiskt OCH && vänster
  Logiskt ELLER || vänster
  Villkorsoperatorn ?: höger
  Tilldelning =, +=, -=, *=, /=, %=, >>=, <<=, &=, ^=, |= höger
Lägsta Komma-operatorn , vänster

Scenario

En teckning av några militärer som sitter och lyssnar
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)

FRA vill göra en enkel trafikanalys. Gör ett C-program som läser filen avlyssnat.txt, och som sen talar om vilka två IP-nummer som sänt respektive tagit emot flest meddelanden.

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: