| TTIT33 | Tema 3: Algoritmer och Optimering, 6,5 poäng /Algorithms and Optimization/ För: IT2 | |
| Utbildningsområde: Naturvetenskap/teknik Ämnesgrupp: Optimeringslära/Datalogi | ||
| Fördjupningsnivå: 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 optimerings problem 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: Matematik i termin 1, TTIT 31 Programmering.Påbyggnadskurser: TDDA 32 Konstruktion och Analys av Algoritmer, TAOP 19 Kombinatorisk Optimering fortsättningskurs.Organisation: Se studiehandboken, del 1. Vissa kursmoment integreras med TTIT36 Kommunikation IT.Kursinnehåll: Grundläggande linjärprogrammering, 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. | ||
| TEN1 | Skriftlig/muntlig tentamen, 4 p. | |
| LAB1 | En laborationsserie., 2,5 p. | |
| MOM1 | Kombinatorisk optimering termin 3 graderade betyg , 0 p. | |
| MOM2 | Datastrukturer och algoritmer, termin 3, graderat betyg., 0 p. | |
| Endast betyg godkänd ges på Tema 3. | ||
Undervisningsspråk är svenska.