| 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
|
| |
|
|