Laskennan teorian opintopiiri
Vuosi | Lukukausi | Päivämäärä | Periodi | Kieli | Vastuuhenkilö |
---|---|---|---|---|---|
2014 | kevät | 13.01-21.02. | 3-3 | Suomi | Antti Laaksonen |
Harjoitusryhmät
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Ke 16-18 | C220 | Paula Lehtola | 13.01.2014—21.02.2014 |
Yleistä
Kurssin ohjaaja: Paula Lehtola
Kurssilla tehdyt kirjalliset työt: http://www.cs.helsinki.fi/u/pklehtol/late14.html
Laskennan teoriaan liittyy monia tärkeitä ja kiinnostavia aiheita, joita ei käsitellä kurssilla Laskennan mallit. Tämä kurssi tutustuttaa joukkoon tällaisia aiheita opintopiirin muodossa. Kurssin osallistujat laativat suullisen esityksen ja kirjallisen työn valitusta laskennan teorian aiheesta. Kurssilla voi opiskella yksin tai ryhmässä, ja ensimmäisessä tapaamisessa sovitaan tarkemmin käsiteltävät aiheet ja kurssin aikataulu.
Mahdollisia aiheita:
- äärellisen automaatin minimointi (Hopcroft s. 67-71)
- deterministiset vs. epädeterministiset pinoautomaatit, deterministiset kieliopit ja sulkeumat (Hopcroft s. 234 ->, Sipser 3. painos s. 130-154)
- Chomskyn hierarkia ja yhteysherkät kieliopit (Hopcroft s. 223-228, Cohen s. 729-759)
- Postin vastaavuusongelma (Hopcroft s. 193-200)
- Turingin koneen vaihtoehdot, yleiskuva: lambda-kalkyyli, rekursiiviset funktiot, yleiset kieliopit (unrestricted grammars), Postin kone (esim. Cohen s. 584-615 ja 729-759, Hopcroft s. 220-223)
- tilavaativuus, PSPACE-täydellisyys (Sipser s. 309-313, Hopcroft s. 343-347)
- Savitchin teoreema (PSPACE = NPSPACE) (Sipser s. 305-309)
- Immerman-Szelepcsényi-teoreema (NL = co-NL)
- satunnaisalgoritmit (Sipser s. 374-386)
- oma aihe
Kurssin suorittaminen
Opintopisteiden saamisen kriteerit (2 op):
- läsnäolo aloituskerralla sekä ainakin neljällä viidestä muusta kerrasta
- suullisen esitelmän ja kirjallisen työn laatiminen
- vertaispalautteen antaminen
Jos kurssista haluaa saada 3 op, tulee osallistua kahden esityksen ja kirjallisen työn tekemiseen.
Kurssi arvioidaan asteikolla hyväksytty/hylätty.
Kirjallisuus ja materiaali
Esimerkiksi:
- Cohen, Daniel I. A.: Introduction to Computer Theory
- Hopcroft, John E. ja Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation (vuoden 1979 painos, vaaleakantinen)
- Sipser, Michael: Introduction to the Theory of Computation