OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op

Prof. Tapio Elomaa

Syksy 2005, periodit I ja II

Luennot: 29.8.-24.11.: ma 12-14 ja to 14-16 TB222

Viikkoharjoitukset: DI Jussi Kujala to 10-12 TC103

Kurssikoe: 29.11.2005

Ajankohtaista

Tentti on tiistaina 29.11.

Yleistä

Kurssin pääsivu.

Esitietovaatimuksena ovat opintojaksot MAT-20600 Diskreetti matematiikka ja OHJ-2150 Algoritmien analyysi. (Myös vanhat esitietovaatimukset 8100310 Tietorakenteet ja algoritmit sekä 8100500 Ohjelmistotekniikan matemaattiset menetelmät kelpaavat).

Jatko-opintokelpoinen. Pakollinen ohjelmistotieteen syventävissä 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

Syksyn 2005 toteutuksen luennot perustuvat kirjaan

• Michael Sipser: Introduction to the Theory of Computation, Second (International) ed., Thomson, 2006.

Kurssin tentit perustuvat luentoihin (ei siis pelkästään luentokalvoihin).

Viikko	Päivät	Kalvot	Harjoitukset	Kirjan luvut
1	29.8 ja 1.9.	PS ja PDF	PS ja PDF	0, 1.1
2	5. ja 8.9.	PS ja PDF	PS ja PDF	1.2-1.3
3	12. ja 15.9.	PS ja PDF	PS ja PDF	1.4, 2
4	19. ja 22.9.	PS ja PDF	PS ja PDF	3.1-3.2
5	26. ja 29.9.	PS ja PDF	PS ja PDF	4.2
6	17. ja 20.10.	PS ja PDF	PS ja PDF	4.1-4.2
7	24. ja 27.10.	PS ja PDF	PS ja PDF	5.1, 5.3
8	31.10. ja 3.11.	PS ja PDF	PS ja PDF	7.1-7.3
9	7. ja 10.11.	PS ja PDF	PS ja PDF	7.4-7.5
10	14. ja 17.11.	PS ja PDF	PS ja PDF	8
11	21. ja 24.11.	PS ja PDF	--	10.1

Viikkoharjoitukset

Viikkoharjoituksissa on lisäpistejärjestelmä.

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

Sisältö

Kirjallisuutta

• 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, Second (International) ed., Thomson, 2006

Linkkejä