TDDA32 Konstruktion och analys av algoritmer 2007

studiehandbok@lith

Tekniska högskolan vid Linköpings universitet

År : 2007

TDDA32	Konstruktion och analys av algoritmer, 3,5 p / 5 hp /Design and Analysis of Algorithms/ För: C D I Ii IT
	Prel. schemalagd tid: 30 Rek. självstudietid: 103
	Utbildningsområde: Teknik Ämnesgrupp: Datalogi, 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, Logik, Datastrukturer och algoritmer. Grundläggande kunskaper i sannolikhets- 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)	3,5 p	/	5 hp

Undervisningsspråk är Svenska.
Institution: IDA.
Studierektor: sas-sr@ida.liu.se
Examinator: Peter Jonsson
Länk till kurshemsida på kursgivande institution
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 2008 enligt beslut av ansvarig programnämnd/fakultetstyrelse.

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