MAT-72606 Approximation Algorithms, 4 cr
Lisätiedot
No lectures in the academic year 2017-2018.
Suitable for postgraduate studies.
Ei toteuteta lukuvuonna 2017-2018.
Vastuuhenkilö
Tapio Elomaa
Opetus
| Toteutuskerta | Periodi | Vastuuhenkilö | Suoritusvaatimukset |
| MAT-72606 2017-01 | - |
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:
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