МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
ИСЧИСЛЕНИЯ
1. Исчисление высказываний.
1.1. Алгебра высказываний
1.2. Приложения алгебры высказываний .
1.2.1. Функции алгебры высказываний (булевы функции)
1.2.2. Метод синтеза релейно-контактных схем
1.2.3. Приложение в теории множеств .
1.3. Аксиоматическая система в исчислении высказываний ..
2. Исчисление предикатов
2.1. Предикаты .
2.2. Система аксиом в исчислении предикатов
2.3. Формальная арифметика
АЛГОРИТМЫ
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. Классы сложности. Элементарные функции .
Вид литературы:
Лекции
Учебный предмет:
Математическая логика и теория алгоритмов