| TTIT33 | TEMA 3, ALGORITMER OCH OPTIMERING, 6,5 poäng /Algorithms and Optimization/ För: IT2 | |
| Utbildningsområde: Naturvetenskap Ämnesgrupp: Matematik/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. Kunna genomföra en argumenterande muntlig presentation.Förkunskaper: Matematik i termin 1, TTIT31 Programmering.Påbyggnadskurser: TDDA32 Konstruktion och Analys av Algoritmer, TAOP19 Kombinatorisk Optimering fortsättningskurs.Organisation: Se studiehandboken, del 1. 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). Kommunikationsstrimman: Den muntliga presentationens olika syften (informerande, argumenterande osv). Kroppsspråk. Kurslitteratur: Enligt litteraturlista.Examination: | ||
| LAB 1 | En laborationsserie. | |
| UPG 1 | Muntlig presentation. | |
| TEN1 | Skriftlig/muntlig tentamen | |
| Endast betyg godkänd ges på Tema 3. I följande moment ges slutbetyg när tema 3 är godkänt. Moment 1 Kombinatorisk optimering, termin 3, graderat betyg. Moment 2 Datastrukturer och algoritmer, termin 3, graderat betyg. I följande moment ges slutbetyg när tema 1, tema 3 och tema 4 är godkända. Moment 3 Kommunikationsstrimman, termin 3, betyg G. | ||