Гамова А.Н. Математическая логика и теория алгоритмов: Учеб.пособие для студентов мех.- мат. фак. и фак. компьют. наук и информ. техн.- 3-е изд., доп. - Саратов: Изд-во Сарат. ун-та, 2005. - 80с: ил. ISBN 5–292–02515-1
Учебное пособие состоит из двух разделов: исчисления и алгоритмы. Теоретический материал сопровождается примерами решения задач и упражнениями.
Для студентов механико-математического факультета и факультета компьютерных наук и информационных технологий, а также аспирантов.
Содержание
Предисловие.
Введение.
РАЗДЕЛ 1. ИСЧИСЛЕНИЯ
Глава 1. Исчисление высказываний.
1.1. Алгебра высказываний.
1.2. Приложения алгебры высказываний.
1.2.1. Функции алгебры высказываний (булевы функции).
1.2.2. Метод синтеза релейно-контактных схем.
1.2.3. Приложение в теории множеств.
1.3. Аксиоматическая система в исчислении высказываний.
Глава 2. Исчисление предикатов.
2.1. Предикаты.
2.2. Система аксиом в исчислении предикатов.
2.3. Формальная арифметика.
РАЗДЕЛ 2. АЛГОРИТМЫ
Глава 1. Алгоритмы и вычислимые функции.
1.1. Машины Тьюринга.
1.2. Частично рекурсивные функции.
1.2.1. Класс примитивно рекурсивных функций.
1.2.2. Рекурсивно перечислимые множества и предикаты.
1.2.3. Порожденные множества.
1.2.4. Функции на n-ках.
1.2.5. Рекурсия второй ступени.
1.2.6. Универсальная функция.
1.2.7. Универсальные частично рекурсивные функции.
Глава 2. Приложения теории алгоритмов.
2.1. Теоремы о рекурсии и неполноте.
2.2. Разрешимость и неразрешимость формальных систем.
Глава 3. Сложность вычислений.
3.1. Меры сложности.
3.2. Теорема об ускорении.
3.3. Классы сложности. Элементарные функции.
Список литературы
