Tutvustada kuulajatele arvutatavuse mõistet ning ülesannete algoritmilise lahendatavuse piire. Tuua näiteid mittelahenduvatest ülesannetest. Esitada sissejuhatus formaalsete keelte ja automaatide teooriasse.

Introducing the concept of computability and the limits of solving problems with algorithms. Provide examples of non-solvable tasks. Introduce the theory of formal languages and machines.

Kursuse läbinud üliõpilane:
- tunneb arvutatavuse analüüsiks kasutatavaid formaalseid mudeleid, sh lõplikke automate, magasinmäluga automate ja Turingi masinat ning oskab neid hulkade (keelte) aktsepteerimise ja rekursiivse loendamise ülesannete jaoks koostada;
- tunneb Church-Turingi teesi ja oskab teoreetiliselt põhjendada ülesannete mittelahenduvust;
- tunneb klassikalisi keerukusklasse, sh P ja NP, ning oskab hinnata algoritmide ja ülesannete keerukust.

On completion of the course, the student:
- Understands the formal models used for computability analysis, including final machines, machines with a magazine memory and the Turing machine, and can compile them for the tasks of accepting and recursively counting the amounts (languages);
- Understands the Church-Turing thesis and can theoretically explain the non-solvability of the problems;
- Understands the classic complexity classes, including P and NP, and can evaluate the complexity of algorithms and tasks.

Lõplikud automaadid ja regulaarsed keeled. Regulaarsed avaldised. Keeled ja grammatikad. Keele regulaarsuse ja kontekstivabaduse tunnused. Keelte Chomsky hierarhia. Magasinmäluga automaadid ja kontekstivabad keeled. Turingi masin. Arvutatavuse mõiste. Church-Turingi tees ja peatumisprobleemid. Lahenduvad ja rekursiivselt loenduvad hulgad. Rekursiivsed funktsioonid ja Gödeli numbrid. Algoritmide ja ülesannete keerukus. Deterministlik ja mittedeterministlik keerukus. Ajalise ja mahulise keerukuse klasside hierarhia ja täielikud keerukusklassid. Programmide tsüklomaatiline keerukus.

Finite state machines and regular languages. Regular expressions. Languages and grammar. Characteristics of language regularity and contextual freedoms. Chomsky hierarchy of languages. Machines with a magazine memory and context free languages. Turing machine. Concept of computability. Church-Turing thesis and halting problems. Solvable and recursively countable amounts. Recursive functions and Gödel numbers. Complexity of algorithms and tasks. Deterministic and non-deterministic complexity. Hierarchy of time and volume complexity classes and complete complexity classes. Cyclomatic complexity of programmes.

Eksamil on nii suuline (teooria) kui kirjalik (ülesannete lahendamine) osa. Kodu- ja kontrolltööde tulemusi võidakse arvestada lõpphinde komponendina.

The examination has both an oral (theory) and a written (problem solving) part. Homework and test results may be taken into account as a component of the final grade.

3* 16 tundi loenguid + 1*16 harjutustundi + 92 tundi iseseisvat (sisaldab ülesannete lahendamist kodutööna) tööd = 156 tundi

3* 16 h of lectures + 1* 16 h of practical work + 92 h of independent study (including solving problems as homework) = 156 h

1. Michael Sipser. Introduction to the Theory of Computation. Third Edition. Cengage Learning, 2013.
2. H.Rogers. Theory of Recursive Functions and Effective Computability (The MIT press, Cambridge, Massachusetts, 1992).
3. M. Tombak. Keerukusteooria. Tartu Ülikooli Kirjastus, Tartu, 2007.
4. Aine koduleht: http://www.cs.ioc.ee/RekKursus/

-