8101100 Johdatus tietojenkäsittelyteoriaan, 4 ov

Prof. Tapio Elomaa

Kevät 2004

Luennot: 8.1.-22.4.: ti 12-14 K1703 ja to 13-15 TB109

Viikkoharjoitukset: Ville Laakso
ma 10-12 TC210 ja to 10-12 TC128

Kurssikoe: pe 7.5. klo 9-12

Ajankohtaista

Tentti perjantaina 7. 5. klo 9-12

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).

Luentovko	Kalvot	Harjoitukset
1: 8. 1.	PS ja PDF	--
2: 12.-16. 1.	PS ja PDF	PS ja PDF
3: 19.-23. 1.	PS ja PDF	PS ja PDF
4: 26.-30. 1.	PS ja PDF	PS ja PDF
5: 2.-6. 2.	PS ja PDF	PS ja PDF
6: 9.-13. 2.	PS ja PDF	PS ja PDF
7: 16.-20. 2.	PS ja PDF	PS ja PDF
8: 2.-5. 3.	PS ja PDF	PS ja PDF	Tähänastiset kalvot yhtenä tiedostona PS ja PDF
9: 8.-12. 3.	PS ja PDF	PS ja PDF
10: 15.-19. 3.	PS ja PDF	PS ja PDF
11: 22.-26. 3.	PS ja PDF	PS ja PDF
12: 29. 3.- 2. 4.	PS ja PDF	PS ja PDF
13: 5.- 16. 4.	PS ja PDF	PS ja PDF
14: 19.- 23. 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
• 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ä

Apr. 22, 2004