Kursuse ITB8821: "Arvutamisteooria" veebipesa

2019/20 sügissemester

TTÜ õppekavad: IABM11,  IABM12,  IABM13,  IAPM31





Teated:


Õ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: 07.10.2019

jaan@cs.ioc.ee