Hoppa till innehållet


KURSPLAN

Algoritmer 7,5 högskolepoäng

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


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

Behörighet

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


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 effektivitetsanalys av 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 om den vetenskapliga grunden för att utveckla och analysera algoritmer och datastrukturer omfattande kunskap om dess beprövade erfarenhet
  • visa förmåga att utveckla, analysera och kritiskt utvärdera olika algoritmiska lösningar med 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 kompetitivitet analys.
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
Kursens undervisningsspråk samt undervisningsform anges för varje kurstillfälle och framgår av kurssidan på Luleå tekniska universitets hemsida.

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
Om det finns beslut om särskilt pedagogiskt stöd, i enlighet med Riktlinjen Studentens rättigheter och skyldigheter vid Luleå tekniska universitet, finns möjlighet till anpassad eller alternativ examinationsform.

Skriftlig tentamen med 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 (SRT)

Moduler
KodBenämningBetygskalaHPTillståndGäller frånTitel
0002Skriftlig tentamenG U 3 4 57.50ObligatoriskV22

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.

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

Reviderad
av Jonny Johansson, HUL SRT 2021-02-17