| TAOP19 | KOMBINATORISK OPTIMERING, fortsättningskurs, 4 poäng /Combinatorial Optimization, advanced course/ För: D4, C4 | |
| Utbildningsområde: Naturvetenskap Ämnesgrupp: Matematik | ||
| Fördjupningsnivå: D | ||
| Klassning för datavetenskaplig examen: Datavetenskap | ||
| Mål: Kursen utgör en komplettering till TAOP13 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 kombinato riska problem (III) färdighet i att modifiera existerande standardalgoritmer för att lösa nya problem (IV) orientering i parallella kombinatoriska algoritmer.Förkunskaper: TAOP13 Kombinatorisk optimering, grundkurs.Organisation: Föreläsningarna behandlar den för algoritmutvecklingen erforderliga matematiska teorin. Lektionerna ägnas åt övningar i modellformulering och problem lö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, lokal-sökning och metaheuristiker.Kurslitteratur: Meddelas vid kursstart. | ||
| LAB 1 | En laboration. | |
| TEN 1 | En skriftlig tentamen omfattande problemformulering, problemlösning samt teorifrågor. | |