OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op
- Prof. Tapio Elomaa
ja DI Jussi Kujala
- Syksy 2006, periodit I ja II
- Luennot: 28.8.-23.11.: ma 12-14 ja to 14-16 TB222
- Viikkoharjoitukset: DI
Timo Aho ti 10-12 TC131
- Kurssikoe: to 30.11.2006 klo 9-12
Ajankohtaista
- Tentti torstaina 30.11. klo 9-12 salissa TB109
- Timo Ahon tiivistelmät luennoista ovat saatavilla hänen
kotisivultaan
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 2006 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 | 28. ja 31.8. |
PDF |
PDF |
0, 1.1 |
| 2 | 4. ja 7.9. |
PDF |
PDF |
1.2-1.4 |
| 3 | 11. ja 14.9. |
PDF |
PDF |
2 |
| 4 | 18. ja 21.9. |
PDF |
PDF |
3.1-3.2 |
| 5 | 25. ja 28.9. |
PDF |
PDF |
4.2 |
| 6 | 2. ja 5.10. |
PDF |
PDF |
4.1-4.2 |
| 7 | 16. ja 19.10. |
PDF |
PDF |
4.2, 5.1 |
| 8 | 23. ja 26.10. |
PDF |
PDF |
5.3, 7.1 |
| 9 | 30.10. ja 2.11. |
PDF |
PDF |
7.2-7.4 |
| 10 | 6. ja 9.11. |
PDF |
PDF |
7.4-7.5, 8.1-8.2 |
| 11 | 13. ja 16.11. |
PDF |
PDF |
8.3-8.5, 10.1 |
| 12 | 20. ja 23.11. |
PDF |
-- |
10.1-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.
-
laskuharjoitusmerkinnät
Sisältö
- Johdanto
laskennalliset ongelmat, esitykset, päätösongelmat, laskennallisten
ongelmien ratkeavuus
- Kertausta
- Äärelliset automaatit
- Automaattien minimointi
- Epädeterministiset äärelliset automaatit
- Säännölliset lausekkeet
- Säännöllisten kielten rajoituksista
- Kontekstittomat kielet
moniselitteisyys, Chomskyn normaalimuoto, pinoautomaatit
- Laskennan universaaleja malleja
- Turingin koneet
Turingin koneiden laajennuksia: moninauhaiset koneet,
epädeterministiset koneet
- Kieliopeista
- Algoritmeista
- Laskettavuusteoriaa
- Rekursiivisten ja RE-kielten perusominaisuuksia
- Turingin koneiden koodaus
- Ratkeavia ongelmia
- Äärettömistä joukoista
- Universaalit Turingin koneet
- Pysähtymisongelma
- Chomskyn kieliluokat
- Palautuvuus
epätyhjyysongelma, säännöllisen kielen tunnistavat Turingin
koneet, Ricen lause, lineaarisesti rajoitetut automaatit,
rekursiiviset palautukset
- Aikavaativuus
- Vaativuusfunktioiden kertaluokat
- Luokka P
- Luokka NP
- NP-täydellisyys
- Tilavaativuus
- Savitchin lause
- PSPACE-täydellisyys
- Luokat L ja NL
- Approksimointi
- Satunnaisalgoritmit
Kirjallisuutta
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,
Second (International) ed., Thomson, 2006
Linkkejä
Nov. 23, 2006
http://www.cs.tut.fi/~elomaa/