Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

581336-0 Laskennan teoria (3 ov)

(Erilliskokeet)

Syksyn 2003 kurssikoe on arvosteltu.

Opetus syksyllä 2003

Opetus on päättynyt.

Luennot
Jyrki Kivinen 14.10.-3.12. ti 12-14, ke 10-12 A217
Harjoitusryhmät (pidettiin 20.10.-10.12.)
  1. Mikko Rauhala ti 14-16 B453
  2. Mikko Rauhala ti 16-18 B453
  3. Jouni Siren ke 14-16 A217
  4. Janne Rinta-Mänty to 10-12 A319
  5. Janne Rinta-Mänty to 14-16 C454
  6. Jouni Siren pe 14-16 A318
Kurssikoe
pe 12.12. kello 9-13 Auditorio
Kurssikysely

Kurssimateriaali

Paperiversio on huoneen A412 kurssikansiossa.

Luennot

PostScript-versiossa on neljä sivua per arkki ja ne on tarkoitettu mustavalkotulostukseen. PDF-versio lienee mukavampi näytöllä. Tulostamista laitoksen kirjoittimilla pyydetään välttämään.

Koko materiaali yhtenä tiedostona:

Sama materiaali löytyy myös alkuperäisinä pieninä palasina, joita ilmestyi lukukauden mittaan.

Laskuharjoitukset

Yleistä

Kurssi laajentaa ja syventää Ohjelmoinnin ja laskennan perusmallit -kurssin antamaa tietojenkäsittelytieteen teoreettisten perusteiden tuntemusta. Erityisesti tarkastellaan Turingin koneita, laskennallisten ongelmien ratkeavuutta sekä laskennan vaativuusteoriaa.

Asema opetuksessa

Laudaturin pakollinen kurssi tietojenkäsittelyn, opettajan sekä bioinformatiikan ja laskennallisen biologian suuntautumisvaihtoehdossa.

Opiskelijoilta edellytetään kurssien Ohjelmoinnin ja laskennan perusmallit ja Tietorakenteet tiedot sekä kohtuulliset matemaattiset perusvalmiudet (esim. kursseilta Algebra I tai Diskreetti Matematiikka I).

Aihepiiriin liittyviä jatkokursseja ovat mm. Algoritmien suunnittelu ja analyysi ja useat algoritmien erikoistumislinjan erikoiskurssit sekä Laskettavuuden teoria ja osittain muutkin matemaattisen logiikan kurssit.

Suoritusmuodot

Luentokurssi koostuu luennoista, laskuharjoituksista ja kurssikokeesta. Vaihtoehtoisesti kurssin voi myös suorittaa erilliskokeella.

Laskuharjoitukset ovat pakollisia suoritettaessa kurssi kurssikokeella. Laskuharjoituksista voi tällöin saada myös lisäpisteitä. Tarkemmista yksityiskohdista tiedotetaan erikseen.

Kirjallisuutta

Kurssikirja:
Hopcroft J. E., Motwani R., Ullman J. D.: Introduction to Automata Theory, Languages, and Computation (2nd ed.), Addison-Wesley, 2001
Oheislukemista:
Pekka Orponen: Laskennan teoria. Luentomoniste, 1994.

Luentokalvojen kopiot toimitetaan saataville kurssin edetessä.

Sisältöluonnos

  1. Johdanto
    • Laskennalliset ongelmat
    • Pysähtymisongelman ratkeamattomuus
  2. Universaaleja laskennan malleja
    • Turingin koneet
    • Rajoittamattomat kieliopit
    • Churchin-Turingin teesi
  3. Laskettavuusteoriaa
    • Rekursiiviset ja rekursiivisesti lueteltavat kielet
    • Rekursiiviset funktiot ja palautukset
    • Universaalit Turingin koneet
    • Ratkeamattomuustuloksia
  4. Vaativuusteoriaa
    • aika- ja tilavaativuus
    • deterministiset ja epädeterministiset vaativuusluokat
    • polynomiset palautukset
    • luokka NP; NP-täydellisyys
    • SAT ja muita NP-täydellisiä ongelmia

Linkkejä

Ohjelmoinnin ja laskennan perusmallit
Algoritmien suunnittelu ja analyysi
Laskettavuuden teoria, matematiikan laudatur-kurssi
Teoreettiseen tietojenkäsittelyyn liittyviä visualisointityökaluja
Algoritmien erikoistumislinja


Jyrki Kivinen