KURSPLAN

Algoritmer 7,5 Högskolepoäng

Algorithms
Avancerad nivå, D7009E
Version
Kursplan gäller: Vår 2017 Lp 3 - Tillsvidare
Vald version visar för vilken termin och läsperiod som denna kursplanen gäller för. Senaste version visas först.

Kursplanen fastställd
av Institutionen för systemteknik 2007-02-28

Reviderad
av Jonny Johansson, HUL SRT 2016-06-15

Utbildningsnivå
Avancerad nivå
Fördjupningskod
A1N
Betygskala
G U 3 4 5
Ämne
Datalogi
Ämnesgrupp (SCB)
Datateknik

Behörighet

Kursen förutsätter kunskaper i grundläggande algoritmer och datastrukturer, och diskret matematik motsvarande de som kurserna D0012E och M0009M ger.


Urval

Urvalet grundas på 20-285 högskolepoäng



Mål/Förväntat studieresultat

Kursen mål är att ge färdigheter i konstruktion och effektivitetsanalysav algoritmer och datastrukturer, fördjupad kunskap om algoritmiska metoder för problem på mängder, grafer, aritmetik, nätverk, och geometri, samt orientering om beräkningskomplexitet av olika problem.

 Efter kurs ska studenten kunna

  • visa kunskap omden vetenskapliga grunden för att utveckla och analysera algoritmer och datastrukturer omfattande kunskap om dess beprövade erfarenhet
  • visa förmåga attutveckla, analysera och kritiskt utvärdera olika algoritmiska lösningarmed avseende på korrekthet, effektivitet, och pålitlighet
  • visa förmåga att identifiera, formulera och hantera problem med hög komplexitet genom att konstruera datorprogram som effektivt utnyttjar datorresurs
  • visa kunskap om matematiska verktyg för analys av algoritmer
  • visa förmåga att planera och, med adekvata metoder, genomföra kvalificerade uppgifter inom givna ramar
  • visa förmåga att modellera, förutsäga och utvärdera skeenden även med begränsad information


Kursinnehåll

Algoritmanalys: korrekthet och effektivitet, amorterad och kompetitivitetanalys.
Algoritmkonstruktionsprinciper: dynamisk programmering, approximation, augmenterad datastrukturer, probabilistiska, dynamiska, parallella,och on-line algoritmer.
Beräkningskomplexitet: effektivitetsmått, övre och undre gränser, reduktionsbegreppet, komplexitetsklasserna P, NP, och NP-fullständiga problem.


Genomförande

Undervisningen består huvudsakligen av föreläsningar. Under tiden kursen ges kan det förekomma hemuppgifter som ger bonuspoäng på den tentamen som följer direkt efter kursen.


Examination

Skriftlig tentamenmed differentierade betyg.


Övrigt

Kursen kan ej kombineras i examen med
SMD 073, SMD087, SMD141, och SMD160.

Examinator
Jingsen Chen

Litteratur. Gäller från Höst 2012 Lp 1 (Kan ändras fram till 10 veckor innan studiestart)
Th. H Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein: Introduction to Algorithms (Third Edition) ISBN 0-262-03384-4, 978-0-262-03384-8, MIT Press, 2009.
Vetenskapliga uppsatser (bestäms vid tillfället).

Kursgivare
Institutionen för system- och rymdteknik

Prov
ProvnrTypHpBetyg
0001Tentamen7.5G U 3 4 5

Studiehandledning
Studiehandledning finns i lärplattformen Canvas före kursstart. Du som är ny student hittar all information du behöver på www.ltu.se/nystudent. Du som redan studerar vid Luleå tekniska universitet hittar information om kursstart via schema på studentwebben alternativt via kursrummet i lärplattformen. Du når lärplattformen via Mitt LTU.