| TAOP13 | KOMBINATORISK OPTIMERING, grundkurs, 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: Datavetenskap | ||
| 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: TAOP19 Kombinatorisk optimering, fortsättningskurs.Organisation: Föreläsningarna behandlar den för algoritmutvecklingen erforderliga matema tiska teorin. Lektionerna ägnas åt övningar i modellformulering och problem lö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. | |