КОНСПЕКТ

за курса по Теоретични основи на функционалното програмиране, четен през летния семестър на 2001/2002 уч. година

  1. Частични функции и предикати в дадено множество. Композиция, разклонение и итерация.
  2. Московакисово разширение на множество. Проста изчислимост на функция относно дадено множество от функции.
  3. Проста изчислимост на функции на няколко променливи.
  4. Представяне на частично рекурсивните функции чрез просто изчислими функции в произволно Московакисово разширение.
  5. Проста изчислимост на частично рекурсивни функции.
  6. Просто разрешими множества.
  7. Просто полуразрешими множества.
  8. Итерацията като неподвижна точка. Едновременна рекурсия.
  9. Непрекъснати монотонни изображения в области на Скот.
  10. Монотонност и непрекъснатост на просто изчислимите изображения.
  11. Тъждества, чрез които може да се пресмятат рекурсивно определени функции в едно Московакисово разширение.
  12. Привеждане на едновременната рекурсия към каноничен вид.
  13. Итеративен метод за намиране на стойностите на рекурсивно определени функции.
  14. Построяване на най-малкото решение на система от каноничен вид с помощта на итеративния метод.
  15. Проста изчислимост на рекурсивно определените функции.
  16. Действия с функции, зависещи от параметри.
  17. Универсални просто изчислими функции.
  18. Втора теорема за рекурсия и теорема на Райс-Успенски в теорията на просто изчислимите функции.
  19. Дефиниция на проста изчислимост без използване на итерация, но с използване на рекурсия.
  20. Програма на Пролог за универсална просто изчислима функция - твърдение за коректност.
  21. Програма на Пролог за универсална просто изчислима функция - твърдение за пълнота.