Изчислимост и сложност (2013/2014) Изб.

Курсът е разделен на две части. В първата се въвеждат изчислимите функции в
естествените числа и се доказват основните им свойства. Дискутират се резултати за
алгоритмична неразрешимост. Доказват се Първа и Втора теорема за рекурсията. Във
втората част се въвежда Машинно независимата теория на сложността. Доказват се
основните теореми, свързани с абстракната теория на сложността, сред които
теоремите за пропастта и за ускорението.

Основна литература:

И. Сосков, А. Дичев, Теория на програмите, Университетско издателство, 1997.
А. Соскова, Ст. Николова, Теория на програмите в задачи, Софтех, 2001.