Nada

Lösning till fiktiv tentamen i Datalogi, 2D1343

1 Vetenskap (5p)

Turing-pappersremsa, Alfvén-plasma, Gödel-obevisbarhet, Randi-skepsis, Arkimedes-badkar.

2 Sortera kö (5p)

Bubbelsortering kan göras med köanrop:
  y= Queue.get()                       ; 
  x= Queue.get()                       ; // Första paret ut!
  while(x!=999999999)                  {
    Om x>y byter vi dom nu: x<->y
    Queue.put(x)                       ; 
    x= Queue.get()                     ;} 
  Queue.put(y)                         ; 
  Queue.put(x)                         :}// Sista paret in!
På detta sätt gås kön igenom gång på gång tills inga byten sker mer.

3 Samkörning (5p)

Läs personnumret pnr1 från första filen och personnumret pnr2 från andra filen. Upprepa följande tills någon fil är slutläst.

4 Nya personnummerlagen (10p)

Lämplig sorteringsmetod för en array är insättningssortering. Eftersom vektorn är nästan sorterad redan blir metoden mycket snabb.

Det finns nog inget smart sätt att utnyttja att det gamla binärträdet är nästan sorterat. Man får sortera in dom gamla posterna en efter en i det nya trädet, men man får inte gå igenom det gamla trädet i inordning (från vänster till höger), då blir det nya trädet katastrofalt obalanserat. Pre- eller postordning fungerar bra.

5 Abstrakta pengar (5p)

Datatypen ska kunna ha värden med fjorton heltalssiffror och två decimaler. Viktiga metoder är String toString(), long getKr(), int getÖre(), void addMillions(int mille), void addKr(long kr), void addÖre(int öre), void add(Money x) osv. Den kan implementeras som en
class Money {
  private int mille;                // högst åttasiffrigt
  private int öre  ;                // högst åttasiffrigt
  String tostring(){
  - - - 

6 Syntetisering (10p)

Databasen läses in i poster skapade med new Process() där
class Process               {
  String substans1,substans2;
  double utbyte             ;}
och hashas med substans1 som söknyckel. Problemträdet byggs upp av typen
class Node       {
  String substans;
  double  massa  ;
  Node fader     ;}
och metoden void makesons(Node far) söker far.substans i hashvektorn och skapar alla söner (med massan utbyte*far.massa). Sönerna läggs i en trappa (prioritetskö) där översta positionen har största massan och får föda söner först. Det blir alltså en bästa-först-genomgång av problemträdet.

Om flera positioner har samma substans är det bara den med största massan som är intressant, övriga är dumsöner och kan kasseras. För detta ändamål sparas rekordpositionerna i en annan hashvektor. Speciellt lägger man märke till rekordet för slutsubstansen - när översta posten i trappan har lägre massa än så är algoritmen klar och alla steg kan återskapas via rekordpositionens faderspekare etc.

7 Hashning av substanser (5p)

Hashvektorn bör gärna ha cirka femtio procent luft, så lämplig storlek kan vara primtalet 14999. Bra hashfunktion beräknas i en slinga med
h:=(256*h+k-te tecknet i den kemiska formeln) % 14999.

8 Snabbsortering (5p)

När N växte från tusen till tiotusen tog Tottes sortering 100 gånger så lång tid (urvalssorteringens komplexitet är proportionell mot N i kvadrat) men Tildas bara 13 gånger så lång tid. N log N växer ju från cirka 10000 till cirka 132000. (log 8000 = 13 och log 16000 = 14). Tottes sortering tog alltså nu nästan åtta gånger så lång tid som Tildas.
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 29 april 1999
Tekniskt stöd: <webmaster@nada.kth.se>