Sök i programutbudet

Använd sökfunktionen för att leta efter kurser och program i Chalmers utbildningsutbud. Den programplan och utbildningsplan som avser dina studier är i allmänhet från det läsår du började dina studier.

​​​​​​​​​​​​​

Kursplan för

Läsår
TDA206 - Discrete optimization
 
Kursplanen fastställd 2012-02-18 av programansvarig (eller motsvarande)
Ägare: MPALG
7,5 Poäng
Betygskala: TH - Fem, Fyra, Tre, Underkänt
Utbildningsnivå: Avancerad nivå
Huvudområde: Datateknik, Informationsteknik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Undervisningsspråk: Engelska
Sökbar för utbytesstudenter
Blockschema: A

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs Ej Lp
0101 Tentamen 7,5 hp Betygskala: TH   7,5 hp   Kontakta examinator,  Kontakta examinator

I program

MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Årskurs 1 (valbar)
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Årskurs 1 (obligatoriskt valbar)
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Årskurs 2 (valbar)
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Årskurs 1 (obligatoriskt valbar)

Examinator:

Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke


Kursutvärdering:

http://document.chalmers.se/doc/afaddcd6-ec8c-49ea-8c9f-1028bc718c8d


  Gå till kurshemsida

Behörighet:

För kurser inom Chalmers utbildningsprogram gäller samma behörighetskrav som till de(t) program kursen ingår i.

Kursspecifika förkunskaper

A basic course in Optimization or Operational Research. A basic course in Algorithms is recommended.

Syfte

The topic of the course is the theory and practice of optimization problems over discrete structures, and has strong connections to Optimization Theory (linear programming), Computer Science (algorithms and complexity), and Operational Research. Problems of this kind arise in many different contexts including transportation, telecommunications, industrial planning, finance, bioinformatics, hardware design and cryptology.
A characteristic property of these problems are that they are difficult to solve. The course intends to develop the skill of modelling real problems and to use mathematical and algorithmic tools to solve them, optimally or heuristically.

Lärandemål (efter fullgjord kurs ska studenten kunna)

- identify optimization problems in various application domains,
- formulate them in exact mathematical models that capture the essentials
of the real problems but are still manageable by computational methods,
- assess which problem class a given problem belongs to,
- apply linear programming, related generic methods, and additional
heuristics, to computational problems,
- explain the geometry of linear programming,
- dualize optimization problems and use the dual forms to obtain bounds,
- work with the scientific literature in the field.

Innehåll

modelling, linear programs and integer linear programs, polytopes, duality in
optimization, branch-and-bound and other heuristics, some special graph
algorithms

Organisation

Lectures and homework assignments.

Litteratur

See separate literature list.

Examination

Assignments and home exam. Grading scale U, 3, 4 or 5.


Sidansvarig Publicerad: on 24 jan 2018.