misle.ru страница 1
скачать файл

Программа экзамена по дисциплине

«Математическая логика и теория алгоритмов»

для студентов II курса

специальности ПВС и направления ИВЧТ





  1. Высказывания. Формулы логики высказываний. Логические связки. Примеры.

  2. Тавтологии. Доказательство тавтологий методом обратного рассуждения. Законы логики высказываний. Примеры.

  3. Логическое следование в логике высказываний. Правила пропозиционального вывода. Примеры.

  4. Теорема о дедукции. Примеры.

  5. Принцип резолюций в логике высказываний. Примеры.

  6. Синтаксис логики предикатов. Кванторы. Связанные и свободные переменные. Примеры.

  7. Категорические высказывания. Примеры.

  8. Непосредственные заключения. Примеры.

  9. Общезначимость формул логики предикатов.

  10. Логическое следствие в логике предикатов.

  11. Неклассические логики. Истоки возникновения.

  12. Нечеткая логика. Основные определения. Область применения.

  13. Понятие алгоритма. Основные свойства алгоритмов. Эффективные алгоритмы.

  14. Машины Тьюринга.

  15. Нормальные алгоритмы Маркова. Тезис Черча.

  16. Примитивно-рекурсивные функции. Схемы рекурсии.

  17. Примеры рекурсивных функций. Рекурсивное описание.

  18. Алгоритмическая разрешимость.

  19. Меры сложности алгоритмов.

  20. Верхние и нижние оценки сложности алгоритмов.

  21. Классы задач P и NP.
скачать файл


Смотрите также: