• Muuseum
• Raamatukogu
• Tartu
• Arianaltik

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 arvutilingvistidele 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.)
[Täiendav: 2. C.D. Manning, H. Schütze. Foundations of Statistical Natural Language Processing. MIT, 2001, 2003. (Olemas matemaatika-informaatika raamatukogus Liivi 2.)]

 Vt. ka
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, kontekstisidusad keeled ja kontekstisidusad grammatikad. Lineaarselt tõkestatud automaadid. Kontekstisidusad grammatikad. Kontekstisidusad 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)