Наименование тем

Введение

История развития математической логики и теории алгоритмов. Математическая логика и основания математики. Теория алгоритмов и принципиальные возможности вычислительных машин. Сложность алгоритмов и ее значение для практики. (2 часа)

Алгебра высказываний и алгебра предикатов

Основные логические операции и их свойства. Понятие булевой алгебры. Алгебра высказываний и алгебра подмножеств, множества как примеры булевых алгебр. Предикаты на множестве и их связь с отношениями. Логические операции над предикатами. Определение формулы алгебры предикатов. Выполнимые. Тождественно истинные и тождественно ложные формулы. Равносильность формул, основные формулы равносильности и их использование для упрощения формул. Существование для каждой формулы алгебры высказываний приведенной формы, дизъюнктивной и конънктивной нормальных форм. (4 часа)

Булевы функции и их обобщения

Понятие булевой функции и функций многозначной логики.Их представление формулами над заданной системой функций. Представление булевых функций формулами алгебры высказываний и многочленами Жегалкина. Критерии полноты для булевых функций и функций многозначной логики. (2 часа)

Исчисление высказываний

Общее понятие о логическом исчислении. Выводимость и доказуемость формул в исчислении высказываний. Непротиворечивость и полнота исчисления высказываний. (2 часа)

Исчисление предикатов

Язык, аксиомы и правила вывода исчисления предикатов. Вспомогательные правила вывода: правило силлогизма, правила разделения и умножения формул, правила умножения и разделения посылок, правило перестановок посылок, правило умножения заключений, правило контрапозиции, правила де Моргана, правила противоречия, закон исключенного третьего. Эквивалентность формул. Приведение формул к нормальным формам. Теорема Гёделя о полноте исчисления предикатов. Применение исчисления предикатов для записи математических утверждений и автоматического доказательства теорем. (2 часа)

Метод резолюций

Применение исчисления предикатов для доказательства теорем. Метод резолюций для логики предикатов. Теорема о полноте метода резолюций для логики предикатов. (2 часа)

Элементы теории алгоритмов

Интуитивное понятие алгоритма и его характерные черты. Необходимость уточнения понятия алгоритма. Определение нормального алгоритма. Примеры. Принцип Маркова. Композиция нормальных алгоритмов. Определение машины Тьюринга - Поста. Нумерация слов в счетном алфавите и арифметизация алгоритмов. Определение рекурсивных и частично рекурсивных функций. Примеры алгоритмически неразрешимых массовых задач. Неразрешимость проблем распознавания самоприменимости нормальных алгоритмов и самоприменимости машин Тьюринга. Теорема Чёрча о неразрешимости исчислений предикатов. Рекурсивные и рекурсивно перечислимые множества. Примеры. Теорема Клини о неподвижной точке.

(6 часов)

Сложность алгоритмов и вычислений

Подходы к оценкам сложности алгоритмов и вычислений. Модели вычислений. Сложность вычисления на машине Тьюринга. Меры сложности. Методы построения эффективных алгоритмов. Метод разбиения и рекурсии. Сложность рекурсивных алгоритмов. Умножение чисел и матриц. Быстрое преобразование Фурье. (4 часа)

Теория алгоритмов и задачи использования ЭВМ

Вычислительные возможности современных ЭВМ. Модель ЭВМ - машина произвольного доступа. МПД - вычислимые функции и их связь с частично рекурсивными функциями. (2 часа)