Курсът се чете отделно за студентите от втори курс на две специалности - Компютърни науки и  Софтуерно инженерство, като материалът, усвояван в лабораторните занятия е с едно и също съдържание и разпределение по седмици.

 

Включени са тематичи описания на упражненията, съдържащи: от една страна - изброяване на материала, обект на усвояване в съответното занятие, от друга - условията на практическите задачи за реализиране в рамките на занятието.

Курсът е въведение в класическата и съвременната теория на изчислимостта. Основните теми са теорията на автоматите и формалните езици, изчислимост с машини на Тюринг, Тезис на Чърч – Тюринг, неразрешимост, сложност , класовете P и NP, NP – пълни проблеми. Подходът е математически, но от гледна точка на компютърната наука. Целта на курса е да се разгледат основните идеи, модели и резултати, свързани с теоретичните основи на програмирането.

Курсът е предназначен за студенти I курс от специалност компютърни науки. Дава приложение на темите, разгледани в курса Дискретни структури. Дава основата за курсовете: Езици за програмиране, Дизайн и анализ на алгоритми, Изчислимост и сложност и Семантики на езиците за програмиране.