MAT-72606 Approximation Algorithms, 4 cr

Lisätiedot

Suitable for postgraduate studies.

Vastuuhenkilö

Tapio Elomaa

Opetus

Toteutuskerta Periodi Vastuuhenkilö Suoritusvaatimukset
MAT-72606 2016-01 4 Tapio Elomaa

Osaamistavoitteet

After completion of the course the student will appreciate the approach of approximating the solution of computationally difficult problems. Examples of combinatorial algorithms and linear programming based algorithms are familiar for the student.

Sisältö

Sisältö Ydinsisältö Täydentävä tietämys Erityistietämys
1. Greedy algorithms and local search     
2. Rounding data and dynamic programming     
3. Deterministic rounding of linear programs     
4. Random sampling     
5. Randomized rounding of semidefinite programs     
6. The primal-dual method     

Ohjeita opiskelijalle osaamisen tasojen saavuttamiseksi

The assessment is based on an exam.

Arvosteluasteikko:

Numerical evaluation scale (0-5)

Osasuoritukset:

Completion parts must belong to the same implementation

Oppimateriaali

Tyyppi Nimi Tekijä ISBN URL Lisätiedot Tenttimateriaali
Book   The Design of Approximation Algorithms   David P. Williamson & David B. Shmoys         Yes   

Esitietovaatimukset

Opintojakso P/S Selite
MAT-02650 Algoritmimatematiikka Mandatory    
TIE-02100 Johdatus ohjelmointiin Mandatory    

Vastaavuudet

Opintojakso ei vastaan mitään toista opintojaksoa

Päivittäjä: Ikonen Suvi-Päivikki, 13.04.2016