Ссылки на литературу по перечисленным вопросам:
Формальные модели. Логика высказываний.
(КА гл. 6, п. 6.1, 6.2 с. 217-261)
(НО гл.4, п.4.1-4.3, с. 100-118)
Автоматизация доказательства теорем: метод резолюций.
(НО гл. 4, п.4.5, с. 127-133)
Исчисление предикатов (предикаты, кванторы, свойства, свободные и связанные переменные, логический вывод в логике предикатов). Теоремы Гёделя о неполноте. Доказательство корректности программ методом логического вывода.
(НО гл.4, п.4.4, с. 118-127).
Конечный автомат. Определение и границы возможностей (невозможность генерации непериодической последовательности).
(КА гл.8, с. 295-298, с.316)
Машина Тьюринга. Пример программы умножения натуральных чисел в единичной записи.
Границы возможностей машины Тьюринга: теорема Райса (проблема останова).
(КА г.5, с.144-162, 176-178)
Языки (определение, операции над языками). Грамматики (определение).
Контекстно-свободные грамматики: запись в форме Бэкуса-Наура и синтаксической диаграммы.
(КА гл.7, п.7.1, с.261-279)
Автоматные грамматики и языки. Регулярные множества и регулярные выражения.
(КА гл.8, п.8.2, с.313-330)
Проектирование синтаксических анализаторов.
(ВТ, гл.5, п.5.1, 5.2, 5.3, 5.4, с.319-335)
Примеры алгоритмов различной сложности: алгоритмы над числами (обычный и расширенный алгоритм Евклида, умножение целых чисел и разложение целых чисел на множители).
(ВИ гл.1, параграф 1, с.7-24).
Классы трудоемкости P, PC, NP.
(КА гл.9, п.9.1, 9.2, с. 351-358, 381-384, 398-399)
Метод ветвей и границ.
(КА гл.9, п.9.3, с.399-411)
Криптография: практическое использование результатов теории сложности алгоритмов.
(ВИ гл.2, параграф 5, гл.3, параграф 1-6, с.30-48)
(НО гл.6, п.6.5, с.180-188)
Возврат
