Laskennan teorian opintopiiri
2-3
Algorithms and machine learning
Intermediate studies
Tällä kurssilla on tarkoituksena tutustua yhdessä tehden sellaisiin laskennan teorian aihepiireihin, joita ei ole Laskennan malleissa käsitelty. Kurssi suoritetaan osallistumalla harjoitustilaisuuksiin, tekemällä ryhmän kanssa esitys ja kirjallinen työ jostain kurssin aihepiiristä, sekä vertaisarvioimalla muiden töitä. Kurssin laajuus on 2 op. Mikäli tekee toisen esityksen ja kirjallisen työn, kurssista saa 3 op. Kurssi on tarkoitettu joko tänä syksynä tai aiemmin Laskennan mallit -kurssin käyneille.
Year | Semester | Date | Period | Language | In charge |
---|---|---|---|---|---|
2013 | spring | 14.01-22.02. | 3-3 | Finnish | Antti Laaksonen |
Exercise groups
Time | Room | Instructor | Date | Observe |
---|---|---|---|---|
Wed 16-18 | C220 | Paula Lehtola | 14.01.2013—22.02.2013 |
General
Kurssilla on tarkoitus tehdä ryhmässä esitys ja kirjallinen työ laskennan teoriaan liittyvästä aiheesta. Tarkoitus on, että esitykset ja kirjalliset työt ovat tasoltaan niin selkeitä, että muut kurssilaiset ymmärtävät ne. Ryhmä tekee kirjallisen työn samasta aiheesta kuin esityksen, ja työn pituus on noin 1000 sanaa.
Kurssin IRC-kanava on #late IRCnet-verkossa.
Laskarivetäjän email: pklehtol[at]cs.helsinki.fi
Alla on aihe-ehdotuksia sekä joitain esimerkkejä siitä, mistä löytyy tietoa:
- äärellisen automaatin minimointi (Hopcroft s. 67-71)
- deterministiset vs. epädeterministiset pinoautomaatit, deterministiset kieliopit ja sulkeumat (Hopcroft s. 234 ->)
- 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)
- P vs. NP, aikavaativuus (Sipser s. 260-274)
- NP-täydellisyys (Sipser s. 275-297)
- 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
Completing the course
Opintopisteiden saamisen kriteerit (2 op):
- läsnäolo aloituskerralla sekä ainakin neljällä viidestä muusta kerrasta
- osallistuminen ryhmässä esityksen valmisteluun ja esittämiseen, sekä omasta aiheesta ryhmänä tehtävään kirjalliseen työhön
- vertaispalautteen antaminen
Jos kurssista haluaa saada 3 op, tulee osallistua kahden esityksen ja kirjallisen työn tekemiseen.
Kurssi arvioidaan asteikolla hyväksytty/hylätty.
Literature and material
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
- Jyrki Kivisen luentokalvot (Laskennan mallien sivuilla)
- googlettamalla löytyy paljon materiaalia