|
|
|||||||||||||||||
Opinto-opas 2010-2011
MAT-41180 Formaalit kielet, 6 op
|
Vastuuhenkilö
Keijo Ruohonen
Opetus
| Opetusmuoto | P1 | P2 | P3 | P4 | Kesä | Toteutuskerrat | Luentoajat ja -paikat |
| |
Suoritusvaatimukset
Hyväksytysti suoritettu kirjallinen tentti.
Osasuoritusten pitää liittyä samaan toteutuskertaan
Osaamistavoitteet
Opintojakson suoritettuaan opiskelija osaa määritellä formaalien kielten perusperheet sekä generointi- ja tunnistustavat. Opiskelija osaa kielten perusoperaatiot ja niiden perusominaisuudet, erityisesti kielten perusperheiden yhteydessä. Opiskelija osaa myös luokitella yksinkertaisia kieliä perusperheisiin. Osaamistavoitteet saavutettuaan opiskelijalla on käytössään työkalut, joilla analysoida syntaktisesti sovellustilanteissa esiintulevia kieliä, mm. ohjelmointikieliä, luonnollisten kielten yksinkertaisia malleja, koodeja ja jossain määrin myös moninaisia kielten yleistyksiä (multikielet, stokastiset kielet, kvanttikielet, sumeat kielet). Kyseisiä työkaluja on kehitetty ja tutkittu laajasti ja pitkän aikaa, eikä yhden opinjakson puitteissa ole mahdollista ottaa mukaan koko alueen osaamistavoitteita täysin kattavasti. Opintojakson suoritettuaan opiskelijalla on edellytykset myös laajentaa taitojaan ja omaksua muutakin.
Sisältö
| Sisältö | Ydinaines | Täydentävä tietämys | Erityistietämys |
| 1. | Formaalien kielten perusominaisuudet ja -operaatiot. Säännölliset lausekkeet ja kielet perusominaisuuksineen. Äärelliset automaatit perusominaisuuksineen. Säännöllisen kielen pumppaaminen. Äärellisen automaatin minimointi. | Kielen luokittelu säännölliseksi tai ei-säännölliseksi. Säännöllisten kielten sulkeumaominaisuudet annettujen operaatioiden suhteen. | |
| 2. | Chomskyn kielioppi- ja kielityypit (säännölliset kielet, CF-kielet, CS-kielet, laskettavat kielet, laskettavasti numeroituvat kielet) perusominaisuuksineen. | ||
| 3. | CF-kieliopit ja -kielet perusominaisuuksineen. Pinoautomaatit perusominaisuuksineen. CF-kielioppien normaalimuodot. CF-kielten pumppaaminen. CF-kielioppien yksiselitteisyys ja jäsennys. | Kielten luokittelu CF-kieleksi tai ei-CF-kieleksi. CF-kielten sulkeumaominaisuudet annettujen operaatioiden suhteen. | CF-kielten ratkeamattomuustulokset. Postin vastaavuusprobleema. |
| 4. | CS-kieliopit ja -kielet sekä pituutta kasvattavat kieliopit perusominaisuuksineen. Normaalimuodot. Lineaarisesti rajoitetut automaatit perusominaisuuksineen. CE-kielet ja Turingin koneet perusominaisuuksineen. Laskettavuuden käsite. | Kielten luokittelu CS-kieleksi tai ei-CS-kieleksi. Turingin koneiden variantit. | |
| 5. | Koodit perusominaisuuksineen. Sardinas-Patterson-algoritmi ja sen soveltaminen yksinkertaisiin esimerkkeihin. Prefiksikoodit ja rajoitetun viipeen koodit. Huffmanin koodausalgoritmi ja sen soveltaminen yksinkertaisiin esimerkkeihin. | Huffmanin algoritmin soveltaminen mutkikkaammissa tapauksissa. | |
| 6. | Lindenmayerin systeemit perusomaisuuksineen. | Kielten luokittelu eri L-kieliperheisiin. | |
| 7. | Formaalit potenssisarjat perusominaisuuksineen ja -operaatioineen. Esimerkkeinä multikielet, stokastiset kielet, kvanttikielet ja sumeat kielet. |
Opintojakson arvostelu
Arvosana määräytyy harjoitusten ja tentin perusteella. Läpipääsyyn vaaditaan hyväksytysti suoritettu tentti. Hyväksymisraja tentissä on maksimista puolet tai alempi. Tentissä saatuja, hyväksymisrajan ylittäneitä pisteitä voi parantaa harjoituksissa aktiivisesta osallistumisesta etukäteen saaduilla pisteillä eri taulukon mukaan. Ydinaineksen hallitseminen hyvin riittää opintojakson läpäisemiseen arvosanalla 3. Arvosanan 4 saavuttamiseksi on osattava myös täydentävän tietämyksen asioita. Arvosanaa 5 varten on osattava täydentävän tietämyksen asioita hyvin.
Arvosteluasteikko:
Opintojaksolla käytetään numeerista arviointiasteikkoa (1-5)
Osasuoritukset:
Oppimateriaali
| Tyyppi | Nimi | Tekijä | ISBN | URL | Painos,saatavuus... | Tenttimateriaali | Kieli |
| Kirja | Introduction to Languages and the Theory of Computation | Martin, J.C. | Englanti | ||||
| Kirja | Theory of Formal Languages with Applications | Simovici, D.A. & Tenney, R.L. | Englanti | ||||
| Luentokalvot | Formaalit kielet | Ruohonen, K. | Suomi | ||||
| Muu verkkomateriaali | Kotisivu | Suomi | |||||
| Opintomoniste | Formaalit kielet | Ruohonen, K. | Suomi |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| MAT-21161 Algoritmimatematiikka | Suositeltava |
Esitietoketju (Vaatii kirjautumisen POPiin)
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
|
|
|
|
|
|
|
Vastaavuus 1 = 1 |
Lisätiedot
Kurssi luennoidaan joka toinen lukuvuosi.
Soveltuu jatko-opinnoiksi
Ei luennoida lukuvuonna 2010-2011
Tarkempia tietoja toteutuskerroittain
| Toteutus | Kuvaus | Opetusmuodot | Toteutustapa |
Opintojaksoon liittyvät dokumentit