| TAOP13 | Kombinatorisk optimering gk, 3,5 poäng /Combinatorial Optimization, introductory course/ För: D3, C3 | |
| Utbildningsområde: Naturvetenskap Ämnesgrupp: Matematik | ||
| Fördjupningsnivå: C | ||
| Klassning för datavetenskaplig examen: Matematik, tillämpad matematik. | ||
| Mål: Kursen utgör en inledande kurs i optimeringslära med inriktning mot praktisk behandling av kombinatoriska optimeringsproblem och avser att ge de studerande (I) en exemplifierad orientering om viktiga klasser av kombinatoriska optimeringsproblem (II) färdighet i formulering av problem med hjälp av matematiska modeller samt i att bedöma problemens svårighetsgrad med hjälp av komplexitets teori (III) kunskap om uppbyggnad av effektiva metoder samt färdighet i lösning av kombinatoriska optimeringsproblem.Förkunskaper: Linjär algebra.Påbyggnadskurser: TAOP 19 Kombinatorisk optimering, fortsättningskurs. TDDA32 Konstruktion och analys av algoritmer.Organisation: Föreläsningarna behandlar den för algoritmutvecklingen erforderliga matematiska teorin. Lektionerna ägnas åt övningar i modellformulering och problemlösning. Laborationerna består av övningar i att lösa olika typer av kombinatoriska optimeringsproblem med hjälp av dator.Kursinnehåll: Introduktion till linjär optimering, grafsökning, beräkningskomplexitet, formulering av linjära och diskreta optimeringsproblem, linjärprogrammering, minimalträdsproblem, billigaste vägproblem och närbesläktade problem, trädsökningsprinciper, trädsökning applicerat på handelsresandeproblemet, nätverks problem med fasta kostnader samt kappsäcksproblemet, dynamisk programmering, heuristiker och approximativa metoder.Kurslitteratur: Migdalas, A., Göthe-Lundgren, M.: Kombinatorisk optimering, LiTH 1993. | ||
| TEN1 | En skriftlig tentamen omfattande problemformulering, problemlösning samt teorifrågor., 3,5 p. | |
Undervisningsspråk är svenska.