Løsningsforslag til kapittel 1

Oppgave 1a

Hvilke egenskaper gjelder?

Personene til venstre for venstre hånd er sortert alfabetisk, og de er alle alfabetisk mindre enn resten.

Oppgave 1b

Maksimalt antall ombyttinger?

Hvis rekken er sortert synkende (omvendt sortert) blir det bytter for hver eneste sammenligning. Følgende viser første "gjennomløp" med høyre hånd for en rekke med fire tall (venstre hånd peker på plass 1 hele tiden):

8 - 5 - 4 - 2
5 - 8 - 4 - 2
4 - 8 - 5 - 2
2 - 8 - 5 - 4

Når N=4 får vi altså N-1=3 bytter for å få på plass det minste tallet i plass 1. Merk at tallene fra og med posisjon 2 er omvendt sortert (5 - 4 - 2). Deretter må vi bruke N-2=2 bytter for å få riktig tall i plass 2, og N-3=1 bytter for å få riktig tall i plass 3. Det siste tallet er da nødvendigvis også korrekt plassert. Det betyr (N-1) + (N-2) + ... + 1 = N ×(N-1)/2 bytter. Dette er for øvrig en meget ineffektiv sorteringsalgoritme.

Oppgave 2

Lagringsplass for databasen til Hobbyhuset?

For å svare på denne oppgaven tar vi utgangspunkt i tabelldefinisjonene i vedlegg B. Basert på datatypene til kolonnene kan vi regne ut plassbehovet for én enkelt rad. Deretter anslår vi antall rader i hver tabell for å beregne samlet plassbehov for databasen.

Vi må først finne plassbehovet for enkeltverdier i ulike datatyper. Vi tar utgangspunkt i dokumentasjonen for MySQL, og setter opp følgende forenklede tabell for de datatypene som brukes i Hobbyhuset:

Vi antar her at hvert tegn lagret som tekst krever 1 byte. Dette avhenger av hvilke tegnsett som er valgt. Hvis slike data lagres som Unicode vil hvert tegn kreve minst 2 byter, og noen tegn som mye som 4 byter.

Plassbehovet for verdier i datatypen DECIMAL(p,s) avhenger av totalt antall siffer p og antall plasser etter desimalpunktum s. I Hobbyhuset blir denne datatypen kun brukt for å lagre beløp og da hele veien som DECIMAL(8, 2). Vi går ikke nærmere inn på hvordan plassbehovet for denne datatypen er generelt, og antar bare at DECIMAL(8, 2) krever 8 byter.

Vi antar videre at data blir lagret "tett", ved at vi multipliserer plassbehovet for én rad med anslått antall rader for å finne plassbehovet for en tabell. Dette er ikke realistisk - forklaring følger i kapittel 9.

Totalt vil databasen dermed kreve ca. 1 151 690 byter ≈ 1.2 MB.

Oppgave 3

Eksempeltabeller for universitetsdatabase.

Også på denne oppgaven er det mange mulige svar. Løsningen under fokuserer på ansatte, studenter og kurs, men et universitet må også lagre mange andre typer av informasjon. Vi nøyer oss med noen få eksempelrader for hver tabell.

Merk hvordan visse verdier går igjen i flere tabeller, f.eks. finner vi igjen både studentnumre og kurskoder i tabellen Karakter. Dette gjøres for at tabellene skal henge logisk sammen.

Tabell Ansatt

 

Tabell Studium

 

Tabell Kurs

 

Tabell KursStudium

 

Tabell Student

 

Tabell Karakter

 

Oppgave 4

Oversett 10000111 fra 2-tallsystemet til 10-tallsystemet.

1 × 2⁷ + 0 × 2⁶ + 0 × 2⁵ + 0 × 2⁴ + 0 × 2³ + 1 × 2² + 1 × 2¹ + 1 × 2⁰
= 128 + 0 + 0 + 0 + 0 + 4 + 2 + 1
= 135

 

Oppgave 5

Oversett 204 fra 10-tallsystemet til 2-tallsystemet.

Boken gir ingen oppskrift på hvordan man går fram, så her måtte man enten slå opp i en gammel matte-bok, søke på nettet, eller tenke ut en framgangsmåte selv.

Framgangsmåte: Heltallsdivider tallet på 2 og sjekk om det gir (1 til) rest. I så fall skal siste siffer være 1, og ellers 0. Fortsett på samme måte med toerplassen, firerplassen, åtterplassen osv., helt til resultatet av divisjonen blir 0.

204 i 10-tallsystemet blir altså 11001100 i 2-tallsystemet, som vi kan dobbeltsjekke ved å oversette tilbake: 128 + 64 + 8 + 4 = 204.