| TAOP19 | Kombinatorisk optimering, fk, 4 poäng /Combinatorial Optimization, advanced course/ För: D4, C3, C4, IT4 | |
| Utbildningsområde: Naturvetenskap Ämnesgrupp: Matematik | ||
| Fördjupningsnivå: D | ||
| Klassning för datavetenskaplig examen: Matematik, tillämpad matematik. | ||
| Mål: Kursen utgör en komplettering till TAOP 13 med inriktning mot behandling av kombinatoriska problem och lösningsmetoder som kräver djupare insikt i linjärprogrammering och dualitet. Kursen avser att ge de studerande (I) en exemplifierad orientering om viktiga klasser av kombinatoriska optimeringsproblem (II) en utvidgning av kunskapen om optimeringsmetoder för kombinatoriska problem (III) färdighet i att modifiera existerande standardalgoritmer för att lösa nya problem (IV) orientering i parallella kombinatoriska algoritmer.Förkunskaper: TAOP 13 Kombinatorisk optimering, grundkurs.Organisation: Föreläsningarna behandlar den för algoritmutvecklingen erforderliga matematiska teorin. Lektionerna ägnas åt övningar i modellformulering och problemlösning. Laborationen består av övningar i att lösa olika typer av kombinatoriska optimeringsproblem med hjälp av dator.Kursinnehåll: Linjärprogrammering och Simplexmetoden, Dualitet, Primal-dual metod för maxflödesproblemet, Primal-dual metod för transportproblemet, Primal-dual metod för generella matchningsproblem, Brevbärarproblemet, Duala Simplexmetoden, Plansnittningsmetod, Trädsökning applicerat på generella heltalsproblem, Approximativa algoritmer, lokalsökning och metaheuristiker.Kurslitteratur: Meddelas vid kursstart. | ||
| TEN1 | En skriftlig tentamen omfattande problemformulering, problemlösning samt teorifrågor. , 3,5 p. | |
| LAB1 | En laboration., ,5 p. | |
Undervisningsspråk är svenska.