TDDD20 Konstruktion och analys av algoritmer 2009

studiehandbok@lith

Tekniska högskolan vid Linköpings universitet

År : 2009

TDDD20	Konstruktion och analys av algoritmer, 4 p / 6 hp /Design and Analysis of Algorithms/ För: C COM D I Ii IT Mat MMAT
	Prel. schemalagd tid: 30 Rek. självstudietid: 130
	Utbildningsområde: Teknik Ämnesgrupp: Datateknik Nivå (A-D):D Huvudområde: Datateknik, Datavetenskap, Informationsteknologi Nivå (G1,G2,A): A
	Datavetenskap Datavetenskap, datalogi.
	Mål: 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.
	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 Edition, The MIT Press, ISBN 0-262-03293-7.
	Examination:
TEN1	En skriftlig tentamen (U,3,4,5)	6 hp

Undervisningsspråk är Svenska.
Institution: IDA.
Studierektor: sas-sr@ida.liu.se
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 2009 enligt beslut av ansvarig programnämnd/fakultetstyrelse.

Tekniska högskolan vid Linköpings universitet
Informationsansvarig: TFK , val@tfk.liu.se Senast ändrad: 09/17/2009