Приводится формализация понятия «алгоритм». Обсуждаются два способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы.

Содержание

ФОPМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОPИТМА

Определение

Нормальный алгоритм Маркова

Тезис Маркова

Машина Тьюринга

Основная гипотеза теории алгоритмов (тезис Чёрча)

Универсальная машина Тьюринга

МЕPЫ СЛОЖНОСТИ АЛГОPИТМОВ

Оценка алгоритма

Практические и NP-полные алгоритмы

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

«Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы.» ( из стандарта специальности ВМКСС, дисциплина «Математическая логика и теория алгоритмов)

ФОPМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОPИТМА

Определение

Задача (массовая задача) - некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров, или свободных переменных, конкретные значения которых не определены. Задача определяется 1) общим списком параметров, 2) формулировкой тех свойств, которым должен удовлетворять ответ (решение задачи).

Индивидуальная задача получается из массовой, если всем параметрам массовой задачи присвоить конкретные (допустимые) значения.

Под алгоритмом принято понимать конечную последовательность операций, называемых элементарными, исполнение которой приводит к решению любой задачи из заданного множества задач. В это определение входят такие свойства алгоритма, как дискретность, конечность (конечное число выполняемых операций), массовость (решается не единственная задача, а их класс), результативность (в результате получаем решение задачи). Кроме того, должно выполнятся ещё одно необходимое свойство алгоритма – детерминизм, которое определяется как однозначное понимание каждой операции, или, что то же самое, независимость результата выполнения каждой элементарной операции от того, кто её выполняет.

Под это определение подходит широкий круг алгоритмов. Это может быть алгоритм вычисления математической функции, алгоритм технологического процесса, алгоритм проектирования ЭВМ или цеха завода и т.д. Элементарные операции могут быть достаточно сложными: при вычислении функции это может быть, например, нахождение корней уравнения, в проектных или технологических алгоритмах – принятие сложных проектных или технологических решений.

Данное выше определение алгоритма не является формализованным и строгим по двум причинам. Во-первых, в нём не формализовано понятие элементарной операции, и, во-вторых, не формализовано представление последовательности операций. Важность разработки общего для всех алгоритмов формального описания заключается в том, что оно даёт возможность иметь общие инструментарии для сравнения, оценки, преобразования и других действий над алгоритмами.

Формализация операций алгоритмов связано со следующим. Любой алгоритм определён для некоторого объекта действия, каждый объект представляется в виде описания, причём описанием может быть не только тексты на языке, но и рисунки, чертежи и т.п. Значит, можно предположить, что объект описан в виде слова в заданном алфавите.

Объект может находиться в различных состояниях, чему соответствуют различные слова. Так, объектом для математических алгоритмов являются математическое описание задачи в форме матриц коэффициентов, графа смежности и т.п.т., для проектных алгоритмов – проектируемый объект в виде технического задания на проектирование или перечень требований и условий к результату.

Операция определяется над описанием объекта и её результатом является новое (изменённое) описание (новое слово). Например, если решается графовая задача, то результатом операции может быть описание графа с промежуточным взвешиванием рёбер и/или вершин. Результатом проектной операции будет более полное, уточнённое описание объекта.

Результатом работы всего алгоритма в графовой задаче может быть выделенный путь или цепь, частичный подграф или веса вершин или ребер. Результатом работы алгоритма проектирования является описание объекта проектирования, достаточное для его изготовления в заданной технологической базе.

Рассмотрим несколько способов формального описания алгоритмов.

Нормальный алгоритм Маркова

Алгоритмическая система, созданная А.А.Марковым, основана на соответствии между словами в абстрактном алфавите A.

Алгоритм задают в виде системы подстановок, реализующих отображение слов pi в слова qi.

pi ® qi=1,…,k.

Порядок подстановок зафиксирован. Объектом i-й элементарной операции алгоритма является слово в алфавите A, операция состоит в нахождении в этом слове первого слева вхождения слова pi и замене его на qi. Результатом операции будет изменённое слова, если вхождение найдено, или входное слово, если не найдено.Факт замены фиксируется и используется в организации следования операций.

Исходное задание представляется некоторым словом в алфавите A. Это слово является входным для первой операции, если замена произошла, то снова выполняется первая операция, если нет, то выполняется следующая операция. После каждой операции выполняется следующая операция, если замена произошла, иначе переходят к выполнению первой операции.

Алгоритм удобно представить в виде ориентированного графа, вершинами которого являются элементарные операторы и распознаватели.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--