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. Polynominen aikavaativuushierarkia

3. Oraakkelikoneet ja laskentaongelmien relativointi

4. Alternoivat Turingin koneet ja niiden vaativuusluokat

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