Понятие темпоральной логики. Темпоральные операторы. Некоторые операторы и правила темпоральной логики. Формальная верификация. Теоретические основы верификации. Классы темпоральных логик.

Тема 2.7. Нечеткая и модальные логики

Введение в основы нечеткой логики. Нечеткая логика – новая мощная технология. Понятие нечеткого множества. Операции с нечеткими множествами. Нечеткое управление. Создание нечеткой базы знаний. Приложения нечеткой логики. Модальные логики. Модальность суждений. Модальные характеристики суждений. Область применения модальной логики. Законы модальной логики. Классы модальных логик.

Тема 2.8. Нечеткая арифметика

Нечеткая арифметика. Функция принадлежности нечеткого числа. Дискретизация значений алгебраической суммы. Изменение результата нечеткого обобщения при увеличении числа дискрет.

Тема 2.9. Аксиоматическая логика Ч. Хоара

Алгоритмическая логика Хоара. Смысловое значение логики Хоара. Решение проблемы невыразимости. Аксиомы логики Хоара. Тройки Хоара. Частичная и полная корректность. Правила логики Хоара.

Тема 2.10. Аксиоматические системы

Аксиоматический метод. История аксиоматики. Аксиоматический метод как способ построения научной теории. Первая стадия развития аксиоматического метода. Вторая стадия развития аксиоматического метода. Третья стадия развития аксиоматического метода.

Тема 2.11. Формальный вывод

Формальная логика и мышление, вывод и рассуждение. Формальный вывод в языкознании. Формальный вывод в физике. Понятия формальной логики. Характеристики предметности в формальной логике. Философия познания и формальный вывод.

Тема 2.12. Метатеория формальных систем

Понятие метатеории. Метаязык. Требования к Метатеории. Цель метатеоретических исследований. Взаимоотношение между Метатеорией и предметной теорией. Метаматематика. Вклад Гёделя в Метатеорию.

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

1. Сформулируйте основные положения логики предикатов.

2. Какие операции осуществимы с предикатами?

3. Дайте определение кванторов?

4. Приведите основные законы использования кванторов.

5. Как доказывается истинность предикатных формул?

6. Раскройте алгоритм получения клаузальной формы.

7. Как осуществляется преобразование в клаузальную форму?

8. Как осуществляется сколемизация?

9. Как осуществляется вывод в формальной логической системе?

10. В чем сущность операции унификации?

11. Раскройте сущность темпоральной логики.

12. Сформулируйте правила темпоральной логики.

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

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

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

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

17. Приведите основные законы модальной логики.

18. Что такое «нечеткая арифметика»?

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

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

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

22. Что такое метатеория?

23. Что такое метаязык?

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

3. Раздел: Теория алгоритмов

Тема 3.1. Понятие алгоритмической системы

Понятие алгоритма. Подходы к формализации понятия "алгоритм". Машина Поста. Машина Поста – универсальный вычислитель. Нормальные алгоритмы Маркова. Алгоритм на основе ассоциативного исчисления. Способы композиции нормальных алгоритмов.

Тема 3.2. Рекурсивные функции

Определение рекурсивной функции. Теория вычислимости. Примитивно рекурсивные функции. Операторы подстановки и примитивной рекурсии. Рекурсия для арифметических функций. Частично рекурсивные функции. Общерекурсивные функции. История возникновения названий

Тема 3.3. Формализация понятия алгоритма

Математическое уточнение понятия «Алгоритм». Связь между функцией и алгоритмом. Различия между понятиями алгоритма и функции. Понятийный аппарат алгоритма.

Тема 3.4. Машина Тьюринга

Понятие машины Тьюринга. Общая характеристика машины Тьюринга. Машины Тьюринга для реализации различных алгоритмов. Универсальная машина Тьюринга. Исследования по теории вычислимости. Устройство машины Тьюринга. Описание машины Тьюринга. Полнота по Тьюрингу.

Тема 3.5. Тезис Черча

Тезис Чёрча–Тьюринга. Доказательство теоремы об арифметических функциях. Тезис Тьюринга-Черча и алгоритмически неразрешимые проблемы. Частично рекурсивные функции. Оператор минимизации M. Определение частично рекурсивной функции. Вычислимость частично рекурсивной функции.

Тема 3.6. Алгоритмически неразрешимые проблемы

Проблема разрешения. Значение машины Тьюринга для рассмотрения проблемы разрешимости. Примеры алгоритмически неразрешимых проблем. Причины, ведущие к алгоритмической неразрешимости. Отсутствие общего метода решения задачи. Информационная неопределенность задачи. Логическая неразрешимость.

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

Основные меры сложности алгоритма. Основные определения. Временная сложность в худшем и в среднем случае. Порядок определения временной и емкостной сложности. Критерии оценки сложностей.

Тема 3.8. Легко и трудноразрешимые задачи

Постановка проблемы. Понятие задачи. Формы задач (проблем). Решение задач – неотъемлемая потребность человеческой деятельности. Требования к задачам «с точки зрения» ЭВМ. Интеллектуальные задачи. Классификация задач по их конечным целям. Классификация задач по методам их решения и сложности.

Тема 3.9. Классы задач P и NP

Вычислительные особенности решения задач. Вариативность решения задач. Разграничение задач по сложности. Пути разграничения сложности задач. Пример переборной задачи. Задача распознавания. Понятие полиномиальной сводимости.

Тема 3.10. NP-полные задачи

Универсальность NP-полных проблем. Класс NP-трудных проблем. Примеры NP-полных задач. Задача о k-выполнимости. NP-задача ВЫПОЛНИМОСТЬ. Недетерминированная машина Тьюринга.

Тема 3.11. Понятие сложности вычислений

Классические представления о сложности. Основные положения теории вычислений. Временная и пространственная сложности. Асимптотическая сложность. Трудноразрешимые задачи или неэффективные алгоритмы. Оценки сложности задач, ориентированные на машину Тьюринга. Алгоритмы Магу. Задача о клике.

Тема 3.12. Эффективные алгоритмы

Трудоемкость, эффективность и сложность алгоритма. Понятие эффективности алгоритма. Рандомная сортировка. Блинная сортировка. Задача о подгоревших блинах. Блочная сортировка. Быстрая сортировка. Глупая сортировка. Гномья сортировка. Пирамидальная сортировка. Зависимость понятия «эффективность» от сопутствующих факторов. Эффективность на примерах работы генетического алгоритма.

Тема 3.13. Основы нечеткой логики

Понятие нечёткой логики. Преимущества нечеткой логики. Этапы развития нечеткой логики. Области применения нечеткой логики. Пакет MatLab. Основы нечеткой логики. Горизонты использования. Отличие от традиционной математики. Недостатки нечетких систем. Пример решения бытовой задачи.

Тема 3.14. Элементы алгоритмической логики

Интуитивное представление об алгоритмах. Неформальное понятие алгоритма. Требования к алгоритмам. Влияние исходных данных на работу алгоритма. Определение алгоритма. Необходимость уточнения понятия алгоритм. Алгоритмические логики.