Плиско В.Е. Теория алгоритмов. Курс лекций. - 2004. - 38 с.
Первые примеры алгоритмов встречаются уже в средней школе: алгоритм сложения натуральных чисел столбиком, алгоритм умножения двух натуральных чисел, алгоритм деления с остатком, процесс нахождения наибольшего общего делителя двух целых чисел, известный под названием алгоритма Евклида. Из других алгоритмов можно указать алгоритм разложения натурального числа на простые множители, извлечения квадратного корня из натурального числа, решения системы линейных уравнений методом Гаусса и т. д. Каждый из этих алгоритмов представляет собой некоторую вычислительную процедуру, выполнение которой не требует изобретательности или сообразительности, а состоит лишь в строгом следовании инструкциям.
Содержание
1. Основные понятия теории алгоритмов
2. Машина Тьюринга
3. Частично-рекурсивные функции
4. Машина с неограниченными регистрами
5. МНР-вычислимость частично-рекурсивных функций
6. Нумерация вычислимых функций
7. Теорема о параметризации
8. Универсальная вычислимая функция
9. Разрешимые и перечислимые множества
10. Теоремы о разрешимых и перечислимых множествах
11. Нумерация перечислимых множеств
12. Неразрешимые алгоритмические проблемы
13. Теорема Раиса
14. Десятая проблема Гильберта
15. Индексы разрешимых и конечных множеств
16. Рекурсивно неотделимые перечислимые множества
17. Теорема Раиса - Шапиро
18. Многозначная сводимость
19. Продуктивные множества
20. Креативные множества
21. Простые множества
22. m-полные перечислимые множества
23. Язык формальной арифметики
24. Арифметические множества и функции
25. Гёделева нумерация арифметических формул
26. Теорема Тарского
27. Первая теорема Гёделя о неполноте
28. Меры сложности вычислений
29. Теорема о неподвижной точке
З0. Теорема об ускорении
