MAT-72306 Randomized Algorithms, 4 cr
Lisätiedot
Suitable for postgraduate studies.
Vastuuhenkilö
Tapio Elomaa
Opetus
| Toteutuskerta | Periodi | Vastuuhenkilö | Suoritusvaatimukset |
| MAT-72306 2016-01 | 3 |
Tapio Elomaa |
Exam at the end of the course. Exercises yield extra points. |
Osaamistavoitteet
After completion of the course the student will comprehend the probabilistic background of randomized algorithms and will grasp the general usefulness of randomization in algorithm design.
Sisältö
| Sisältö | Ydinsisältö | Täydentävä tietämys | Erityistietämys |
| 1. | Discrete random variables and expectation | Bernoulli and binomial random variables | |
| 2. | Moments and deviations | Markov's inequality, Chebyshev's inequality | |
| 3. | Chernoff bounds | Moment generating functions | |
| 4. | Balls, bins, and random graphs | The Poisson distribution | |
| 5. | The probabilistic method | Derandomization using conditional expectations | |
| 6. | Markov chains and random walks |
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 | Probability and Computing | Michael Mitzenmacher & Eli Upfal | 521835402 | Yes |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| MAT-02500 Todennäköisyyslaskenta | Mandatory | |
| MAT-02650 Algoritmimatematiikka | Mandatory | |
| TIE-02200 Ohjelmoinnin peruskurssi | Advisable |
Vastaavuudet
Opintojakso ei vastaan mitään toista opintojaksoa