Kursplanen är fastställd av styrelsen för matematik
och datavetenskap 1999-10-05.
2. Kursens mål
Datastrukturer används för att modellera verkligheten när man
konstruerar datorprogram. Kursen skall ge goda kunskaper om olika
typer av datastrukturer och hur de används.
Genomgående skall såväl abstrakta egenskaper som representation
i programspråk behandlas liksom också vanligt förekommande algoritmer
i anslutning till dem.
En algoritm är en lösningsmetod för ett problem, t ex sortering. Den
beskriver, steg för steg, hur man skall gå tillväga för att lösa
problemet. Algoritmkonstruktion och problemlösning är till stor del
synonyma begrepp och övning i problemlösning är en viktig ingrediens
i kursen. Kursen avser att ge kunskaper om algoritmer och vilka
egenskaper dessa har samt goda färdigheter i att konstruera, utveckla,
beskriva och analysera algoritmer. Kursen skall också ge kunskaper om
kända algoritmer för olika typer av problem. Slutligen skall man kunna
analysera algoritmers tids- och minnesbehov vid olika val av
datastrukturer och implementationer och kunna känna igen problem som
har icke polynomisk komplexitet.
Studiet av datastrukturer och algoritmer är centrala områden inom
datalogin.
3. Kursens innehåll
Kursen börjar med att vi lär oss analysera algoritmers komplexitet i
tid och rum -- vi får då en metod att jämföra olika
algoritmer. (Asymptotisk tidskomplexitet, Ordnotation, analys av
rekursiva program).
Eftersom alla algoritmer implementeras med hjälp av någon datatyp så
kommer vi i att ta upp olika datatyper, såväl deras abstrakta
egenskaper som hur man kan representera (realisera) dem i
programspråk. Träd, grafer, prioritetsköer, mängder samt algoritmer
som använder dessa datastrukturer kommer vi att gå igenom
noggrant. (T ex djupet först sökning i träd och grafer. Dijkstras,
Floyds och Kruskals algoritmer m fl)
Olika algoritmer för sortering/sökning (Quicksort, mergesort, heapsort,
bisort).
Det finns ett antal bra metoder för att konstruera algoritmer; några
av dessa skall vi lära oss, bland andra ''divide and conquer'', dynamisk
programmering, ''glupsk'' metod och ''backtracking''.
Trots att datorn kan användas för att lösa många olika problem så
finns det problem som inte alls kan lösas med en dator och det finns
problem som bara går att lösa med väldigt få indata eftersom
beräkningstiden växer exponentiellt med antalet indata. Dessa typer av
problem orienterar vi om. (Beräkningsbarhet, ''intractability'',
NP-kompletta problem m.m.)
4. Undervisningens utformning och omfattning
Undervisningen utgörs av föreläsningar, lektioner och datorlaborationer.
Den lärarledda undervisningen omfattar ca 50 timmar och den totala
arbetsinsatsen ca 200 timmar.
5. Examination
Inlämningsuppgifter samt skriftlig tentamen omfattande både teori och
problemfrågor.
Studerande som ej godkänts vid ordinarie prov erbjuds ytterligare
provtillfällen. På godkänt prov ges betygsgraderna Godkänd
eller Väl godkänd.
