Sök i kursutbudet

Använda sökfunktionen för att hitta i Chalmers utbildningsutbud, både vad gäller kurser och program. När det finns en kurshemsida visas en hus-symbol som leder till denna sida.
Sök program och utbildningsplaner


Institutionernas kurser för doktorander

Kursplan för

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

Kursen är full.
Undervisningsspråk: Svenska
Sökbar för utbytesstudenter: Nej

Kursmoment   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0105 Tentamen 6,0hp Betygskala: TH   6,0hp   07 Jun 2019 em L,  12 Okt 2018 em L,  30 Aug 2019 fm L
0205 Inlämningsuppgift 1,5hp Betygskala: UG   1,5hp    

I program

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

Examinator:

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 inklusive obligatoriska moment

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


Publicerad: to 02 sep 2010. Ändrad: må 16 jul 2018