Laskennan vaativuus
4
Algoritmit ja koneoppiminen
Aineopinnot
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.
Luennot
Aika | Huone | Luennoija | Päivämäärä |
---|---|---|---|
Ke 10-12 | CK112 | Timo Karvi | 12.03.2008-25.04.2008 |
Pe 10-12 | CK112 | Timo Karvi | 12.03.2008-25.04.2008 |
Harjoitusryhmät
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Ke 12-14 | C221 | Harri Forsgren | 17.03.2008—25.04.2008 |