Sök i programutbudet

Använd sökfunktionen för att leta efter kurser och program i Chalmers utbildningsutbud. Den programplan och utbildningsplan som avser dina studier är i allmänhet från det läsår du började dina studier.

​​​​​​​​​​​​​

Kursplan för

Läsår
LET375 - Algoritmer och datastrukturer
 
Kursplanen fastställd 2009-02-26 av programansvarig (eller motsvarande)
Ägare: TIDAL
7,5 Högskolepoäng
Betygskala: TH - Fem, Fyra, Tre, Underkänt
Utbildningsnivå: Grundnivå
Huvudområde: Datateknik, Informationsteknik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Undervisningsspråk: Svenska

Kursmoment   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0105 Tentamen 6,0hp Betygskala: TH   6,0hp   05 Jun 2015 em L,  18 Apr 2015 em L,  25 Aug 2015 fm L
0205 Inlämningsuppgift 1,5hp Betygskala: UG   1,5hp    

I program

TKELT ELEKTROTEKNIK, CIVILINGENJÖR, Årskurs 3 (obligatoriskt valbar)
TKIEK INDUSTRIELL EKONOMI, CIVILINGENJÖR - Informationsteknik, Årskurs 2 (obligatorisk)
TIDAL DATAINGENJÖR, Årskurs 2 (obligatorisk)

Examinator:

Univ lektor  Uno Holmer


  Gå till kurshemsida

 

Behörighet:

För kurser på grundnivå inom Chalmers utbildningsprogram gäller samma behörighetskrav som till de(t) program där kursen ingår i programplanen.

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

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


Publicerad: fr 26 nov 2010. Ändrad: må 28 nov 2016