Глава 3. Алгоритмы. Алгоритмизация

3.1 Абстрактные автоматы и понятие алгоритма

Классические примеры абстрактных автоматов -— машина Тьюринга или алгоритмическая система Поста(Пост в отличие от Тьюринга не пользовался термином машина). Чтобы подчеркнуть единство подходов обоих авторов будем употреблять термин «машина». Машина Поста состоит из бесконечной ленты, разделенной на отдельные секции (ячейки), в которые можно либо заносить метку, либо считывать метку с помощью записывающей или считывающей головки (рис. 3.1). Лента (или головка) может передвигаться в левую или правую стороны на один шаг в зависимости от команды. Лента всегда останавливается так, чтобы напротив головки находилась секция (ячейка). Команды абстрактного автомата обычно включают в себя одно из следующих действий (на примере машины Поста); движение головки вправо, движение головки влево, запись метки, стирание метки, передача управления, остановка (стоп).

Каждая команда имеет свой номер i. Стрелка указывает направление движения. Второе число j, стоящее в конце команды, называется отсылкой.

Рис. 3.1.

У команды передачи управления могут быть две отсылки. Поэтому программа абстрактного автомата должна обладать двумя свой­ствами:

• на первом месте в списке всегда стоит команда с номером 1, на вто­ром месте — с номером 2 и т. д.;
• отсылка любой из команд всегда находится в списке команд про­граммы.

После передвижения ленты влево или вправо головка считывает со­стояние секции (пустая или записана метка). Информация о том, какие сек­ции пусты, а какие отмечены, образует состояние ленты или состояние автомата. Таким образом, обладая указанным выше набором команд, ав­томат может осуществлять определенные действия, которые будут зада­ваться программой. Программой абстрактного автомата будем называть ко­нечный непустой список команд.

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

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

автомат дошел до выполнения невыполнимой команды (запись метки в занятую ячейку, стирание метки в пустой ячейке); выполнение программы прекращается, автомат останавливается (назовем это состояние поломкой автомата), происходит безрезультатная остановка;

автомат дошел до команды стоп, программа считается выполненной, происходит результатная остановка;

автомат не доходит ни до результатной, ни до безрезультатной оста­новки, происходит бесконечная работа (автомат «завис»).

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

Назовем последовательность секций (ячеек), содержащих метку, массивом, а число секций в нем — длиной массива. Условимся число n представлять на ленте массивом длины n + 1. Тогда этот массив будем называть автоматным изображением числа. Например, числа 6, 3 и 2 представлены соответственно на рис. 3.2. автоматными изображениями.

Рис. 3.2.автоматные изображения чисел

Представим себе, что на машине Поста надо прибавить 1 к любому числу.

Для этого требуется написать программу для машины Поста, обладающую следующим свойством: для любого числа n, записанного на ленте, программа должна дать результатную остановку с записью числа n+1 в произвольном месте ленты.

Программа должна выглядеть следующим образом:

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

Можно составить программы для сложения, умножения, деле­ния чисел. Есть ли ограничения на вычисления, производимые на машине Поста? Ответ на этот вопрос был сформулирован самим Э. Постом в сле­дующем виде: «Задача па составление программы, приводящей от исход­ного данного к результирующему числу, тогда и только тогда имеет ре­шение, когда имеется какой-нибудь общий способ, позволяющий по произвольному и одному данному выписать результирующее число».

Формулировка постулата Поста подводит к понятию алгоритма.

Английский математик А. М. Тьюринг в работе «О вычислимых числах с приложением

к проблеме разрешения» и американский математик Э, X, Пост в работе «Финитные комбинаторные процессы» почти одновременно в 1936 г. дали уточнения понятия «алгоритм» на примере гипотетической машины с бесконечной лентой. Машина Тьюринга отличается от

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

Исторически термин «алгоритм» произошёл от фамилии узбекского математика IX века Мухаммада ибн Муса ал – Хорезми, который впервые сформулировал правила четырёх арифметических действий. Поначалу именно эти правила назывались алгоритмами, но затем термин получил дальнейшее развитие в первую очередь в математике.

Су­ществует много определений термина «алгоритм». Например, по определе­нию акад. Л, Н. Колмогорова, алгоритм или алгорифм — это всякая система вычислений, выполняемых по строго определенным правилам, кото­рая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

В инженерной практике часто используется следующее определение: алгоритм — конечная совокупность точно сформулированных правил ре­шения какой-то задачи.

3.2 Формы записи алгоритмов.

Словесная форма записи алгоритма.

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задаётся в произвольном изложении на естественном языке.

Например, алгоритм нахождения наибольшего общего делителя(алгоритм Евклида) двух натуральных чисел можно записать следующим образом:

1) задать два числа;

2) если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;

3) определить большее из чисел;

4) заменить большее из чисел разностью большего и меньшего из чисел;

5) повторить алгоритм с шага 2.

По указаниям этого алгоритма можно найти наибольший общий дели­тель для любой пары целых чисел.

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