OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op

Prof. Tapio Elomaa

Syksy 2008, periodit I ja II

Luennot:

• P I 26.8.-2.10.: ti 14-16 TC103 ja to 14-16 TC133
  
• P II 14.10.-20.11.: ti 14-16 TB219 ja to 12-14 TB224

Viikkoharjoitukset: DI Jussi Kujala (DI Timo Aho) ma 12-14 TC131

Kurssikoe: ke 26.11.2008 klo 9-12

Ajankohtaista

• Tentti keskiviikkona 26.11. klo 9-12 salissa TB111

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 2008 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	26. ja 28.8.	I:1	8.9.	0, 1.1
2	2. ja 4.9.	I:2	15.9.	1.2-1.4
3	9. ja 11.9.	I:3	22.9.	2
4	16. ja 18.9.	I:4	29.9.	3.1-3.2
5	23.9.	I:5	13.10.	4.2
6	30.9. ja 2.10.	I:6	20.10.	4, 5
7	14. ja 16.10.	II:7	27.10.	5
8	21. ja 23.10.	II:8	3.11.	7.1-7.2
9	28. ja 30.10.	II:9	10.11.	7.3-7.4
10	4. ja 6.11.	II:10	17.11	7.4-7.5, 8.1-8.3
11	11. ja 13.11.	II:11	--	8.4-8.5, 10.1
12	17. ja 20.11.	II:12	--	10.2

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ö

1. Johdanto
   laskennalliset ongelmat, esitykset, päätösongelmat, laskennallisten ongelmien ratkeavuus
2. Kertausta
   • Äärelliset automaatit
   • Automaattien minimointi
   • Epädeterministiset äärelliset automaatit
   • Säännölliset lausekkeet
   • Säännöllisten kielten rajoituksista
3. Kontekstittomat kielet
   moniselitteisyys, Chomskyn normaalimuoto, pinoautomaatit
4. Laskennan universaaleja malleja
   • Turingin koneet
     Turingin koneiden laajennuksia: moninauhaiset koneet, epädeterministiset koneet
   • Kieliopeista
   • Algoritmeista
5. Laskettavuusteoriaa
   • Rekursiivisten ja RE-kielten perusominaisuuksia
   • Turingin koneiden koodaus
   • Ratkeavia ongelmia
   • Äärettömistä joukoista
   • Universaalit Turingin koneet
   • Pysähtymisongelma
   • Chomskyn kieliluokat
6. Palautuvuus
   epätyhjyysongelma, säännöllisen kielen tunnistavat Turingin koneet, Ricen lause, lineaarisesti rajoitetut automaatit, rekursiiviset palautukset
7. Aikavaativuus
   • Vaativuusfunktioiden kertaluokat
   • Luokka P
   • Luokka NP
   • NP-täydellisyys
8. Tilavaativuus
   • Savitchin lause
   • PSPACE-täydellisyys
   • Luokat L ja NL
9. Approksimointi
10. Satunnaisalgoritmit

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ä