Kursas skiriamas gilesniam teorinės informatikos sričių nagrinėjimui. Kurso struktūra apima šias teorinės informatikos temas: formaliosios kalbos ir formaliosios gramatikos sąvoka; Chomskio klasifikacija; formaliosios pirmos eilės kalbos; termų ir formulių įvertinimas; kalbos sintaksė ir semantika; formulių teisingumas ir realizuojamumas kalbos modelyje; formulių išvedamumas bei formaliosios loginės ir dalykinės teorijos, teoremos ir įrodymai; loginio programavimo samprata; baigtinio automato teorija; Tiuringo mašina; algoritmo sudėtingumo teorija; NP-pilnumas bei efektyvūs algoritmai NP-pilniems uždaviniams spręsti; Kolmogorovo sudėtingumas; naturalios kalbos teorija.
- Dėstytojas: Dalia Baziukė