- •Основные понятия и определения дисциплины.
- •История развития теории алгоритмов.
- •Роль алгоритмов в науке и технике.
- •Понятие алгоритма и алгоритмического процесса.
- •2. Формальное определение алгоритма
- •Алгоритмический процесс.
- •Основные вопросы теории алгоритмов.
- •Классификация алгоритмов.
- •Свойства алгоритмов.
- •Логика предикатов.
- •Интерпретация.
- •Истинность и выполнимость формул.
- •Нормальные алгоритмы Маркова.
- •Гипотеза Черча.
- •Машина Тьюринга.
- •Рекурсивные функции.
- •Алгоритмически неразрешенные проблемы.
- •Сложность алгоритмов.
- •Временная и вычислительная сложность.
- •Понятие p и np-задач.
- •Темпоральные логики. Нечеткая и модальные логики.
- •Примеры задач np-класса.
- •Логическое программирование.
- •Дедуктивные теории.
- •Свойства дедуктивных теорий. Противоречивость
- •Полнота
- •Независимость аксиом
- •Разрешимость
- •Формальные аксиоматические теории.
- •Свойство выводимости.
- •Логические матрицы.
- •Модели Крипке для логики высказываний.
- •Формальное определение
- •Основные понятия мЛиТа.
- •Логические функции.
- •Правила логики высказываний. Законы логики высказываний.
- •Основные понятия
- •Равносильность. Логическое следствие.
- •Кванторы.
- •Категорические высказывания. Высказывание Категорическое
- •Связанные и свободные переменные. Свободные и связанные переменные
- •Операции над кванторами
- •Общая значимость.
- •Логические функции.
- •Алгоритмы сортировки данных. Сортировка слиянием.
- •Алгоритмы сортировки данных. Сортировка «пузырьком».
- •Алгоритмы сортировки данных. Сортировка вставками.
- •Алгоритмы сортировки данных. Сортировка Шейкером.
- •Алгоритмы сортировки данных. Быстрая сортировка.
- •Алгоритмы сортировки данных. Сортировка подсчетом.
- •Моделирование алгоритмов программ с помощью блок-схем.
- •История развития математической логики.
- •Логика высказываний.
- •Булева алгебра и основные логические тождества.
- •Пропозициональные формулы и логические функции.
- •Аксиоматический метод исчисления высказываний.
Примеры задач np-класса.
Задача о выполнимости.
Пусть х1, х2, …, хn – множество логических переменных; – их отрицания или дополнения.
if xi = true then = false
- И; - ИЛИ.
Дизъюнкция: х1 х5 …
Конъюнкция: х4 х3 …
Конъюнктивная нормальная форма:
E*(x1, …, xn) = (x1 x2 x3) (x1 ) ( x4) ( ) (*)
Задача о выполнимости заключается в определении, является ли булевская функция, записанная в КНФ, выполнимой.
Любая булевская функция может быть представлена в КНФ по правилу Де Моргана:
А(ВС)=( АВ)(АС)
Говорят, что булевская функция выполнима, если существует некоторое присваивание переменным true или false, при этом функция должна быть равна true.
Для функции (*) она будет выполнима, если ввести следующие присваивания:
(*)
Например:
Функция
f2(xi)=(x1 x2)( )( )
не является выполнимой, т. к. при любых xi f2(xi)=false.
Теорема:
Задача о выполнимости является NP-полной.
for i=1 to N do
xi выбор (true, false)
if E(x1, x2, …, xN) then успех
else неудача
Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным.
К-выполнимость.
К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*(х2), содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е*.
E*(x1, x2,…, xn)E*(xi)
Для этого используется метод уменьшения порядка дизъюнкта
(1 2 … k)=(1 2 z) (3 4 … k )
Применяя итерационный процесс разложения, можно получить Е*.
Найти алгоритм решения Е* проще, чем функции Е. Но при этом доказав выполнимость Е*, докажем выполнимость исходной функции Е.
Частный случай: при К=2 функция Е входит в Р.
Примерами задач NP-класса могут послужить также задачи на графах:
Определение максимума клик неориентированного графа (NP-трудная задача).
Задача определения полного подграфа (NP-полная задача).
Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).
Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).
Задача определения существования Гамильтонова цикла для графа (NP-полная задача).
Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача).
Задача составления расписания (NP-полная задача).
Логическое программирование.
Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.
Самым известным языком логического программирования является Prolog.
Первым языком логического программирования был язык Planner, в котором была заложена возможность автоматического вывода результата из данных и заданных правил перебора вариантов (совокупность которых называлась планом). Planner использовался для того, чтобы понизить требования к вычислительным ресурсам (с помощью метода backtracking) и обеспечить возможность вывода фактов, без активного использования стека. Затем был разработан язык Prolog, который не требовал плана перебора вариантов и был, в этом смысле, упрощением языка Planner.
От языка Planner также произошли логические языки программирования QA-4, Popler, Conniver и QLISP. Языки программирования Mercury, Visual Prolog, Oz и Fril произошли уже от языка Prolog. На базе языка Planner было разработано также несколько альтернативных языков логического программирования, не основанных на методе поиска с возвратами (backtracking), например, Ether.