Opinto-opas 2010-2011
Jatko

Perus Pori KV Jatko Avoin

|Tutkinnot|     |Opintokokonaisuudet|     |Opintojaksot|    

Opinto-opas 2010-2011

MAT-41180 Formaalit kielet, 6 op
Formal Languages

Vastuuhenkilö

Keijo Ruohonen

Opetus

Opetusmuoto P1 P2 P3 P4 Kesä Toteutuskerrat Luentoajat ja -paikat
            MAT-41180 2011-01  

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:

Osasuoritusten pitää liittyä samaan toteutuskertaan

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 
MAT-41180 Formaalit kielet, 6 op 73118 Formaaliset kielet, 3 ov  
MAT-41180 Formaalit kielet, 6 op MAT-41186 Formal Languages, 6 op 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
MAT-41180 2011-01        

Opintojaksoon liittyvät dokumentit

FK.pdf

Viimeksi muokattu25.10.2010