Kursplan för Algoritmer och datastrukturer

Kursplan fastställd 2019-02-20 av programansvarig (eller motsvarande).

Kursöversikt

  • Engelskt namnAlgorithms and data structures
  • KurskodLET375
  • Omfattning7,5 Högskolepoäng
  • ÄgareTIDAL
  • UtbildningsnivåGrundnivå
  • HuvudområdeDatateknik, Informationsteknik
  • InstitutionDATA- OCH INFORMATIONSTEKNIK
  • BetygsskalaTH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd

Kurstillfälle 1

  • Undervisningsspråk Svenska
  • Anmälningskod 62121
  • Max antal deltagare120
  • Sökbar för utbytesstudenterNej
  • Endast studenter med kurstillfället i programplan.

Poängfördelning

0105 Tentamen 6 hp
Betygsskala: TH		 6 hp
  • 03 Jun 2021 em L
  • 09 Okt 2020 em L
  • 27 Aug 2021 em L
0205 Inlämningsuppgift 1,5 hp
Betygsskala: UG		 1,5 hp

I program

Examinator

Gå till kurshemsidan (Öppnas i ny flik)

Behörighet

Grundläggande behörighet för grundnivå
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Särskild behörighet

Samma behörighet som det kursägande programmet.
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Kursspecifika förkunskaper

Kunskaper i objektorienterad programmeringsteknik omfattande klasser och objekt, datainkapsling, arv och polymorfism i Java motsvarande DAT050 Objektorienterad programmering. Elementära kunskaper i diskret matematik.

Syfte

Algoritmer och datastrukturer utgör fundamentala byggstenar i de flesta moderna programvaror. Kunskaper och färdigheter i tekniker för konstruktion och analys av algoritmer är viktiga verktyg vid produktion av korrekta och effektiva program. Förtrogenhet med begreppen dataabstraktion och datastruktur är nödvändig vid konstruktion, användning och underhåll av förändringsbara och återanvändbara programkomponenter. Kursen skall ge kunskaper och färdigheter i konstruktion och användning av algoritmer och datastrukturer, introduktion till olika tekniker för analys av algoritmer, samt insikter i fördelarna med dataabstraktion vid programutveckling.

Lärandemål (efter fullgjord kurs ska studenten kunna)

  • Använda olika algoritmtekniker som problemlösningsverktyg vid programkonstruktion.
  • Göra enkla analyser av algoritmers och datastrukturers resurskrav.
  • Använda olika datastrukturer och känna till viktiga tillämpningar.
  • Använda standardbibliotek för datastrukturer och algoritmer.
  • Implementera egna datastrukturer i ett objektorienterat språk.

Innehåll

I kursen används Java som programmeringsspråk.
  • Algoritmtekniker: Iterativa och rekursiva algoritmer, induktionsbevis, divide and conquer, backtracking, dynamisk programmering.
  • Analys av algoritmers och datastrukturers resurskrav med avseende på beräkningstid och minnesbehov. Asymptotisk komplexitet, genomsnittlig komplexitet och värsta-fall-komplexitet.
  • Linjär- och binärsökning.
  • Olika sorteringsalgoritmer och deras egenskaper.
  • Begreppen abstrakt datatyp och datastruktur.
  • Datastrukturer: Vektorer, strängar, stackar, köer, listor, träd, binära sökträd, hashtabeller, prioritetsköer, grafer, mängder. Vanliga användningsområden. Typiska egenskaper och tidskomplexitet för strukturernas operationer.
  • Standardiserade algoritmer och klasser för datastrukturer.
  • Implementering av datastrukturer.

Organisation

Undervisningen sker i form av föreläsningar och handledda övningar. Övningarna består dels i att analysera och modifiera givna program, dels i att konstruera egna program. Vissa av uppgifterna är obligatoriska och redovisas med skriftlig dokumentation. Stor vikt läggs vid de studerandes egen aktivitet i kunskapsinhämtandet.

Litteratur

Weiss, M.A., Data structures and problem solving using Java, Addison-Wesley. Upplaga meddelas vid kursstart, eller på förfrågan hos examinatorn.

Examination inklusive obligatoriska moment

Obligatoriska inlämningsuppgifter och skriftlig tentamen. Slutbetyg i skala 3-5 ges efter godkända inlämningsuppgifter och baseras på tentamen.