Kursplan för Datastrukturer och algoritmer

Kursplan fastställd 2021-01-22 av programansvarig (eller motsvarande).

Kursöversikt

  • Engelskt namnData structures and algorithms
  • KurskodDAT038
  • Omfattning7,5 Högskolepoäng
  • ÄgareTKDAT
  • 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 Engelska
  • Anmälningskod 49124
  • Max antal deltagare215
  • Sökbar för utbytesstudenterJa
  • Endast studenter med kurstillfället i programplan.

Poängfördelning

0119 Laboration 3 hp
Betygsskala: UG		 3 hp
0219 Tentamen 4,5 hp
Betygsskala: TH		 4,5 hp
  • 13 Jan 2022 em J
  • 15 Mar 2022 em J
  • 18 Aug 2022 fm J
  • 04 Jun 2022 fm J

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 programmering motsvarande minst 7,5hp, inklusive rekursiva funktioner och metoder. Grundläggande matematiska begrepp, såsom mängder, funktioner, relationer, grafer, logaritmer och induktionsbevis.

Syfte

Datastrukturer och algoritmer utgör fundamentala byggstenar i nästan alla programvaror. Kunskaper och färdigheter i dataabstraktion, datastrukturer och algoritmer är nödvändiga vid konstruktion, användning och underhåll av förändringsbara, återanvändbara, korrekta och effektiva programkomponenter.

Kursen ger kunskaper och färdigheter i konstruktion och användning av algoritmer och datastrukturer, introduktion till algoritmanalys och dataabstraktion, samt insikter i fördelarna med dataabstraktion vid programutveckling.

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

Kunskap och förståelse

  • redogöra för grundläggande abstrakta datatyper och datastrukturer, bland annat listor, köer, hashtabeller, träd och grafer
  • redogöra för några av de algoritmer som används för att effektivt hantera dessa datastrukturer, och förklara varför de är korrekta

Färdigheter och förmåga

  • tillämpa grundläggande abstrakta datatyper och datastrukturer, samt algoritmer relaterade till dessa
  • implementera och använda abstrakta datatyper som gränssnitt, och datastrukturer som klasser, i ett objektorienterat programmeringsspråk
  • använda ett standardbibliotek för datastrukturer och algoritmer
  • läsa, specificera och beskriva algoritmer, på en högre abstraktionsnivå än programkod

Värderingsförmåga och förhållningssätt

  • analysera effektivitet hos grundläggande algoritmer och datastrukturer
  • göra välgrundade val mellan olika datastrukturer och algoritmer för olika tillämpningar

Innehåll

Följande ämnen täcks av kursen:
  • abstrakta datatyper
  • vanliga datastrukturer, såsom fält (arrayer), länkade listor, obalanserade och balanserade träd, heapar och hashtabeller
  • hur dessa kan användas för att implementera abstrakta datatyper, såsom stackar, köer, prioritetsköer, avbildningar, mängder och grafer
  • standardalgoritmer för dessa datastrukturer, inklusive deras resurskrav
  • söknings- och sorteringsalgoritmer
  • standardbibliotek för datastrukturer och algoritmer
  • asymptotisk effektivitet och enkel komplexitetsanalys av datastrukturer och algoritmer

Organisation

Undervisningen består av föreläsningar, grupparbete, övningar och handledning i samband med övningarna.

Litteratur

Se kursens hemsida.

Examination inklusive obligatoriska moment

Kursen examineras genom en skritlig salstentamen, och inlämningsuppgifter som normalt genomförs i mindre grupper.

Kursens examinator får examinera enstaka studenter på annat sätt än vad som anges ovan om särskilda skäl föreligger, till exempel om en student har ett beslut från Chalmers om pedagogiskt stöd på grund av funktionsnedsättning.