581336-0 Laskennan teoria (3 ov)
Syksyn 2003 kurssikoe on arvosteltu.
- tehtävät
- malliratkaisuja ja pisteytys
- tulokset (korjaus 29.12.: lisätty yksi puuttunut laskuharjoituskirjaus)
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.)
-
- Mikko Rauhala ti 14-16 B453
- Mikko Rauhala ti 16-18 B453
- Jouni Siren ke 14-16 A217
- Janne Rinta-Mänty to 10-12 A319
- Janne Rinta-Mänty to 14-16 C454
- 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
- Harjoitus 1: tehtävät PS ja PDF; malliratkaisut
- Harjoitus 2: tehtävät PS ja PDF; malliratkaisut
- Harjoitus 3: tehtävät PS ja PDF; malliratkaisut
- Harjoitus 4:tehtävät PS ja PDF; malliratkaisut
- Harjoitus 5: tehtävät PS ja PDF; malliratkaisut
- Harjoitus 6: tehtävät PS ja PDF; malliratkaisut
- Harjoitus 7: tehtävät PS ja PDF; malliratkaisut
- Harjoitus 8: tehtävät PS ja PDF; malliratkaisut
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
- Johdanto
- Laskennalliset ongelmat
- Pysähtymisongelman ratkeamattomuus
- Universaaleja laskennan malleja
- Turingin koneet
- Rajoittamattomat kieliopit
- Churchin-Turingin teesi
- Laskettavuusteoriaa
- Rekursiiviset ja rekursiivisesti lueteltavat kielet
- Rekursiiviset funktiot ja palautukset
- Universaalit Turingin koneet
- Ratkeamattomuustuloksia
- 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