Laskennan vaativuus
4
Algorithms and machine learning
Intermediate studies
Kurssilla kerrataan Turingin koneen formalismit ja niiden aikavaativuudet. Sen jälkeen esitellään vaativuusluokat P, NP, PSPACE, L ja NL. Muutamia NP-täydellisiä ongelmia käsitellään tarkasti, muiden luokkien täydellisiä ongelmia sen sijaan ylimalkaisemmin. Lopuksi, jos aikaa jää, käsitellään satunnaisalgoritmeja. Esitiedot: Laskennan mallit. Kurssikirja: Sipser M.: Introduction to the Theory of Computation (2nd ed.), Thomson Course Technology, 2006.
Lectures
Time | Room | Lecturer | Date |
---|---|---|---|
Wed 10-12 | CK112 | Timo Karvi | 14.03.2007-27.04.2007 |
Fri 10-12 | CK112 | Timo Karvi | 14.03.2007-27.04.2007 |
Exercise groups
Time | Room | Instructor | Date | Observe |
---|---|---|---|---|
Tue 12-14 | B119 | Harri Forsgren | 19.03.2007—27.04.2007 |