Вспомогательные материалы для подготовки к экзамену - http://depositfiles.com/files/zpjhoehdj

 Вопросы к экзамену по курсу  Математическая логика и теория алгоритмов

 1.         Логические парадоксы. Критика неконструктивных доказательств. Пример – теорема о существовании иррациональных чисел p и q, что - иррационально.

2.    Формулы логики высказываний. Построение таблиц истинности. Эквивалентные формулы. Основные эквивалентности.

3.    Нормальные формы формул. Приведение к д.н.ф. и  к.н.ф.  путем эквивалентных преобразований.

4.    Теорема об эквивалентности произвольной формулы формуле, находящейся в д.н.ф и к.н.ф.

5.    Принцип двойственности. Теорема о двойственных формулах.

6.    Применение логики высказываний к построению релейно- контактных схем.

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

8.    Правило удаления противоречивой посылки.

9.    Теорема о выводимости: для произвольной формулы              и набора значений  переменных            верно  , где .

10. Доказательство в ИВ основных эквивалентностей (  и др. упр 9 стр.68 задачника).

11. Теорема полноты ИВ. Разрешимость ИВ.

12. Логика предикатов: предикаты, функции, сигнатуры. Термы и формулы. Примеры математических теорий.

13. Конгруэнтные формул.

14. Интерпретации формул логики предикатов. Общезначимые, выполнимые и противоречивые формулы. Примеры.

15. Алгоритм проверки выполнимости в конечных моделях. Неразрешимость проблемы выполнимости в общем случае.

16. Допустимые правила. Допустимость правил подстановки, обобщения и правила удаления квантора существования.

17. Нормальные формы логических формул. Теорема о приведении формулы к пренексной нормальной форме.

18. Аксиоматика ИП.  Теоремы. Примеры доказательств в ИП.

19. Лемм о добавлении отрицания невыводимой формулы и лемма Линденбаума.

20. Теорема дедукции для ИП.

21. Теорема о свидетелях.

22. Теорема полноты ИП. Следствия.

23. Классификация формул.

24. Теорема Эрбрана.

25. Формальная арифметика (ФА). Система аксиом ФА. Вывод формул  t=t  и t=rà r=t.

26. Схема аксиом индукции в ФА. Доказательство формулы .

27. Отношения  «меньше» и «меньше или равно». Доказательство формул , .

28. Представимость отношений в ФА. Представимость отношения =.

29. Представимость функций в ФА. Представимость в ФА функций x=0, s(x)=x+1 и функции выборки .

30. Примитивно рекурсивные и общерекурсивные функции. Примеры.

31. Машины Тьюринга. Тезис Черча.

32. Разрешимые и неразрешимые проблемы. Неразрешимость проблемы остановки.

33. Теорема Геделя о неполноте (схема доказательства).

34. Общее понятие алгоритма. Оценки сложности алгоритмов. Временная и пространственная сложность. Сложность как функция длины описания задачи. Примеры арифметических алгоритмов и оценка их сложности.

35. Алгоритм сортировки массива методом слияния. Оценка его сложности.

36. Рекурсивные алгоритмы. Общая оценка рекурсивных алгоритмов (без доказательства). Алгоритм умножения длинных чисел и оценка его сложности.

37. Недетерминированные машины Тьюринга. NP-трудные задачи. Классы P и NP. Примеры NP-трудные задач.

38. NP-полные задачи. Полиномиальная сводимость. NP-полнота задачи SAT.

 

 

 

Литература:

Э.  Мендельсон. Введение в математическую логику, М.:Наука, 1971, 320 с.

Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов, т.2, Языки и исчисления, М.: МЦНМО, 2000, 291 с.

И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов, изд.4,  М.:Физматлиз, 2004, 256 с.

Т.  Кормен, Ч. Лейзерсон,  Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, изд.2, Москва, 2005, 1292 с.

В.А. Носов. Основы теории алгоритмов и анализа их сложности, курс лекций, Москва, 1992, 140 с.