Алгоритмы. Машина Тьюринга

В первой половине IX века узбекский математик Абу-Джафар Мухаммед ибн Муса (787 - 850 г.) аль-Хорезми (из Хорезма) опубликовал свой трактат «Китаб аль-джебр вальмукабала», в котором были разработаны правила выполнения четырёх действий арифметики. Трактат был переведен на латинский язык в XII в. и оказал значительное влияние на развитие математики в Европе. Название трактата (аль-джебр) и место, где проживал его автор (аль-Хорезми), послужили источниками названий таких понятий как алгебра и алгоритм. Хотя алгоритмические процедуры были известны ещё со времён Евклида, наиболее точная формулировка понятия алгоритм, связанная с понятием машины Тьюринга, появилась только в ХХ веке.

Наиболее известный пример алгоритма даёт нам правило отыскания наибольшего общего делителя (НОД)[3] двух натуральных чисел, предложенное Евклидом в 3 в. до Р.Х.

Для любых натуральных чисел N и K определена операция деления с остатком: N = p*K + q; p – частное, q – остаток (0 £ q < K). Если q = 0, то говорят, что N делится на K нацело. Для вычисления остатка от деления целых чисел в математике (и программировании) применяется обозначение N mod K (читается «N по модулю K»).

Пример. 17 делим на 3: 17 = 5*3+2. Здесь частное равно 5, остаток равен 2, то есть 17 mod 3 = 2.

Итак, пусть заданы два натуральных числа N и K. Требуется найти их НОД.

Алгоритм Евклида решения задачи.

1) Вычислим R = N mod K;

2) присвоим N:=K,

3) присвоим K: = R;

4) если K ¹ 0, то вернуться к выполнению 1 шага.

5) нашли НОД = N.

6) Закончить алгоритм (Stop).

Продемонстрируем работу алгоритма на примере чисел N=112 и K=24.

1) R = 112 mod 24 à R = 16;

2) N = 24;

3) K = 16;

4) K¹ 0; опять вычисляем R = N mod K;

5) R = 24 mod 16 à R = 8;

6) N=16;

7) K = 8;

8) K¹ 0 à опять вычисляем R = N mod K;

9) R = 16 mod 8 à R = 0;

10) N = 8;

11) K = 0;

12) т.к. K = 0 à найден НОД: N = 8;

13) Stop.

Приведём интуитивное (неформальное) определение алгоритма из Математической энциклопедии, том 1.

Определение 1. Алгоритм - точное предписание, которое задаёт вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма данных) и направленный на получение полностью определяемого этим исходным данным результата.

Здесь алгоритмический процесс - процесс последовательного преобразования так называемых конструктивных объектов (слов, чисел, пар слов …), происходящий дискретными шагами.

Определение 2. Алгоритм — это точное предписание, определяющее порядок действий исполнителя, направленное на решение поставленной задачи.

Определение 3 (определение А.И. Мальцева). Алгоритм - процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задаётся исходная система величин, а в каждый следующий момент система величин получается по определённому закону из системы величин, полученных в предыдущие моменты времени.

Приведённые определения алгоритма можно представить в виде схемы:

Исходные данные à Алгоритм à Результат.

Во всех определениях алгоритма неявно предполагается, что есть некто (или нечто), кто будет выполнять заданное предписание или процесс преобразование данных - исполнитель алгоритма. Исполнитель должен понимать команды алгоритма и уметь их выполнять. Исполнителем может являться человек, ЭВМ, техническое устройство и т.д.

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

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

Основные свойства алгоритма:

1) Дискретность шагов алгоритма: каждый шаг отделён от другого ненулевым отрезком времени.

2) Элементарность шагов: на каждом шаге алгоритма надо выполнить простые, понятные для исполнителя действия, причём за конечный промежуток времени.

3) Определённость: каждый шаг заканчивается определённым результатом, зависящим от исходных данных для этого шага; последовательность шагов алгоритма строго определена.

4) Конечность: для получения результата надо выполнить, быть может, большое, но конечное число шагов.

5) Массовость: входные данные алгоритма принадлежат некоторому множеству значений.

Для записи алгоритмов существуют различные способы. Одни из них ориентированы на исполнителя-человека, другие – на исполнение техническими устройствами, в частности компьютерами, роботами и т.д. То есть алгоритм задается в той форме, которая наиболее понятна исполнителю. Существуют следующие способы представления алгоритмов:

· словесный (описательный);

· формульный;

· графический;

· табличный или схематичный, в виде графа;

· в виде блок-схемы;

· в виде программы.

В обыденной жизни наиболее распространенным способом задания алгоритма являются описательный (словесный и словесно-пошаго­вый) способ. Когда объясняют, как добраться до нужного места, или описывают внешность незнакомого человека, с которым необходимо встретить­ся, то строится словесное описание алгоритмов поиска и «опозна­ния». Хорошим примером такого задания алгоритма является кулинарный рецепт приготовления какого-либо блюда. Если в словесном описании четко выделены и пронумеро­ваны элементарные шаги, то такое описание называется словесно-пошаговым. Например, алгоритм быстрого получения большого количества денег, который лиса Алиса и кот Базилио предложили Буратино: «В Стране Дураков есть волшебное поле, - называется Поле Чудес... На этом поле выкопай ямку, скажи три раза: "Крекс, фекс, пекс", положи в ямку золотой, засыпь землей, сверху посыпь солью, полей хорошенько и иди спать. Наутро из ямки вырастет небольшое деревце, на нем вместо листьев будут висеть золотые монеты. Понятно?». Этот алгоритм состоит из семи шагов, исходные данные – Поле Чудес и золотая монета.

Некоторые из способов записи алгоритмов предназначены только для исполнителей, обладающих определенными знаниями и умениями, исполнителей-специалистов. Например, для определения площади ка­кой-либо сложной фигуры математик воспользуется алгоритмом вычис­ления определенного интеграла — это формульный способ записи алгоритма. Химик сможет получить нужное ему вещество, если извест­на формула соответствующей реакции. По этой же формуле он определит, какие исходные вещества и в каком количестве ему необходимы – это будут исходные данные алгоритма.

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

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

Программы строятся по строгим формальным правилам, в блок-схемах же допустимы обозначения, введенные самим пользователем. В этом состоит одно из отличий программы от блок-схемы. Блок-схема создаётся в предположении, что она будет восприниматься человеком, программа предназначена для «восприятия» её ЭВМ. Блок-схема не является обязательным этапом при переходе от алгоритма к программе. Однако, наличие блок-схемы, как правило, облегчает написание программы. Известны три типа алгоритмов – линейный, ветвящийся и циклический. Тип алгоритма определяется характером решаемой в соответствии с его командами задачи.

Линейный тип алгоритма - алгоритм, в котором команды выполняются в порядке их естественного следования друг за другом, переход от одной команды к другой происходит только после выполнения предыдущей команды и независимо от каких–либо условий.

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