Mat-1.190 Laskennan vaativuusanalyysi (2 ov)

Kurssi on luennoitu viimeisen kerran syksyllä 2004, ja poistuu opetusohjelmasta

Kurssin sisältö

Kurssi on käsitellyt algoritmien ns. laskennallista kompleksisuutta. Esimerkkien valossa on tarkasteltu eräiden algoritmien suorittamisen vaatimaa työmäärää ja tutkittu mahdollisuuksia valita toiminnaltaan nopeita algoritmeja ko. tehtävien suorittamiseen.

Kurssin sisältöä:

Hitaat ja nopeat algoritmit, suuruusluokka-arvioita, rekursiiviset algoritmit.
Graafialgoritmeja, matriisituloista, nopea Fourier-muunnos.
Virtausverkot: Ford-Fulkersonin algoritmi ja MPM-algoritmi.
Lukuteoriaa, pseudoalkuluvut, kryptografiaa, tekijöihin jakamisesta, alkuluvuksi todistamisesta.
Ratkaisuprobleemoista, Turingin koneista, tyydytettävyysprobleema.
NP-täydellisyys.

Kirjallisuus

Oppikirja, jonka voi korvata opetusmonisteella, on Herbert S. Wilf: Algorithms and Complexity, Prentice-Hall 1986.

Esitiedot

Matematiikan perustiedot, esim. peruskurssien 1 - 2 laajuudessa.

Kurssin suorittaminen

Yhdellä tentillä sopimuksen mukaan.

Kurssin opettaja

Lehtori Seppo Ilkka.

Seppo Ilkka

11.1.2006