| TTIT33 |
Tema: Algoritmer och optimering, 6,5 p
/Algorithms and Optimization/ |
||
|
Utbildningsområde: Naturvetenskap Ämnesgrupp: Optimeringslära/Datalogi/Datateknik Nivå (A-D):B |
|||
|
Mål:
Färdighet i att modellera kombinatoriska optimeringsproblem matematiskt och att bedöma problemens svårighetsgrad med hjälp av komplexitetsteori samt kunskap om några välkända typer av kombinatoriska optimeringsproblem och om algoritmer med vilka de effektivt kan lösas. Förståelse av och färdighet i metoder för design och analys av algoritmer samt kännedom om grundläggande abstrakta datatyper och effektiva implementationer av dessa. |
|||
| Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan) TATM18 Linjär algebra, TTIT31 Tema: Programmering, TTIT07 Tema: Diskreta strukturer. 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 TDDA32 Konstruktion och analys av algoritmer, TAOP19 Kombinatorisk optimering fortsättningskurs. |
|||
| Organisation: Se studiehandboken, del 1. Vissa kursmoment integreras med TTIT36 Kommunikation IT. |
|||
| Kursinnehåll: Grundläggande linjärprogrammering och dualitet, problemklassificering, nätverksproblem (algoritmer baserade på grafsökning), billigaste uppspännande trädproblem, trädsökning, icke-optimerande algoritmer (approximativa algoritmer och heuristiker). Tidskomplexitet av algoritmer, abstrakta datatyper (lista, stack, kö, avbildning, träd, mängd, ordbok, prioritetskö, graf) och deras implementationer, sortering och urval, metoder för algoritmdesign (söndra och härska, dynamisk programmering, giriga algoritmer). |
|||
| Kurslitteratur: Enligt litteraturlista. |
|||
| Examination: | |||
| TEN1 LAB2 UPG2 BAS1 |
Skriftlig tentamen En laborationsserie Uppgift och muntlig examination Basgruppsarbete |
4 p 2 p 0,5 p 0 p |
|
Undervisningsspråk är Svenska. Några föreläsningar och tentafrågor kan dock vara på engelska..
Institution: IDA.
Studierektor: sas-sr@ida.liu.se
Examinator:
Länk till kurshemsida på kursgivande institution
Ansvarig utbildningsnämnd: UND
Engelsk kursplan
Om inget annat anges ovan gäller betygsskala enligt avsnitt a8.5 i de gemensamma bestämmelserna.
Kursplanen gäller för 2003.
 |
||||||
| ||||||