582208

Laskennan vaativuus
Komplexitet av beräkning
Complexity of Computation
582208
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.

Toistuminen

Ei tarjota

Tulevat erilliskokeet

Ei kokeita.

Kurssisivut

Ei kursseja.