Algoritmer og datastrukturer

Faget er grunnleggende

I dokumentasjonen til de fundamentale Collection-klassene i Java, finner man følgende snutt:

''The Java platform contains two general-purpose List implementations. ArrayList, which is usually the better-performing implementation, and LinkedList which offers better performance under certain circumstances.''

Noe mer om hva slags "circumstances" man snakker om står det ikke noe om, man tar det for gitt at en IT-før person straks skjønner hintet.

Mer fra samme dokumentasjon:

''It is guaranteed to run in n log(n) time and runs substantially faster on nearly sorted lists. Empirical tests showed it to be as fast as a highly optimized quicksort. A quicksort is generally considered to be faster than a merge sort but isn't stable and doesn't guarantee n log(n) performance.''

På samme måte, dette er terminologi man forventer at IT-personer skal beherske. I dette kurset får dere anledning til å lære dere grunnleggende prinsipper og terminologi, som gjelder uavhengig av programmeringsspråk og plattformer:

• I informatikkens verden er algoritmer og datastrukturer som hammer, spiker og planker for snekkeren. Datastrukturer er å regne som materialer og festemidler som vi bygger programvare av, og algoritmene er verktøyene vi bruker. Algoritmene og datastrukturene henger nøye sammen. En algoritme er gjerne knyttet til en eller flere datastrukturer og vice versa.
• I programvareutvikling er kunnskaper om algoritmer og datastrukturen den første og viktigste forutsetningen for et bra resultat. Jo mer kompliserte oppgaver programmene skal utføre, jo viktigere er denne kompetansen.
• I dette kurset skal vi få kjennskap til og erfaring med å bruke et sett med standard algoritmer og standard datastrukturer. Vi skal også få innblikk i hvordan vi for et gitt problem kan velge den mest hensiktsmessige kombinasjonen av datastrukturer og algoritmer.

Faget er viktig

• En oppgave kan løses ved hjelp av "rå (prosessor)kraft" ("brute force"), eller man kan bruke smartere metoder som gjør at oppgaven løses raskt uten unødig bruk av maskinressurser. I anvendelser som involverer store datamengder, i sanntidsproblemer og programmer med intensiv brukerinteraksjon er effektive algoritmer en nødvendighet.
• En klassisk problemstilling er å finne korteste vei gjennom ulike typer nettverk. Tenk deg for eksempel at du skal kjøre bil gjennom en stor, fremmed by, og at du har en datamaskin i bilen som finner den korteste veien fra der du er til dit du skal. Et slikt program kan lages på minst to forskjellige måter:
  1. "Rå kraft":
     Vi prøver alle mulige veier, og velger til slutt den korteste.
  2. En av mange "korteste vei" algoritmer:
     Det finnes et knippe standard algoritmer for å løse slike problemer. Ved å velge den mest hensiktsmessige for dette formålet, og kanskje tilpasse den noe for å få den til å passe inn, vil vi raskt kunne lage programmet.

Faget er klassisk

Informatikken er en ung vitenskap, og mange viktige resultater og teknologiske gjennombrudd er ikke mer enn et par år gamle. I en slik rivende utvikling er det viktig å finne en slags grunnmur som uansett videre utvikling er et like aktuelt fagområde. En del av denne grunnmuren er teorien omkring algoritmer og datastrukter. Donald Knuth skrev tidlig på 70-tallet tre store bind som er av mange blir refert til som programmernes bibel. Dette verket dreier seg i stor grad om temaene for kurset Algoritmer og Datastrukturer.

Faget er nyttig

Dette kurset er ikke bare for de som skal drive med programvareutvikling i en eller annen form. Ved å få oversikt over informatikkens viktigste verktøykasse, blir man bedre skikket til f.eks. å lese spesifikasjoner, kommunisere med programvareutviklere, vurdere hva man trenger av programvare og maskinvare for å løse et spesielt problem i en bedrift osv. Når man i tillegg kan analysere algoritmer og dermed vite hvor raskt et problem kan løses med en gitt metode, og har kunnskap om hvilke typer problemer som ikke kan løses med en datamaskin, så står man mye stødigere i enhver IT-preget jobb.

Programmering

• Kurset bygger på programmeringsferdigheter tilsvarende kursene Innføring i programmering og Objektorientert Programmering.
• Programmeringsspråk er Java.
• Eksamen i kurset kommer til å kreve både teoretiske og praktiske ferdigheter.
• Det er mulig å greie seg gjennom algdat uten å "programmere seg ihjel", men for å oppnå et godt resultat må man regne med å programmere en god del.