Maht: 64 tundi auditoorset tööd (32 t. loenguid, 32 t. praktikume), 96 t. iseseisvat tööd

1 semester, 4 tundi nädalas

6 EAP

Eeldusained: MTAT.06.019 Matemaatika arvutuslingvistidele I

Sisu lühikirjeldus: Kursuses käsitletakse arvutilingvistikas vajalikke mõisteid algebrast, formaalsete keelte ja automaatide teooriast ning tõenäosusteooriast ja matemaatilisest statistikast.

Kohustuslik kirjandus:
1. B.H. Partee, A. ter Meulen, R.E.Wall. Mathematical Methods in Linguistics. Kluwer, 1990. (Olemas üldkeeleteaduse raamatukogus.)
2. C.D. Manning, H. Schütze. Foundations of Statistical Natural Language Processing. MIT, 2001.

 Vt. ka
http://www.ifi.unizh.ch/CL/schacht/index.html Mathematische Grundlagen der Computerlinguistik
http://www.coli.uni-sb.de/~saurer/lehre/ws00/mg1-ws00.html Mathematische Grundlagen der Computerlinguistik I: Mengenlehre, Algebra und Logik
http://www.coli.uni-sb.de/~saurer/lehre/ss00/mg2/mg2-ss00.html Mathematische Grundlagen der Computerlinguistik II: Formale Sprachen und Automaten
F.D.Lewis. Essentials of Theoretical Computer Science

Programm

l - loeng, p - praktikum, i - iseseisev töö

I. ALGEBRA. [1], lk. 249-316.

1. Algebra põhimõisted. Algebra mõiste. Operatsioonide omadused. Kujutused ja morfismid. (2 l, 2 p, 6 i)
2. Operatsioonilised struktuurid. Rühmad. Alamrühmad, poolrühmad, monoidid. (2 l, 2 p, 6 i)
3. Võred. Osaliselt järjestatud hulgad, duaalsus ja diagrammid. Võred, poolvõred ja alamvõred. Morfismid võredes. Filtrid ja ideaalid. (4 l, 4 p, 9 i)
4. Boole'i ja Heytingi algebrad. Boole'i algebra. Boole'i algebra mudelid. Esitus hulkade abil. Heytingi algebra. Kripke semantika. (4 l, 4 p, 9 i)

• Põhimõisted. Grammatika, keel, automaat. Chomsky hierarhia. Puud. (2 l, 2 p, 6 i)
• Lõplikud automaadid, regulaarsed keeled ja regulaarsed grammatikad. Lõplikud automaadid. Regulaarsed grammatikad. Regulaarsed keeled. Nende omadused. (2 l, 2 p, 6 i)
• Magasinmäluga automaadid, kontekstivabad keeled ja kontekstivabad grammatikad. Magasinmäluga automaadid. Kontekstivabad grammatikad. Kontekstivabad keeled. Nende omadused. (4 l, 4 p, 9 i)
• Turingi masinad, rekursiivselt loetletavad keeled ja 0-tüüpi grammatikad. Turingi masinad. Churhi hüpotees. Rekursiivsed ja rekursiivselt loetletavad hulgad. Turingi masina peatumise probleem. (2 l, 2 p, 6 i)
• Lineaarselt tõkestatud automaadid, kontekstitundlikud keeled ja kontekstitundlikud grammatikad. Lineaarselt tõkestatud automaadid. Kontekstitundlikud grammatikad. Kontekstitundlikud keeled ja rekursiivsed hulgad. Nende omadused. (4 l, 4 p, 9 i)

• Tõenäosusruum. Tinglik tõenäosus ja sõltumatus. (2 l, 2 p, 6 i)
• Bayesi teoreem. Juhuslikud muutujad. (2 l, 2 p, 6 i)
• Jaotused. Diskreetsed jaotused: binoomjaotus. Bayesi statistika. (2 l, 2 p, 6 i)

Kordamisküsimused

Hinde kujunemine: 30% kodused ülesanded, 20% kontrolltööd (8. ja 16. nädalal), 50% eksam.
Eksamil: 1. mõisted ja teoreemide sõnastused (5), 2. ülesanded (5).

Eksam neljapäeval, 3. juunil 9.00-11.00 Liivi 2-202.

Koduste ülesannete lahendamine