8101100 Johdatus tietojenkäsittelyteoriaan, 4 ov

Prof. Tapio Elomaa

Kevät 2005

Luennot: 13.1.-28.4.: ti 12-14 K1703 ja to 13-15 TB109

Viikkoharjoitukset: DI Jussi Kujala: ti 14-16 ja to 15-17 TC161

Kurssikoe: 11.5.2005

Ajankohtaista

Yleistä

Kurssin pääsivu.

Esitietovaatimuksena ovat opintojaksot 8100310 Tietorakenteet ja algoritmit ja 8100500 Ohjelmistotekniikan matemaattiset menetelmät.

Pakollinen ohjelmistotieteen pitkässä ammattiaineessa sekä ohjelmistotekniikkaan keskittyvissä jatko-opinnoissa.

Kurssin tavoitteena on tutustua ohjelmoinnin ja laskennan pohjimmaisiin mahdollisuuksiin - mitä ongelmia periaatteessa voidaan ohjelmallisesti ratkaista ja mitkä ongelmat voidaan lisäksi ratkoa tehokkaasti. Lisäksi pyritään vetämään näiden tulosten yhteyksiä käytännön ohjelmistotyöhön.

Luennot

Kurssin luennot eivät perustu suoraan mihinkään lähteeseen, vaan yhdistelevät tietoja monista kirjallisista lähteistä. Kurssin tentit perustuvat luentoihin (ei siis pelkästään luentokalvoihin).

Viikko	Päivät	Kalvot	Harjoitukset
1	13.1.	PS ja PDF
2	18. ja 20.1.	PS ja PDF	PS ja PDF
3	25. ja 27.1.	PS ja PDF	PS ja PDF
4	1. ja 3.2.	PS ja PDF	PS ja PDF
5	8.2.	PS ja PDF	PS ja PDF
6	15.2.	PS ja PDF	--
7	22. ja 24.2.	PS ja PDF	PS ja PDF
8	8. ja 10.3.	PS ja PDF	PS ja PDF
9	15. ja 17.3.	PS ja PDF	PS ja PDF
10	22. ja 31.3.	PS ja PDF	PS ja PDF
11	5. ja 7.4.	PS ja PDF	PS ja PDF
12	12.4.	PS ja PDF	PS ja PDF
13	19. ja 21.4.	PS ja PDF	PS ja PDF
14	26. ja 28.4.	PS ja PDF

Viikkoharjoitukset

Viikkoharjoituksissa on lisäpistejärjestelmä: Osallistumisesta harjoituksiin saa "merkinnän", valmiudesta esittää harjoitustehtävän ratkaisu "taululla" saa merkinnän. Harjoituksia on 12, joissa kussakin on n. 6 tehtävää, joten merkintöjä voi kerätä yhteensä n. 7*12=84 kappaletta. Merkintöjen kokonaisosuus määrää lisäpisteet seuraavasti:
20%: 1 p., 30%: 2 p., 40%: 3 p., ..., 80%: 7 p. ja 90%: 8 p.

Viikkoharjoituksiin osallistuminen ja tehtävien itsenäinen ratkominen on lähes välttämätön edellytys kurssin suorittamiselle.

Sisältö

Kurssin sisältö on jokseenkin sama kuin aiempina vuosina, kuitenkin siten ettei kurssilla Ohjelmistotekniikan matemaattiset menetelmät jo opetettuja asioita käydä enää toistamiseen läpi. Kurssin alustava sisältö on:

1.	Johdanto
2.	Automaatit ja lausekkeet
3.	Kielioppien jäsentäminen
4.	Äärettömät joukot
5.	Laskenan malleja
6.	Laskettavuusteoria
7.	Laskennan vaativuusteoriaa

Kirjallisuutta

Hyödyllisintä taustamateriaalia kurssille ovat luentomonisteet

• Antti Valmari: Johdatus tietojenkäsittelyteoriaan, TTY 2003
• Pekka Orponen: Laskennan teoria, HY 1993

Melkein mikä tahansa alan oppikirja sisältää useimmat kurssilla käsitellyt asiat. Kirjoja ovat mm.

• Eitan M. Gurari: An Introduction to the Theory of Computation, Computer Science Press, 1989
• John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second ed., Addison-Wesley, 2001
• Efim Kinber & Carl Smith: Theory of Computing, A Gentle Introduction, Prentice Hall, 2001
• Harry R. Lewis & Christos H. Papadimitriou: Elements of the Theory of Computation, Second ed., Prentice-Hall, 1998
• J. Martin: Introduction to Languages and the Theory of Computation, Third ed., McGraw-Hill, 2003
• B. Moret: The Theory of Computation, Addison-Wesley, 1998
• Michael Sipser: Introduction to the Theory of Computation, PWS Publishing Company, 1997

Linkkejä