Kursused ITT0050: "Rekursiooni- ja  keerukusteooria" ja ITB8821: "Arvutamisteooria"

2018/19 sügissemester

TTÜ õppekavad: IAPM02, IABB02, IAPB02, IASB02


Õppeaine eesmärk:

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

Õpiväljundid:

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;
  • Church-Turingi teesi ja oskab teoreetiliselt põhjendada ülesannete mittelahenduvust;
  • klassikalisi keerukusklasse, sh P ja NP, ning oskab hinnata algoritmide ja ülesannete keerukust.



Materjalid ja teated osalevatele tudengitele ja teistele huvilistele:


Uuendatud: 12.01.2019

jaan@cs.ioc.ee