ВОПРОСЫ К ЭКЗАМЕНУ
1) Формальные модели математической логики.
2) Логика высказываний. Автоматизация доказательства теорем: метод резолюций.
3) Исчисление предикатов.
4) Теоремы Гёделя о неполноте. Доказательство корректности программ методом логического вывода.
5) Конечный автомат. Определение и границы возможностей.
6) Машина Тьюринга. Границы возможностей машины Тьюринга.
7) Языки (определение, операции над языками). Грамматики (определение). Контекстно-свободные грамматики: запись в форме Бэкуса-Наура и синтаксической диаграммы.
8) Автоматные грамматики и языки. Регулярные множества и регулярные выражения.
9) Проектирование синтаксических анализаторов.
10) Классы сложности алгоритмов.
11) Примеры алгоритмов различной сложности: алгоритмы над числами.
12) NP- полные задачи.
13) Криптография: практическое использование результатов теории сложности алгоритмов.
Возврат
