studiehandbok@lith
 

Tekniska högskolan vid Linköpings universitet

 
 
År : 2017
 
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.



Undervisningsspråk är Svenska.
Institution: MAI.
Studierektor: Ingegerd Skoglund
Examinator: Kaj Holmberg
Länk till kurshemsida på kursgivande institution
Ansvarig programnämnd: Data&Medie

Engelsk kursplan


Tekniska högskolan vid Linköpings universitet


Informationsansvarig: TFK , val@tfk.liu.se
Senast ändrad: 08/26/2016