Jyväskylän yliopisto
Matematiikan laitos
Pekka Orponen

Kurssini

ALGORITMIEN TEORIA (TIE310, 3 OV)

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

Kurssi on tietotekniikan l-opintojen valinnainen opintojakso (ohjelmistotekniikan linjalla pakollinen), ja täydentää sisällöltään Tietorakenteet ja algoritmit 1&2 –kurssien tietoja. Käsiteltäviä  aihepiirejä ovat mm. tehokkaat tietorakenteet (tasapainotetut puut, keot, binomimetsät, hyppylistat), algoritmianalyysin menetelmät, likimääräis- ja satunnaisalgoritmit sekä laskennan vaativuusteorian perusteet. Esitietoina edellytetään kurssien Tietorakenteet ja algoritmit 1 ja 2 sekä Matematiikan approbaturin tiedot. (Kurssit Automaatit ja kieliopit, Johdatus diskreettiin matematiikkaan sekä Todennäköisyyslaskenta ovat suositeltavia.)

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

Kurssi perustuu luentomuistiinpanoihini, mutta vastaa sisällöltään esim. teoksen M. Penttonen, ”Johdatus algoritmien suunnitteluun ja analysointiin” (Otatieto 1997) lukuja 2, 3, 7, 8, 9, 15, 16. Hyviä englanninkielisiä esityksiä kurssin aihepiiristä ovat. teokset T. Cormen, C. Leiserson, R. Rivest, ”Introduction to Algorithms” (MIT Press 1990) ja G. Brassard, P. Bratley, “Fundamentals of Algorithmics” (Prentice-Hall 1996).

Tervetuloa kurssille!
Pekka Orponen