- •Основные понятия и определения дисциплины.
- •История развития теории алгоритмов.
- •Роль алгоритмов в науке и технике.
- •Понятие алгоритма и алгоритмического процесса.
- •2. Формальное определение алгоритма
- •Алгоритмический процесс.
- •Основные вопросы теории алгоритмов.
- •Классификация алгоритмов.
- •Свойства алгоритмов.
- •Логика предикатов.
- •Интерпретация.
- •Истинность и выполнимость формул.
- •Нормальные алгоритмы Маркова.
- •Гипотеза Черча.
- •Машина Тьюринга.
- •Рекурсивные функции.
- •Алгоритмически неразрешенные проблемы.
- •Сложность алгоритмов.
- •Временная и вычислительная сложность.
- •Понятие p и np-задач.
- •Темпоральные логики. Нечеткая и модальные логики.
- •Примеры задач np-класса.
- •Логическое программирование.
- •Дедуктивные теории.
- •Свойства дедуктивных теорий. Противоречивость
- •Полнота
- •Независимость аксиом
- •Разрешимость
- •Формальные аксиоматические теории.
- •Свойство выводимости.
- •Логические матрицы.
- •Модели Крипке для логики высказываний.
- •Формальное определение
- •Основные понятия мЛиТа.
- •Логические функции.
- •Правила логики высказываний. Законы логики высказываний.
- •Основные понятия
- •Равносильность. Логическое следствие.
- •Кванторы.
- •Категорические высказывания. Высказывание Категорическое
- •Связанные и свободные переменные. Свободные и связанные переменные
- •Операции над кванторами
- •Общая значимость.
- •Логические функции.
- •Алгоритмы сортировки данных. Сортировка слиянием.
- •Алгоритмы сортировки данных. Сортировка «пузырьком».
- •Алгоритмы сортировки данных. Сортировка вставками.
- •Алгоритмы сортировки данных. Сортировка Шейкером.
- •Алгоритмы сортировки данных. Быстрая сортировка.
- •Алгоритмы сортировки данных. Сортировка подсчетом.
- •Моделирование алгоритмов программ с помощью блок-схем.
- •История развития математической логики.
- •Логика высказываний.
- •Булева алгебра и основные логические тождества.
- •Пропозициональные формулы и логические функции.
- •Аксиоматический метод исчисления высказываний.
Понятие p и np-задач.
В зависимости от значений функции f(N) различают следующие классы алгоритмов:
1) Задачи, для которых
f(N)=aN (линейная сложность)
Примеры: топологическая сортировка, отыскание остовного дерева и связанных компонент дерева.
2) Задачи, для которых f(N) является нелинейной, но не более чем полиномиальной
f(N)=Nm, m2
Примеры: умножение матриц, нахождение кратчайшего пути в дереве, нахождение минимума остовных деревьев.
3) Задачи, о которых нельзя сказать, что они обязательно имеют экспоненциальную сложность, но для которых не известны быстрые алгоритмы, требующие менее, чем kn операций.
Примеры: задача коммивояжера (TSP), определение изоморфизма, алгоритм нахождения максимальной клики в графе.
4) Задачи с обязательной экспоненциальной сложностью
f(N)=KN , K2
Для этого класса не существует быстрых алгоритмов.
Примеры: прохождение всех остовных деревьев графа, всех его циклов и всех клик.
Для таких задач невозможно открыть новый алгоритм с меньшей сложностью.
Замечание: Для 3-го класса задач существуют теоретические предпосылки разработки эффективных алгоритмов с полиномиальной сложностью (класса 2), но которые пока не найдены. Разработка полиномиального алгоритма для любой из задач 3-го класса автоматически означала бы решение всех задач этого класса за полиномиальное время.
В недетерминированном алгоритме (НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора.
НДА не является случайным или вероятностным алгоритмом. Он представляет собой алгоритм, который может находиться во многих состояниях (это эквивалентно параллельному решению задачи с множеством вариантов).
Полиномиальный алгоритм – это алгоритм с полиномиальной трудоемкостью (временем работы).
Полиномиальный или экспоненциальный характер работы алгоритма инвариантен относительно формы представления входных данных (двоичная, десятичная или другая система счисления).
Говорят, что алгоритм является полиномиальным, если время его работы, т. е. временная сложность, ограничивается сверху полиномом некоторой степени T(N)=O(Nm). Тогда все задачи, которые решаются таким алгоритмом, образуют Р-класс задач. Говорят, что эти задачи входят в Р.
Задачи, временная сложность которых экспоненциальна (T(N)=O(KN)), не входят в Р.
NP- трудные и NP-полные задачи.
Задача, входящая в Р, является NP-трудной, если существует полиномиальный ДА (ПДА) ее решения, который модно использовать для получения решения всех задач, входящих в NP. Т. е. такая задача является NP-трудной, если она, по крайней мере, так же трудна, как любая задача, входящая в NP.
NP-трудная задача, принадлежащая NP, называется NP-полной задачей. Такие задачи не менее трудны, чем любая задача из NP. При этом существование ПДА для NP-трудной или NP-полной задачи означает, что классы Р и NP совпадают, т. е. возможно решение всех задач 3-го класса быстрым алгоритмом.
Для доказательства того, что задача является NP-трудной, необходимо показать, что если для задачи существует ПДА, то его можно использовать для получения другого ПДА решения задач, входящих в NP.
Чтобы установить, что задача является NP-полной, необходимо доказать, что она принадлежит NP.
Идея использовать алгоритм решения одной задачи для получения алгоритма решения другой является одной из наиболее важных в теории алгоритмов.
Определение 1: Задача Р1 преобразуется в задачу Р2, если любой частный случай задачи Р1 можно преобразовать за полиномиальное время в некоторый частный случай задачи Р2. Тогда решение Р1 можно получить за полиномиальное время из решения частного случая задачи Р2.
Если Р1Р2 и Р2Р, то и Р1Р.
Определение 2: Задача является NP-трудной, если каждая задача, входящая в NP, преобразуется в нее. Задача является NP-полной, если она является одновременно NP-трудной и принадлежит NP.