Что такое алгоритм?! часть первая

Универсальные исполнители

Как мы уже видели, понятие алгоритма оказывается «привязанным» к его исполнителю и некоторому языку программирования. Это не позволяет определить алгоритм как математический объект. Поэтому возникла идея попытаться построить универсальный исполнитель.

Универсальный исполнитель — это исполнитель, который может моделировать работу любого другого исполнителя.

Это значит, что для любого алгоритма, написанного для любого исполнителя, существует эквивалентный алгоритм для универсального исполнителя.

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

В середине XX века разными учёными независимо друг от друга были предложены несколько исполнителей, претендующих на роль универсальных (они будут рассмотрены далее), причём в теории алгоритмов доказано, что все они эквивалентны друг другу. Это означает, что для любого алгоритма для одного универсального исполнителя можно построить эквивалентный алгоритм для другого универсального исполнителя.

Как же связан универсальный исполнитель с проблемой строгого определения алгоритма?

Любой алгоритм может быть представлен как программа для универсального исполнителя.

Это основная идея теории алгоритмов. Строго доказать это утверждение невозможно, потому что здесь используется интуитивное понятие «алгоритм».

Как мы увидим, каждый универсальный исполнитель описывается с помощью математических терминов, поэтому на его основе можно дать строгое определение алгоритма:

Алгоритм — это программа для универсального исполнителя.

Универсальный исполнитель — это некоторая модель вычислений, которая задаёт способ описания алгоритмов и их выполнения.

Модель вычислений должна содержать:• «процессор», задающий систему команд и способ их выполнения;
• «память», определяющую способ хранения данных;
• язык программирования (способ записи программ);
• способ ввода данных (чтения входного слова);
• способ вывода слова-результата.

Все универсальные исполнители эквивалентны, поэтому последнее приведённое определение алгоритма не зависит от конкретного исполнителя.

Следующая страница Машина Тьюринга

Cкачать материалы урока

Задача

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

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

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

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

Сразу возникает масса вопросов к этому определению:

  • Что такое правило?
  • Как, кому и для кого это правило можно задать?
  • Что есть объединение совокупностью?
  • Каким образом правила соотносятся с задачей?
  • Что формирует класс задачи?
  • Определяется ли способ формирования совокупности правилами и задачами?

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

  • Какова структура набора?
  • Какие есть варианты действий и исполнителей?
  • Существуют ли минимально возможное действие, минимальный набор необходимых действий?
  • Каким образом действия встроены в исполнителя?
  • Какие есть способы создания копии исполнителя (например, если исполнитель — человек)?
  • Как действия зависят друг от друга в упорядоченном выполнении?
  • Что есть задача кроме того, что она выполняется последовательностью действий?
  • Как задача соотносится с исполнителем и с действиями?
  • Возможно ли использовать решение задачи в качестве действия?
  • Какие возможны варианты указания порядка действий?
  • Если воспроизведение патефоном записи звуков леса является алгоритмом, то какова структура этой задачи?
  • Если репликация ДНК является алгоритмом, то каков её исполнитель?
  • Если исполнителем является Машина Тьюринга, то как с её использованием решить механическую задачу, например, воспроизведение звука?

Перечислено много вопросов, но они мало помогают в поиске методов работы с алгоритмом. Поэтому поставим себе меньшую задачу, но тоже очень нам важную. Давайте попробуем сформулировать, что делает алгоритм способом решения наших задач, и какие процессы являются для него «действиями». Даже решение этой «маленькой» задачи оказывается очень объемным для одной статьи, поэтому будем его разбивать на части. И поэтому первую статью серии целиком посвятим только «Действию» и его признакам, которые опущены в указанных выше определениях алгоритма, но являются очень важными для ответов на все заданные вопросы.

Что такое базовые алгоритмические структуры?

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

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

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

1. Базовая структура  «следование».Образуется последовательностью действий, следующих одно за другим.

2. Базовая структура  «ветвление». Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного
из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Структура ветвление существует в четырех основных вариантах:

  • если—то;
  • если—то—иначе;
  • выбор;
  • выбор—иначе. 

Чем отличается программный способ записи алгоритмов от других?

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

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

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке —
программой для компьютера.

Что такое словесный способ записи алгоритмов?

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

Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).

Алгоритм может быть следующим:

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

Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедитесь в этом самостоятельно, определив с помощью этого алгоритма наибольший
общий делитель чисел 125 и 75.

Словесный способ не имеет широкого распространения, так как такие описания:

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

Что такое алгоритм?

Понятие алгоритма такое же основополагающее для информатики, как и понятие информации

Именно поэтому важно в нем разобраться.. Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в
783—850 гг

В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком», знакомые теперь каждому школьнику. В
XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в
783—850 гг. В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком», знакомые теперь каждому школьнику. В
XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

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

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

Алгоpитм — заранее заданное понятное и точное пpедписание возможному исполнителю
совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов.

Это — не определение в математическом смысле слова, а, скорее, описание интуитивного понятия алгоритма, раскрывающее его сущность.

Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся
одним из важнейших факторов цивилизации .

Проблема

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

В результате программированию учишься по наитию. Лишь немного в этом труде помогают сборники алгоритмов, прикладных техник и шаблонов проектирования. Общая совокупность предлагаемых ими рецептов выстраивается длинным списком, и его длина грозит каждому из прочитанных приемов быть позабытым (как была забыта 53-яя личная группа в «телеге» до введения разбиения по каталогам). Но даже тот прием, который остался в памяти, чаще всего просто является описанием прикладной задачи, в которой было успешно его использование.

Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?

В личном опыте существования в профессии не раз отмечено, что каждый Junior борется с одинаковыми ветряными мельницами и постигает методы создания программ основываясь только на своих ошибках. Но ведь такие ошибки совершили уже очень многие. Почему до сих пор не создана система правил программирования, которая поможет обойти новоиспеченному кораблю-программисту подводные прибрежные камни? Ну, например, объяснение вреда использования метода «Copy-Paste» для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.

Для компактного и полезного набора объяснений нужно:

  • систематизировать методы работы с кодом;
  • разобрать по группам приёмы работы с алгоритмами, которые являются главной целью написания любого кода;
  • выделить простые признаки применения шаблонов проектирования;
  • разработать универсальные правила и наборы эффективных способов построения сложных алгоритмов.

Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.

Задуманная серия статей не претендует на полное решение указанной проблемы. Предпринимается небесспорная попытка сделать первый шаг на пути к этому решению. Этот шаг состоит в выделении структуры и свойств главного кирпичика программиста — Алгоритма.

Какими свойствами обладают алгоритмы?

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

1.   Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных
данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

2.   Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс pешения задачи как последовательное выполнение простых (или pанее
опpеделенных) шагов (этапов).

3.   Определенность — каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение
алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

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

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

Понятие алгоритма. Свойства алгоритма. Исполнители алгоритмов (назначение, среда, режим работы, система команд). Компьютер как формальный исполнитель алгоритмов (программ).

Появление алгоритмов связывают с
зарождением математики. Более 1000 лет назад (в
825 году) ученый из города Хорезма Абдулла (или
Абу Джафар) Мухаммед бен Муса аль-Хорезми
создал книгу по математике, в которой
описал способы выполнения арифметических
действий над многозначными числами. Само
слово алгоритм возникло в Европе после
перевода на латынь книги этого математика.

Алгоритм – описание
последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Вы постоянно сталкиваетесь с этим
понятием в различных сферах деятельности
человека (кулинарные книги, инструкции по
использованию различных приборов, правила
решения математических задач…). Обычно мы
выполняем привычные действия не
задумываясь, механически. Например, вы
хорошо знаете, как открывать ключом дверь.
Однако, чтобы научить этому малыша,
придется четко разъяснить и сами эти действия
и порядок их выполнения:
1. Достать ключ из кармана.
2. Вставить ключ в замочную скважину.
3. Повернуть ключ два раза против часовой
стрелки.
4. Вынуть ключ.

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

Свойства алгоритмов:
1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
2. Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);
3. Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).

Виды алгоритмов:
1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание);
3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий) 
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).

Для более наглядного представления
алгоритма широко используется графическая
форма — блок-схема
, которая составляется из
стандартных графических объектов.

Вид стандартного графического
объекта

Назначение

Начало алгоритма
Конец алгоритма
Выполняемое действие
записывается внутри прямоугольника
Условие выполнения действий
записывается внутри ромба
Счетчик кол-во повторов
Последовательность выполнения
действий.

Стадии создания алгоритма:
1. Алгоритм должен быть представлен в форме,
понятной человеку, который его
разрабатывает.
2. Алгоритм должен быть представлен в форме,
понятной тому объекту (в том числе и
человеку), который будет выполнять
описанные в алгоритме действия.

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

Исполнитель — объект, который выполняет
алгоритм.

Идеальными исполнителями являются машины,
роботы, компьютеры…

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

Исполнитель, как и любой объект, находится
в определенной среде и может выполнять
только допустимые в нем действия. Если
исполнитель встретит в алгоритме неизвестную
ему команду, то выполнение алгоритма
прекратится.

Компьютер – автоматический исполнитель алгоритмов.

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

Программирование — процесс составления
программы для компьютера. Для первых ЭВМ
программы записывались в виде последовательности
элементарных операций. Это была очень
трудоемкая и неэффективная работа. Поэтому
в последствии были разработанные
специальные языки программирования. В
настоящее время существует множество искусственных
языков для составления программ. Однако,
так и не удалось создать идеальный язык,
который бы устроил бы всех.

Что такое графический способ записи алгоритмов?

Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

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

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

Что такое «Исполнитель алгоритма»?

Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая,
биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя хаpактеpизуют:

  • сpеда;
  • элементаpные действия;
  • cистема команд;
  • отказы.

Сpеда (или обстановка) — это «место обитания» исполнителя. Напpимеp, для исполнителя Pобота из школьного учебника [] сpеда — это бесконечное клеточное поле. Стены и закpашенные клетки тоже часть сpеды. А их pасположение и положение самого Pабота задают
конкpетное состояние среды.

Система команд. Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя. Для каждой команды должны
быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды. Напpимеp, команда Pабота
«ввеpх» может быть выполнена, если выше Pабота нет стены. Ее pезультат — смещение Pабота на одну клетку ввеpх.

После вызова команды исполнитель совеpшает соответствующее элементаpное действие.

Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.

Обычно исполнитель ничего не знает о цели алгоpитма. Он выполняет все полученные команды, не задавая вопросов «почему» и «зачем».

В информатике универсальным исполнителем алгоритмов является компьютер.

Выводы

Соберём всё, что мы отметили рассматривая разные примеры «действия»:

  • «действие» можно использовать для создания алгоритма;
  • «действие» может быть элементарным;
  • «действие» может быть реализовано алгоритмом;
  • в «действии» обязательно участвует некоторый объект или группа объектов;
  • для группы объектов «действие» происходит только тогда, когда эти объекты «достаточно близко»;
  • в действии изменяются связи и параметры объектов (включая параметры их движения);
  • «действие» всегда и обязательно должно быть повторимо.

Признак Повторимости помогает нам в создании наших алгоритмов. С его использованием мы из всех процессов выделяем те, что являются «действием» и на их основе создаём новые алгоритмы. Более того этот признак достаточно прост и на основе его формализации можно снизить требования к системе обнаруживающей и создающей «действия» и поручить это нашему компьютеру.

Следующая статья серии (Часть 2) будет посвящена рассмотрению способов, с использованием которых «действия» могут быть сгруппированы в алгоритм. Этих способов достаточно много и есть предпосылки, что их описание не получится уместить в одну статью. Напишем — увидим.

Спасибо Вам за внимание