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

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

ViikkoPäivätKalvotHarjoitukset 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ö

  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

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

- Linkkejä


Nov. 23, 2006 http://www.cs.tut.fi/~elomaa/