Контрольные вопросы по 3 разделу:

1. Как работает машина Поста?

2. В чем сущность нормальных алгоритмов Маркова?

3. Определите способы композиции нормальных алгоритмов.

4. Приведите основные положения теория вычислимости.

5. Что такое примитивно рекурсивные функции?

6. Что такое частично рекурсивные функции?

7. Что такое общерекурсивные функции?

8. Перечислите основные составляющие машины Тьюринга.

9. Дайте определение понятия «недетерминированная машина Тьюринга».

10. Сформулируйте тезис Черча.

11. Что такое алгоритмически неразрешимые проблемы?

12. В чем значение машины Тьюринга для рассмотрения проблемы разрешимости?

13. Приведите примеры алгоритмически неразрешимых задач.

14. Дайте определение понятия сложности вычислений.

15. Приведите критерии оценки сложностей?

16. Что такое легкоразрешимые и трудноразрешимые задачи?

17. Назовите отличительные особенности интеллектуальных задач.

18. Какие задачи относятся к классу NP-трудных задач?

19. Что такое асимптотическая сложность?

20. От каких факторов зависит эффективность алгоритма?

21. Перечислите основные узлы и их функции в контроллере нечеткой логики.

22. Как формулируется теорема Робинсона?

23. Перечислите алгоритм построения наиболее общего унификатора.

24. Раскройте алгоритм метода резолюций в логике предикатов.

25. Для чего используется язык логического программирования Prolog?

26. В чем заключается формальная верификация?

27. Перечислите классы темпоральных логик.

28. В чем отличие правил формулирования «нечеткой» и «чёткой» логики?

29. Что такое нечеткая логика?

30. Назовите основные операции над нечеткими множествами.

31. Какова область применения нечеткой логики?

32. Что такое модальная логика?

33. Как выглядит функция принадлежности нечеткого числа?

34. В чем сущность алгоритмической логики Хоара?

35. В чем значение алгоритмической логики Хоара для информатики?

36. Что такое частичная и полная корректность?

37. Что такое аксиоматический метод?

38. Охарактеризуйте значение аксиоматического метода для построения научной теории.

39. Что такое Метаматематика?

40. Определите связь формальной логики и мышления.

Основная литература

1. Тимофеева, И.Л. Математическая логика: курс лекций: учеб. пособие [Текст] / И.Л. Тимофеева. – 2-е изд. - М.: КДУ, 2007.

Дополнительная литература

1. Гладкий, А.В. Математическая логика [Текст] / А.В. Гладкий. – М.: РГГУ, 1998.

2. Гладкий, А.В. Введение в современную логику [Текст] / А.В. Гладкий. – М.: МЦНМО, 2001.

3. Игошин, В.И. Математическая логика и теория алгоритмов: уч. пос. [Текст] / В.И. Игошин. – М.: Академия, 2004.

4. Игошин, В.И. Задачник-практикум по математической логике: уч. пос. [Текст] / В.И. Игошин. – М.: Академия, 2006.

5. Колмогоров, А.Н. Введение в математическую логику [Текст] / А.Н. Колмогоров, А.Г. Драгалин. – М.: МГУ, 1982.

6. Клини, С. Математическая логика [Текст] / С. Клини. – М.: Мир, 1973.

7. Лавров, И.А., Максимов Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов [Текст] / И.А. Лавров, Л.Л. Максимов. – М.: Физматлит, 2004.

8. Мадер, В.В. Школьнику об алгебре логики [Текст] / В.В. Мадер. – М.: Просвещение, 1993.

9. Мендельсон, Э. Введение в математическую логику [Текст] / Э. Мендельсон. – М.: Мир, 1984.

10. Новиков, П.С. Элементы математической логики [Текст] / П.С. Новиков. – М.: Наука, 1973.

11. Столл, Р. Множества. Логика. Аксиоматические теории [Текст] / Р. Столл. – М.: Просвещение, 1968.

12. Успенский, В.А., Верещагин Н.К. Вводный курс математической логики / В.А. Успенский, Н.К. Верещагин. – М.: Физматлит, 2002.

13. Шапиро, С.И. Решение логических и игровых задач [Текст] / С.И. Шапиро. – М.: Радио и связь, 1984.

14. Шенфилд, Дж. Математическая логика [Текст] / Дж. Шенфилд. – М.: Наука, 1975.

15. Элементы логики и теории множеств: метод. разраб [Текст]. – Киров: КГПИ, 1989.