Введение
История развития математической логики и теории алгоритмов. Математическая логика и основания математики. Теория алгоритмов и принципиальные возможности вычислительных машин. Сложность алгоритмов и ее значение для практики. ( 2 часа )
Алгебра высказываний и алгебра предикатов
Основные логические операции и их свойства. Понятие булевой алгебры. Алгебра высказываний и алгебра подмножеств, множества как примеры булевых алгебр. Предикаты на множестве и их связь с отношениями. Логические операции над предикатами. Определение формулы алгебры предикатов. Выполнимые. Тождественно истинные и тождественно ложные формулы. Равносильность формул, основные формулы равносильности и их использование для упрощения формул. Существование для каждой формулы алгебры высказываний приведенной формы, дизъюнктивной и конънктивной нормальных форм. ( 4 часа )
Булевы функции и их обобщения
Понятие булевой функции и функций многозначной логики.Их представление формулами над заданной системой функций. Представление булевых функций формулами алгебры высказываний и многочленами Жегалкина. Критерии полноты для булевых функций и функций многозначной логики. ( 2 часа )
Исчисление высказываний
Общее понятие о логическом исчислении. Выводимость и доказуемость формул в исчислении высказываний. Непротиворечивость и полнота исчисления высказываний. ( 2 часа )
Исчисление предикатов
Язык, аксиомы и правила вывода исчисления предикатов. Вспомогательные правила вывода: правило силлогизма, правила разделения и умножения формул, правила умножения и разделения посылок, правило перестановок посылок, правило умножения заключений, правило контрапозиции, правила де Моргана, правила противоречия, закон исключенного третьего. Эквивалентность формул. Приведение формул к нормальным формам. Теорема Гёделя о полноте исчисления предикатов. Применение исчисления предикатов для записи математических утверждений и автоматического доказательства теорем. ( 2 часа )
Метод резолюций
Применение исчисления предикатов для доказательства теорем. Метод резолюций для логики предикатов. Теорема о полноте метода резолюций для логики предикатов. ( 2 часа )
Элементы теории алгоритмов
Интуитивное понятие алгоритма и его характерные черты. Необходимость уточнения понятия алгоритма. Определение нормального алгоритма. Примеры. Принцип Маркова. Композиция нормальных алгоритмов. Определение машины Тьюринга - Поста. Нумерация слов в счетном алфавите и арифметизация алгоритмов. Определение рекурсивных и частично рекурсивных функций. Примеры алгоритмически неразрешимых массовых задач. Неразрешимость проблем распознавания самоприменимости нормальных алгоритмов и самоприменимости машин Тьюринга. Теорема Чёрча о неразрешимости исчислений предикатов. Рекурсивные и рекурсивно перечислимые множества. Примеры. Теорема Клини о неподвижной точке.
( 6 часов )
Сложность алгоритмов и вычислений
Подходы к оценкам сложности алгоритмов и вычислений. Модели вычислений. Сложность вычисления на машине Тьюринга. Меры сложности. Методы построения эффективных алгоритмов. Метод разбиения и рекурсии. Сложность рекурсивных алгоритмов. Умножение чисел и матриц. Быстрое преобразование Фурье. ( 4 часа )
Теория алгоритмов и задачи использования ЭВМ
Вычислительные возможности современных ЭВМ. Модель ЭВМ - машина произвольного доступа. МПД - вычислимые функции и их связь с частично рекурсивными функциями. ( 2 часа )