Теория алгоритмов (стр. 1 из 3)
Кафедра: Автоматика и информационные технологии
ТЕОРИЯ АЛГОРИТМОВ
Екатеринбург
2006
Приводится формализация понятия «алгоритм». Обсуждаются два способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач 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. Это слово является входным для первой операции, если замена произошла, то снова выполняется первая операция, если нет, то выполняется следующая операция. После каждой операции выполняется следующая операция, если замена произошла, иначе переходят к выполнению первой операции.
Алгоритм удобно представить в виде ориентированного графа, вершинами которого являются элементарные операторы и распознаватели.
Распознаватель проверяет условие – имеет ли место вхождение рi во входное слово p. Если ДА, то за ним следует оператор, который заменяет первое слева вхождение слова рi на слово qi. Если НЕТ, то управление передается на вход следующего распознавателя.
Дуги, исходящие из операторных вершин, подсоединяются либо к первой вершине – распознавателю, либо к выходной вершине. В первом случае подстановка называется обычной, во втором – заключительной.
Кроме того, имеются входная и выходная вершины. Входная вершина связана дугой с первым распознавателем.
На вход графа подается некоторое входное слово p.
Пример. Граф для трех подстановок (к = 3) (рис.1) имеет три распознавателя (РВ1,РВ2,РВ3) и три операторные вершины (ОП1,ОП2,ОП3).
Если подстановки заданы как ba ® ab, bc ® ba, bb ® ac, а входное слово
р = bcbaab, то работа алгоритма будет иметь следующий вид.
Пpимеp. Задан алфавит А={+, 1} и система подстановок:
‘1+1’ ® ‘11’ , ‘1’®`1`.
Обычная Заключительная
подстановка подстановка
Пусть дано входное слово р = ’11+11+1’. Оно перерабатывается алгоритмом в строку:
‘11+11+1’ ® ‘1111+1’ ® ‘11111’ ® `11111` !
Алгоритм реализует сложение единиц.
Тезис Маркова
Для любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм.
Все известные до сих пор алгоритмы нормализуемы.
Машина Тьюринга
Одно из уточнений понятий алгоритма было дано Э. Постом и А. Тьюрингом независимо друг от друга в 1936-1937гг. Основная мысль их заключалась в том, что алгоритмические процессы – это процессы, которые может свершить подходящим образом устроенная ”машина”. Ими были описаны гипотетические (условные) устройства, которые получили название «Машина Поста» и «Машина Тьюринга»(МТ). Так как в них много общего, то рассмотрим только машину Тьюринга.
Машина Тьюринга состоит из следующих частей:
1. Информационной ленты, представляющей бесконечную память машины. Это бесконечная лента, разделенная на ячейки. В каждой ячейке можно поместить лишь один символ из возможного их множества S={S1,S2,….,Sm},которое составляет внешний алфавит МТ. В этом алфавите один из символов (пусть это будет S1) соответствует пустому символу.
2. Считывающей головки – чувствительного специального элемента, способного обозревать содержимое ячеек. Лента может перемещаться вдоль головки так, что в каждый момент времени головка обозревает одну ячейку.
3. Управляющего устройства (УУ), которое в каждый момент времени находится в некотором состоянии. Число состояний конечно. Обозначим множество состояний как {q1,q2,…,qn}. Среди состояний одно соответствует заключительному, при котором МТ останавливается. УУ связано со считывающей головкой.
Кроме того, УУ вырабатывает три команды на перемещение ленты: П, Л, Н, где
П – переместиться на соседнюю справа ячейку;
Л – переместиться соседнюю слева ячейку;
Н – продолжать обозревать ту же ячейку.
Совокупность символов {q1,q2,…,qn} и {П,Л,Н} образуют внутренний алфавит МТ.
Работа машины происходит в дискретном времени. В начальный момент времени в ограниченный участок ленты записано слово в алфавите S, представляющее исходное условие задачи. В остальных ячейках предполагается записанным пустой символ. Управляющее устройство находится в начальном состоянии q1. На каждом шаге работы МТ обозревает на ленте символ Sk и в зависимости от него и от состояния qi, переходит в состояние qj, заменяет Sk на символ Sl и передвигает ленту (либо нет) на одну ячейку.
Каждая элементарная операция имеет вид
qiSk®qjSl П(Л,Н).
Множество элементарных операций упорядочено и образует абстрактную программу, которая представляет алгоритм.
Считывающая головка и управляющее устройство образуют логический блок, который представляет собой (2,3)-полюсник.