studiehandbok@lith
 

Tekniska högskolan vid Linköpings universitet

 
 
År : 2016
 
TDDD20 Konstruktion och analys av algoritmer, 6 hp
/Design and Analysis of Algorithms/

För:   D   DAV   I   Ii   IT   MMAT  

 

Prel. schemalagd tid: 30
Rek. självstudietid: 130

  Utbildningsområde: Teknik

Huvudområde: Datateknik, Datavetenskap, Informationsteknologi   Nivå (G1,G2,A): A

  Datavetenskap Datavetenskap, datalogi.

  Mål:  IUAE-matris
Kursen syftar till att studenterna ska förvärva fördjupade kunskaper om tekniker för att konstruera och analysera algoritmer. Efter avslutad kurs ska studenterna kunna:
  • konstruera algoritmer för ett givet beräkningsproblem
  • bevisa korrekthet för en given algoritm
  • analysera och värdera algoritmer för ett givet beräkningsproblem


  Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan)
Diskret matematik och logik, grundlägande datastrukturer och algoritmer. Grundkunskaper i sannolikhetslära och optimeringslära.

OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.

  Påbyggnadskurser
Algoritmisk problemlösning

  Organisation:
Under föreläsningarna presenteras teorin och exempel ges på hur olika problem kan lösas algoritmiskt. Dessutom ges möjligheter för studenterna att öva på konstruktion och analys av algoritmer.

  Kursinnehåll:
Kursens innehåll består av tre huvuddelar:
  • Del 1: Grundläggande tekniker. Giriga algoritmer, dekomposition och dynamisk programmering.
  • Del 2: NP-fullständighet. Teorin för NP-fullständighet och dess konsekvenser.
  • Del 3: Inexakta metoder. Konstruktion och analys av approximationsalgoritmer och randomiserade algoritmer.


  Kurslitteratur:
Cormen, T.H., Leiserson, C.E., Rivest, R.L. och Stein, C.: Introduction to Algorithms: Second or Third Edition, The MIT Press.

  Examination:
TEN1
En skriftlig tentamen (U,3,4,5)
6 hp
 



Undervisningsspråk är Svenska.
Institution: IDA.
Studierektor: Ahmed Rezine
Examinator: Peter Jonsson
Ansvarig programnämnd: Data&Medie

Engelsk kursplan

Kursen bedrivs på ett sådant sätt att både mäns och kvinnors erfarenhet och kunskaper synliggörs och utvecklas.

Planering och genomförande av kurs skall utgå från kursplanens formuleringar. Den kursvärdering som ingår i kursen skall därför genomföras med kursplanen som utgångspunkt.

Om inget annat anges ovan gäller betygsskala enligt avsnitt a8.5 i de gemensamma bestämmelserna.

Kursplanen gäller för 2016 enligt beslut av ansvarig programnämnd/fakultetstyrelse.

Tekniska högskolan vid Linköpings universitet


Informationsansvarig: TFK , val@tfk.liu.se
Senast ändrad: 06/09/2016