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:
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