ПРОГРАМА КУРСА МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ТЕОРИИ АЛГОРИТМОВ
ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ
Формальные модели.
Логика высказываний. Автоматизация доказательства теорем: метод резолюций.
Исчисление предикатов (предикаты, кванторы, свойства, свободные и связанные переменные, логический вывод в логике предикатов). Теоремы Гёделя о неполноте. Доказательство корректности программ методом логического вывода.
ТЕОРИЯ АЛГОРИТМОВ.
Конечный автомат. Определение и границы возможностей (невозможность реализации алгоритма перемножения натуральных чисел).
Машина Тьюринга. Пример программы умножения натуральных чисел в единичной записи.
Границы возможностей машины Тьюринга: теорема Райса (проблема останова).
ЯЗЫКИ И ГРАМАТИКИ
Языки (определение, операции над языками). Грамматики (определение). Контекстно-свободные грамматики:
запись в форме Бэкуса-Наура и синтаксической диаграммы. Автоматные грамматики и языки.
Регулярные множества и регулярные выражения. Проектирование синтаксических анализаторов.
СЛОЖНОСТЬ АЛГОРИТМОВ
Классы сложности алгоритмов.
Примеры алгоритмов различной сложности:
- алгоритмы над числами (обычный и расширенный алгоритм Евклида, умножение целых чисел и разложение целых чисел на множители).
Классы трудоемкости P, PC, NP.
Метод ветвей и границ.
Криптография: практическое использование результатов теории сложности алгоритмов.
