Opinto-opas 2003-2004

73118 FORMAALISET KIELET, FORMAL LANGUAGES, 3 ov

Tietoa luennoitsijoista
Professori KEIJO RUOHONEN

Luentoja ja harjoituksia
Luentoja yhteensä 42 h
Harjoituksia yhteensä 28 h

Viikottainen opetus/periodi	S1	S2	K1	K2	Kesä
Luennot (h):	3+	3	-	-	-
Harjoitukset (h):	2+	2	-	-	-

Tavoitteet
Perehtyminen kielten formaaliin teoriaan sekä sen yhteyksiin mm. laskettavuuden ja algoritmien teoriaan.

Sisältö
Formaalien kielten perusominaisuudet. Chomskyn kielioppityypit. Kielten tunnistamiseen käytetyt automaatit (FA, PDA, LBA, TM). Kooditeoriaa (koodit, prefiksikoodit, rajoitetun viipeen koodit, optimikoodit, Huffmanin koodaus).

Tutkintovaatimukset
Hyväksytysti suoritettu kirjallinen tentti.

Kirjallisuus
Ruohonen, K.: Formaalit kielet (kalvosarja) (sisältö, kirjallisuus) (pdf, 0.7 Mb)
Martin, J.C.: Introduction to Languages and the Theory of Computation. McGraw-Hill (-02)
Hopcroft, J.E. & Motwani, R. & Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (-01)

Esitiedot

Numero	Nimi	OV	P/S
73116	Algoritmimatematiikka	3	Suositus

Huomautuksia
Luennoidaan joka toinen vuosi, vuorovuosin kurssin 73117 Automaattiteoria kanssa. Luennoidaan lukuvuonna 2003-2004.

Kurssin kotisivu