| TAOP33 |
Kombinatorisk optimering gk, 4 hp
/Combinatorial Optimization, Introductory Course/
För:
D
U
|
OBS! |
Får ej ingå i examen tillsammans med TAOP07
|
| |
Prel. schemalagd
tid: 42
Rek. självstudietid: 65
|
| |
Utbildningsområde: Naturvetenskap
Huvudområde: Matematik, Tillämpad matematik Nivå (G1,G2,A): G2
|
| |
Datavetenskap Matematik, tillämpad matematik.
|
| |
Mål:
IUAE-matris
Kursen behandlar matematiska verktyg för att lösa och analysera kombinatoriska optimeringsproblem. Fokus ligger på att välja och använda den mest effektiva algoritmen för varje specifik problemstruktur. Algoritmerna är avsedda att implementeras på dator. Efter fullgjord kurs skall studenten kunna:
- redogöra för viktiga klasser av kombinatoriska optimeringsproblem
- formulera kombinatoriska optimeringsproblem som matematiska modeller samt bedöma problemens svårighetsgrad med hjälp av komplexitetsteori
- förklara uppbyggnaden av och principerna bakom effektiva lösningsmetoder samt använda metoderna för att lösa kombinatoriska optimeringsproblem
- använda tillgänglig programvara för att lösa optimeringsproblem
- medverka vid utveckling av ny programvara för optimeringsproblem
- utveckla en enkel heuristik för ett strukturerat kombinatoriskt optimeringsproblem
- förklara och använda grundläggande begrepp, såsom lokal och global optimalitet, konvexitet, extrempunkt, komplexitet, dualitet, grundläggande grafteori samt trädsökning
|
| |
Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan)
Linjär algebra
OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.
|
| |
Organisation:
Föreläsningar och lektioner behandlar teori, metoder och modeller. Tid ägnas även åt övningar i modellformulering och problemlösning. Laborationerna innehåller både implementering av optimeringsalgoritmer och lösning av kombinatoriska optimeringsproblem med hjälp av tillgänglig programvara.
|
| |
Kursinnehåll:
Introduktion till optimering, problemformulering, grafisk lösning, beräkningskomplexitet. Simplexmetoden, linjär dualitet och känslighetsanalys. Grundläggande grafteori, modeller och metoder för att finna billigaste uppspännande träd, billigaste handelsresandetur, billigaste brevbärartur, billigaste väg, minkostnadsflöde samt maxflöde. Metoder för heltalsoptimering, bl.a. trädsökningsmetoder. Problemkomplexitet samt heuristiker.
|
| |
Kurslitteratur:
Kaj Holmberg: Optimering (Liber, 2010).
|
| |
Examination: |
TEN2
LAB2
|
En skriftlig tentamen (U,3,4,5)
Laborationsmoment (U,G)
|
3 hp
1 hp
|
| |
|
Tentamen omfattar problemformulering, problemlösning samt teorifrågor. |
|