OHJ-2300 Johdatus tietojenkäsittelyteoriaan, 6 op

Prof. Tapio Elomaa

Syksy 2008, periodit I ja II

Luennot:
Viikkoharjoitukset: DI Jussi Kujala (DI Timo Aho) ma 12-14 TC131
Kurssikoe: ke 26.11.2008 klo 9-12

- Ajankohtaista

- 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 Kurssin tentit perustuvat luentoihin (ei siis pelkästään luentokalvoihin).

ViikkoPäivätKalvotHarjoitukset 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
  3. Kontekstittomat kielet
    moniselitteisyys, Chomskyn normaalimuoto, pinoautomaatit
  4. Laskennan universaaleja malleja
  5. Laskettavuusteoriaa
  6. Palautuvuus
    epätyhjyysongelma, säännöllisen kielen tunnistavat Turingin koneet, Ricen lause, lineaarisesti rajoitetut automaatit, rekursiiviset palautukset
  7. Aikavaativuus
  8. Tilavaativuus
  9. Approksimointi
  10. Satunnaisalgoritmit

- Kirjallisuutta

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

- Linkkejä


Nov. 20, 2008 http://www.cs.tut.fi/~elomaa/