Jyväskylän yliopisto
Matematiikan laitos
Pekka Orponen

Kurssini

ALGORITMITEORIAN JATKOKURSSI (TIE311, 2 OV)

ensimmäinen luento on ma 22.3. klo 12—14 salissa MaD302. (Huomaa opinto-oppaassa ilmoitetusta poikkeava aloituspäivä.)

Kurssi on tietotekniikan l-opintojen valinnainen opintojakso, jonka aihepiiri on vuosittain vaihtuva. Kevään 1999 kurssin aiheena on laskennan vaativuusteoria (ns. NP-täydellisyysteoria). Esitietoina edellytetään kurssien Algoritmien teoria ja Automaatit ja kieliopit sekä Matematiikan approbaturin tiedot. Kurssit Johdatus diskreettiin matematiikkaan ja Matemaattinen logiikka ovat suositeltavia.

Kurssiin kuuluu 20 h luentoja (ma 12—14, ke 14—16 MaD 302) ja 10 h harjoituksia. Kurssille on ilmoittauduttava Kurki-järjestelmän kautta (os. http://kurki.math.jyu.fi/kurki.htm ).

Kurssin alustava sisällysluettelo on seuraava (loppupään aiheiden toteutuminen on vielä epävarmaa):

0.	Peruskäsitteet: deterministiset ja epädeterministiset Turingin koneet ja niiden vaativuusluokat; vaativuusluokkien perusominaisuudet; palautukset ja täydellisyys
1.	Laskentaongelmien tilavaativuudesta
2.	Alternoivat Turingin koneet ja niiden vaativuusluokat
3.	Polynominen aikavaativuushierarkia
4. 	Oraakkelikoneet ja laskentaongelmien relativointi
5. 	NP-täydellisten kielten rakenteesta
6. 	Luokan NP hienorakenne
7.	Epäuniformit vaativuusmitat: neuvofunktiot ja kombinaatiopiirit
8. 	Probabilistiset Turingin koneet ja niiden vaativuusluokat
9. 	Merkkijonojen Kolmogorov-kompleksisuus
10. Vuorovaikutteiset todistukset ja todistusten tarkastaminen

Kurssi perustuu luentomuistiinpanoihini, mutta sisällöltään vastaavia oppikirjoja ovat esim. J. Balcázar, J. Díaz, J. Gabarró, ”Structural Complexity I/II” (Springer-Verlag 1988/90, 2nd Ed 1995),
D. Bovet, P. Crescenzi, ”Introduction to the Theory of Complexity” (Prentice-Hall 1994) ja C. Papadimitriou, ”Computational Complexity” (Addison-Wesley 1994).

Tervetuloa kurssille!
Pekka Orponen