Определение алгоритма на основе абстрактных автоматов (машины Тьюринга)
Алгоритмические процессы – это процессы, которые может совершать подходяще устроенная «машина».
Под «машиной» в данном случае подразумевается некоторый абстрактный, существующий лишь в воображении автомат.
В общем случае такая машина состоит из следующих частей:
информационная лента, состоящая из ячеек, представляющая неограниченную память машины, так как лента неограниченна в обе стороны. В каждой ячейке можно хранить только один символ, в том числе и ноль;
головка чтения/записи, вдоль которой может перемещаться лента (или которая может перемещаться относительно информационной ленты);
устройство управления, которое в каждый рассматриваемый момент находится в некотором «состоянии». Устройство управления может находиться в некотором конечном числе состояний, если это состояние заключительное, машина заканчивает работу.
Такая машина может сдвигать ленту на одну ячейку влево или вправо, оставляя содержимое ячеек неизменным, или может изменять состояние воспринимаемой ячейки, оставляя ленту неподвижной. Машина Тьюринга работает в произвольном конечном алфавите и выполняет некоторое конечное число приказов.
Машины Тьюринга представляют собой универсальных исполнителей, с использованием которых можно имитировать все алгоритмические процессы, описываемые математиками. Было доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций. Т.о. вопрос о существовании или не существовании алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или не существовании машины Тьюринга, обладающей нужным свойством.
Интуитивное понимание машины Тьюринга: имеется бесконечная лента, разделённая на клетки. По клеткам ездит каретка. Прочитав букву, записанную в клетке, каретка движется вправо, влево или остаётся на месте, при этом буква заменяется новой. Некоторые буквы останавливают каретку и завершают работу.
На базе теорий рекурсивных функций и абстрактных автоматов появилось целое математическое направление – теория алгоритмов, в которой в основу определения алгоритма было поставлено особое соответствие между словами в том или ином абстрактном алфавите (А. Марков, Л. Калужнин). Теория алгоритмов оказалась тесно связанной не только с теоретической математикой (математической логикой, алгеброй, геометрией, анализом), но и с рядом областей лингвистики, экономики, физиологии мозга, философии, естествознания. Примером задачи этой области может служить описание алгоритмов, реализуемых человеком в процессе умственной деятельности.
А.А. Марков – Алгоритм – это предписание, ведущее от исходных данных к искомому результату и обладающее свойствами:
определенности (общепонятности и точности, не оставляющей места для произвола),
массовости (возможности применения ко всем процессам данного класса),
результативности (возможности получения правильного результата за конечное число шагов).
Исполнитель алгоритма - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя хаpактеpизуют:
среда;
элементарные действия;
система команд;
отказы.
Среда (или обстановка) - это "место обитания" исполнителя.
Напpимеp, для исполнителя Робота среда - это бесконечное клеточное поле. Стены и закрашенные клетки тоже часть среды.
Система команд. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды.
Напpимеp, команда Робота "вверх" может быть выполнена, если выше Робота нет стены. Ее результат - смещение Робота на одну клетку вверх. После вызова команды исполнитель совершает соответствующее элементарное действие.
Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.
Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов "почему" и "зачем".
С появлением ЭВМ возникла область теории алгоритмов, тесно связанная с информатикой, которая стала теоретической основой таких ее составных частей, как теория программирования, построение алгоритмических языков и ЭВМ, разработка трансляторов, анализа алгоритмов с целью выбора наиболее рационального для решения на ЭВМ и т.д.
Для решения поставленной задачи необходимо описать способ (метод) решения задачи в соответствии с определенными правилами, а именно:
задать исходные данные;
в требуемой последовательности разбить процесс решения задачи на этапы;
указать признак окончания решения задачи;
определить результат решения задачи.
Такая четко сформулированная последовательность правил, описывающая способ (метод), и является алгоритмом.
Алгоритм - точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому результату.
Алгоритм должен обладать следующими свойствами:
а) определенность - каждая команда алгоритма должна быть понятна исполнителям, чтобы они её однозначно понимали и выполняли совершенно одинаково;
б) результативность - данный алгоритм приводит к получению искомого результата за конечное число шагов;
в) массовость - пригодность для решения различных вариантов данной задачи;
г) дискретность - разбиение процесса обработки информации на ряд более простых этапов.
Исполнителем может быть не только человек, но и автомат. Компьютер – лишь частный, но наиболее впечатляющий пример исполнителя, чьё поведение основано на реализации алгоритма. Более того, создание персонального компьютера оказало воздействие на развитие теории алгоритмов, одной из областей дискретной математики.
Эффективный метод построения алгоритма – метод пошаговой детализации (последовательного построения). При этом сложная задача разбивается на ряд более простых.
Способы описания алгоритмов:
словесное описание (словесно-формульное),
графическое (блок-схема),
псевдокод (структурно-стилизованный)
программа.
Способы записи алгоритмов отличаются друг от друга наглядностью, компактностью, степенью формализации.
Словесное описание(записи на естественном языке);
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Алгоритм может быть следующим:
задать два числа; если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; определить большее из чисел; заменить большее из чисел разностью большего и меньшего из чисел; повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.
Словесный способ не имеет широкого распространения по следующим причинам:
такие описания строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний.
Словесный способ не имеет широкого распространения по следующим причинам:
такие описания строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний.
Начало
1 …..
2….. шаги
3…..
.
. алгоритма
.
Конец
Начало и конец определяют физическое начало и конец алгоритма соответственно. Все шаги алгоритма нумеруются. Номера шагов определяют порядок их выполнения. Для этой формы записи алгоритма выполняется естественный порядок выполнения действий (шагов алгоритма): слева направо и сверху вниз. Этот порядок соответствует процедуре чтения текста: слева направо в строке и по строкам сверху вниз.
3. Графический способ, когда весь вычислительный процесс разбивается на отдельные блоки, для изображения которых используют геометрические фигуры. Комбинации таких фигур дают наиболее полное визуальное представление о рассматриваемой задаче. Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.
Существуют два способа графического представления алгоритмов. Первый, с использованием структурограмм Нэсси-Шнейдермана, широко используется в западной литературе по программированию. Второй – с помощью блок-схем, геометрические фигуры которых имеют начертания в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения», используется преимущественно в нашей литературе.
Структурограммы Нэсси-Шнейдермана
Блоки структурограмм Нэсси-Шнейдермана представлены в табл.1.
Таблица 1
Графические обозначения символов и их функций
-
Название
символа
Обозначение
Функция
Процесс
Выполнение операции
или группы операций
Решение
Проверка условия
Цикл
Повторяют процесс пока
повторяется некоторое условие в начале цикла
Цикл
Повторяют процесс пока
повторяется некоторое условие в начале цикла
Схемы алгоритмов, представленные структурограммами, в связи с тем, что приведенные в таблице 1 блоки являются прямоугольниками представляют собой модуль из соединенных блоков смыкающихся друг с другом. Стандартным правилом изображения передачи управления в блоках модуля считается - сверху вниз, а внутри циклического блока – снизу вверх. (привести пример)
Графический способ записи в виде блок-схемы предполагает использование определенных графических символов – блоков, каждый из которых обозначает определенный тип действия. Совокупность блоков образует схему алгоритма или блок-схему.
Обозначение некоторых блоков в соответствии с ГОСТ 19.701-90 СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ ДАННЫХ И СИСТЕМ
Наименование символа |
Обозначение символа |
Пояснение |
Прерывание |
|
Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных). |
Процесс |
|
Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящие к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться). |
Предопределенный процесс |
|
Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле). |
Решение |
|
Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути. |
Данные
|
|
Символ отображает данные, носитель данных не определен.
|
Ручной ввод |
|
Символ отображает данные, вводимые вручную во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, световое перо, поломки с штриховым кодом).
|
Дисплей |
|
Символ отображает данные, представленные в человекочитаемой форме на носителе в виде отображающего устройства (экран для визуального наблюдения).
|
Модификация |
|
Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию (установка переключателя, модификация индексного регистра или инициализации программы). |
Граница цикла |
|
Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или конце в зависимости от расположения операции, проверяющей условие. |
Комментарий |
|
Символ используют для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры. |
Соединитель |
|
Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение. |
Пропуск
|
|
Символ (три точки) используют в схемах для отображения пропуска символа или труппы символов, в которых не определены ни тип, ни число символов. Символ используют только в символах линии или между ними. Он применяется главным образом в схемах, изображающих общие решения с неизвестным числом повторений. |
Внутри блоков записываются выполняемые действия.
Блоки соединяются линиями потока информации, по которым проходит передача управления. Линии определяют последовательность обработки блоков. Стандартным правилом изображения линии передачи управления считается - сверху вниз и слева направо. Если необходимо передать управление справа налево или снизу вверх, то в этом случае линия должна заканчиваться стрелкой.
К
5
Минимальное количество текста, необходимого для понимания функции данного символа, следует помещать внутри данного символа. Текст для чтения должен записываться слева направо и сверху вниз независимо от направления потока.
Если объем текста, помещаемого внутри символа, превышает его размеры, следует использовать символ комментария.
Пример.
Если использование символов комментария может запутать или разрушить ход схемы, следует поместить текст комментария на отдельном листе и давать перекрестную ссылку на символ.