Основные вычислительные алгоритмы.

Попытки выработать формальное определение алгоритма привели в 20—30-х годах XX века к возникновению теории алгоритмов. В первой половине XX века разные математики (А.Тьюринг, Э.Пост, А.Н. Колмогоров, А.А. Марков и др.) предложили несколько подходов к формальному определению алгоритма: нормальный алгоритм Маркова, машина Тьюринга, машина Поста и т.д. В дальнейшем было показано, что все эти определения эквива­лентны.

Мы рассмотрим формальное определение алгоритма, введенное А.Тьюрингом. Математи­ком для уточнения понятия алгоритма были предложены абстрактные вычислительные конструкции, которые поз­же были названы "машинами". Машина Тьюринга названа по имени английского математика А/Тьюринга (1912— 1954), который описал ее в 1936 году. Аналогичную концепцию машины ввел позднее, в 1937 году, и независимо от Тьюринга американский математик Э.Пост.

У Алана Тьюринга целью создания такой абстрактной воображаемой машины было получение возможности дока­зательства существования или несуществование алгоритмов решения различных задач. Руководствуясь этой целью, Тью­ринг искал как можно более простую, "бедную" алгоритмическую схему, лишь бы она была универсальной.

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

Понятие машины Тьюринга. Что же представляет собой машина Тьюринга — машина, при помощи которой оказалось возможным доказать, что для некоторых задач не существует алгоритмического решения?

Машина Тьюринга — это строгое математическое пост­роение, математический аппарат (аналогичный, например, аппарату дифференциальных уравнений), созданный для решения определенных задач. Этот математический аппа­рат был назван "машиной" по той причине, что по описа­нию его составляющих частей и функционированию он похож на вычислительную машину. Принципиальное отли­чие машины Тьюринга от вычислительных машин состоит в том, что ее запоминающее устройство представляет собой бесконечную ленту; у реальных вычислительных машин за­поминающее устройство может быть как угодно большим, но обязательно конечным. Машину Тьюринга нельзя реа­лизовать именно из-за бесконечности ее ленты. В этом смысле она мощнее любой вычислитель­ной машины.

Прежде чем мы начнем зна­комиться с машиной Тьюрин­га, необходимо сделать два об­щих замечания относительно объектов, с которыми работа­ют алгоритмы.

Замечание. Одной из причин расплывчатости интуитивного понятия алгоритма является разнообразие объек­тов, с которыми работают алгоритмы. В вычислительных алгоритмах объектами являются числа. В алгоритме шахматной игры объектами являются фигуры и их позиции на шахматной доске. В алгоритме форматирования текста — слова некоторого языка и правила переноса слов. Однако во всех этих и других случаях можно считать, что алго­ритм имеет дело не с объектами реального мира, а с некоторыми изображениями этих объектов. Например, есть алго­ритм сложения двух целых чисел. Результатом сложения числовых объектов 26 и 22 будет числовой результат 48. Но мы можем считать, что объектом этого алгоритма является входная последовательность, состоящая из пяти символов: 2 6 + 22, а результатом является последовательность, состоящая из двух символов: 48

При этом мы исходим из того, что имеется набор из 11 различных символов {0, 1,2, 3, 4, 5, 6, 7, 8, 9, +}. Ис­пользуемые символы будем называть буквами, а их набор — алфавитом. В общем случае буквами могут служить любые символы, требуется только, чтобы они были различны между собой и чтобы их число было конечным.

Определение.Любая конечная последо­вательность букв из некоторого алфавита на­зывается словомв этом алфавите.

Определение.Количество букв в слове называется дли­нойслова. Слово, в котором нет букв, называется пустымсловом. Оно часто изображается символом "L" или а₀.

Итак, объекты реального мира можно изображать сло­вами в различных алфавитах. Это позволяет считать, что объектами работы алгоритмов могут быть только слова.

Определение.Слово, к которому применим алго­ритм, называется входнымсловом; слово, получаемое в результате работы алгоритма, называется выходным.Совокупность слов, к которым применим алгоритм, на­зывается областью применимости алгоритма.

К сожалению, нельзя доказать, что все возможные объекты можно описать словами, так так само понятие объекта не было формально (то есть строго) определено. Но можно проверить, что для любого наугад взятого ал­горитма, работающего не над словами, его объекты можно выразить так, что они становятся словами, а суть алго­ритма от этого не меняется.

Замечание 2. Любой алфавит можно заменить другим. Такая замена называется кодировкой. Например, каждой букве из первого алфавита ставится в соответствие код, представляющий собой слово во втором алфавите. В качест­ве второго алфавита достаточно иметь алфавит из двух букв, так как любое слово из любого алфавита можно закоди­ровать в двухбуквенном алфавите с гарантией однозначного восстановления закодированных слов. Следовательно, любой алгоритм можно свести к алгоритму над словами в алфавите {0, 1}, а перед применением алгоритма входное слово следует закодировать, после применения алгоритма выходное слово раскодировать.

Выводы

Можно считать, что алгоритмы работают со словами.

Мы формально описываем объекты-слова, над кото­рыми работают алгоритмы, в некотором алфавите.

Далее для уточнения понятия алгоритма следует фор­мально описать действия над объектами-словами и поря­док выполнения этих действий. В качестве такой фор­мальной схемы мы и рассмотрим машину Тьюринга.

В каждой машине Тьюринга есть две части:

неограниченная в обе стороны лента, разделенная на ячейки;

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

С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов А = {а₀, а₁,…,а_m} и алфавит состояний Q = {q_0, q₁,…, q_p} . (С разными машинами Тьюринга могут быть связаны разные алфавиты А и Q) Состояние q₀ называется пассивным. Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q₁ называется начальным. Находясь в этом состоянии, машина начинает свою работу.

Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от вход­ного слова находятся только пустые ячейки (в алфавит А всегда входит пустая буква а₀ — признак того, что ячей­ка пустая).

Автомат может двигаться вдоль ленты влево или вправо, читать содержимое ячеек и записывать в ячейки бу­квы. Ниже схематично нарисована машина Тьюринга, автомат которой обозревает первую ячейку с данными.

Автомат каждый раз "видит" только одну ячейку. В зависимости от того, какую букву а, он видит, а также в зависимости от своего состояния q_j, автомат может выполнять следующие действия:

записать новую букву в обозреваемую ячейку;

выполнить сдвиг по ленте на одну ячейку вправо/ влево или остаться неподвижным;

перейти в новое состояние.

То есть у машины Тьюринга есть три вида операций. Каждый раз для очередной пары (a_i, q_j) машина Тью­ринга может выполнить определенную команду в соответствии с программой.

Программа для машины Тьюринга представляет собой таблицу, в каждой клетке которой записана команда.

Клетка (a_i, q_j) определяется двумя параметрами — символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: "Л" (влево), "П" (вправо) или "Н" (неподвижен).

После выполнения автоматом очередной команды он переходит в состояние q_m (которое может в частном случае совпадать с прежним состоянием q_j ). Следующую команду нужно искать в m-й строке таблицы на пере­сечении со столбцом a_l (букву а_l автомат видит после сдвига),

Если следить только за лентой, не обращая внимания на автомат, то мы увидим, что в результате выполнения каждой команды изменяются слова: какие-то буквы стираются и вместо них остаются пустые ячейки, в каких-то пустых ячейках появляются новые буквы.

Договоримся, что когда лента содержит входное слово, то автомат находится против какой-то ячейки в со­стоянии q_j. В процессе работы автомат будет перескакивать из одной клетки программы (таблицы) в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q₀. Эта клетка называется клеткой останова. Дойдя до такой клетки, машина Тьюринга останавливается.

Если клеток останова в программе нет, то считается, что машина Тьюринга неприменима к данному входно­му слову. Если клетки останова в программе есть, но машина на них не попадает, также считается, что машина Тьюринга неприменима к данному входному слову. Машина Тьюринга применима к входному слову только в том случае, если, начав работу над этим входным словом, она рано или поздно дойдет до клетки останова.

Прослеживая работу машины Тьюринга, мы можем узнать, что она применима к данному слову. Но если она неприменима к данному слову, то такое прослеживание ничего не даст, так как в любой момент времени мы мо­жем надеяться дойти до клетки останова.

Таким образом, неприменимость не может быть выяснена прямым способом; в ней можно убедиться только путем косвенных рассуждений. Например, если в программе нет клетки останова, то данная машина Тьюринга неприменима ни к одному слову. Или, например, в программе некой машины Тьюринга с алфавитом {0, 1} есть клетка останова, но первая строка программы (таблицы) имеет следующий вид:

Тогда, что бы автомат ни увидел на ленте, он ничего не меняет и сдвигается на шаг вправо, оставаясь всегда в состоянии q₁. А поскольку лента бесконечна, он никогда не остановится.