Algoritmer og datastrukturer

Algoritmer

• Ordet algoritme kommer fra etternavnet til matematikeren og astronomen Al-Khwarizmi (ca. 780-850)
• En algoritme er en beskrivelse av de operasjonene som skal til for å løse en bestemt oppgave - en oppskrift.
• Som regel er det slik at en oppgave kan løses på flere forskjellige måter, det vil si - det finnes flere algoritmer som løser samme oppgave. For eksempel finnes det mange algoritmer for å sortere elementene i en tabell. En gitt algoritme kan igjen implementeres (programmeres) på flere måter.
• Legg merke til at denne definisjonen ikke begrenser algoritmer til datamaskinenes verden. Vi omgir oss med algoritmer hele dagen, vi bruker de for å pusse tennene og til å ta ut penger i minibanken. Algoritmer kan beskrives i et hvilket som helst slags språk, både Swahili og Java duger. Det viktigste er at vi beskriver en algoritme på en utvetydig måte, slik at alle de (personer eller datamaskiner) som utfører algoritmen vil gjøre eksakt det samme, og at algoritmen virker på samme måte selv om vi endrer dataene (materialene) algoritmen arbeider ut fra. De fleste dataprogrammer, med unntak av de som er basert på visse teknikker innen kunstig intelligens, utfører sine oppgaver ved hjelp av algoritmer.
• Legg også merke til at en algoritme må ha en klar stoppbetingelse. Hvis ikke risikerer vi å gå inn i en evig løkke, algoritmen terminerer aldri, og løser dermed ikke problemet vårt.

Beskrivelse av algoritmer

Algoritmer som skal utføres av en datamaskin kan beskrives på forskjellige måter:

• Pseudokode - fri tekst - kvasikode
• Programkode

Hva man bruker, er avhengig av formålet. Med pseudokode kan det være lettere å få frem de store linjene der hvor eksakt kode blir for detaljert. På den andre siden kan pseudokode lett bli for unøyaktig, og det innføres tvetydigheter. Ofte brukes en kombinasjon av de to beskrivelsesteknikkene.

Effektivitet

• Vi skal også se på hvor effektive algoritmene er. Effektiviteten til en algoritme kan måles i antall (dominerende) operasjoner som utføres i algoritmen, og kan ofte uttrykkes som en funksjon av problemets størrelse, N (for eksempel antallet elementer i en tabell som skal sorteres).
• Et eksempel på en algoritme som er korrekt, men lite effektiv er Boblesorteringsalgoritmen. Den er forholdsvis enkel å forstå og å implementere, men bruker uforholdsmessig mange operasjoner på å utføre oppgaven.

Datastrukturer

• En datastruktur er den måten en samling data er organisert på.
• En algoritme vil vanligvis være knyttet til datastruktur. Hvis vi for eksempel skal søke etter en verdi i en samling verdier, er det opplagt at søkemetoden avhenger av måten verdiene er organisert på.
• Ligger for eksempel verdiene i en uordnet tabell, har vi ikke noe annet valg enn å starte på begynnelsen av tabellen og se på ett og ett element helt til vi eventuelt finner verdien vi søker etter. Det er med andre ord ikke mulig å søke på en effektiv måte.
• Vi skal i løpet av kurset se på andre måter å organisere dataene på som gjør det mulig å søke etter verdier på en effektiv måte.

Datastrukturer - II

Relasjonene danner en ordning av elementene ved å definere hvilke naboer de har. Et slikt naboskap kalles gjerne for topologi. Vi skiller mellom tre hovedtyper topologier:

1. Lineære (en-til-en) strukturer.
   Brukes når man har en mengde elementer ordnet i rekkefølge. En noe kan ha to typer relasjoner, en referanse til forrige node og en til neste.
2. Hierarkiske (en-til-mange) strukturer.
   En node kan ha flere etterfølgende noder (barn), men kun en forrige node (forelder).
3. Nettverk (mange-til-mange).
   Dannes når relasjonene ikke er orndet på noen regulær måte. Det finnes ingen forrige- eller neste-relasjoner, og heller ingen foreldre/barn-relasjoner. Hver node kan derimot kan derimot ha et vilkårlig antall naboer.

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.

Faget er grunnleggende

• 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.