Какое свойство алгоритма называется массовостью
I. Дискретность
Одним из таких свойств является дискретность. Под дискретностью понимается то, что алгоритм состоит из описания последовательности шагов обработки, организованный таким образом, что в начальный момент задаётся исходная ситуация, а после каждого следующего шага ситуация преобразуется на основе данных, полученные в предшествующие шаги обработки. Дискретность алгоритма означает, что он исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
II. Определённость
Другое свойство принято называть определённостью. Оно означает, что на каждом шаге однозначно определено преобразование объектов среды исполнителя, полученных на предшествующих шагах алгоритма.
К примеру, в одном из кулинарных рецептов сказано:
Слегка потрясите, чтобы смесь стала комковатой. Подогрейте коньяк в маленькой кастрюльке и влейте её в смесь.
Формальному исполнителю здесь неясно, требуется ли трясти смесь, пока она вся не станет комом, и какой всё-таки величины кастрюля. Большая или маленькая? И до какой температуры надо подогреть коньяк. Так что такой алгоритм любому исполнителю выполнить довольно трудно, практически невозможно. Можно сказать, что в алгоритме не должны присутствовать не определённые слова: немного, чуть-чуть, слегка и т. д.
III. Результативность
Третье свойство — результативность алгоритма. Это свойство подразумевает, что каждый шаг (и алгоритм в целом) после своего завершения даёт среду, в которой все имеющиеся объекты однозначно определены. Если это по каким — либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует.
К примеру, в инструкции по применению лекарства от кашля сказано:
Если врач не прописал, то принимать 3-4 раза в день по 15-20 капель, лучше всего в горячей сладкой воде.
Здесь не определено, например, когда должен заканчиваться алгоритм — когда кашель пройдет или когда лекарство закончиться. Свойство результативности обычно подразумевает конечность алгоритма, т. е. завершение его работы за конечное число шагов (при этом количество шагов может быть заранее не известным и различным для разных исходных данных) .
IV. Понятность
Надо сказать, что алгоритм должен быть понятен не только автору, но и исполнителю. Если мы предложим исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т. к. такой программы в нём не заложено. Или, например, если мы предложим какому-нибудь мальчику испечь торт то у него, как правило, ни чего не получится, потому что этого они делать не умеют. Но если мы составим подробный алгоритм работы, разобьем его на элементарные шаги, такие, что он без труда поймёт и сможет выполнить каждый шаг, то он сможет успешно испечь любой торт. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Это свойство алгоритма называют понятностью.
V. Массовость
Наконец, еще одно свойство алгоритма — массовость. Оно означает, что имеется некоторое множество данных, которые могут обрабатываться алгоритмом, или данный алгоритм может быть применен для решения любой задачи одного типа. Массовость алгоритма тесно связанна с понятностью, в качестве примера можно разобрать пример с тортом, и сказать, что чем подробнее будет описан алгоритм приготовления, тем больше вероятности, что торт будет испечен. Также в качестве примера можно взять руководство по эксплуатации электрических приборов, инструкции и т. д. , чем полнее изложен алгоритм работы с приборами, тем легче нам с вами будет в нем разобраться. С точки зрения практической ценность алгоритмов важно, что бы множество допустимых исходных данных было достаточно большим, как правило, практическая ценность алгоритма не велика, если его можно использовать только один раз.
ПОНЯТИЕ АЛГОРИТМА.
СВОЙСТВА АЛГОРИТМА. ВИДЫ АЛГОРИТМОВ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ
Алгоритмом называется
точное и понятное предписаниe исполнителю совершить последовательность
действий, направленных на решение поставленной задачи. Слово «алгоритм»
происходит от имени математика Аль Хорезми, который сформулировал правила
выполнения арифметических действий. Первоначально под алгоритмом понимали
только правила выполнения четырех арифметических действий над числами.
В дальнейшем это понятие стали использовать вообще для обозначения последовательности
действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме
вычислительного процесса, необходимо понимать, что объектами, к которым
применялся алгоритм, являются данные. Алгоритм решения вычислительной
задачи представляет собой совокупность правил преобразования исходных
данных в результатные.
Основными свойствами
алгоритма являются:
- детерминированность
(определенность). Предполагает получение однозначного результата вычислительного
процecca при заданных исходных данных. Благодаря этому свойству процесс
выполнения алгоритма носит механический характер; - результативность.
Указывает на наличие таких исходных данных, для которых реализуемый
по заданному алгоритму вычислительный процесс должен через конечное
число шагов остановиться и выдать искомый результат; - массовость. Это
свойство предполагает, что алгоритм должен быть пригоден для решения
всех задач данного типа; - дискретность.
Означает расчлененность определяемого алгоритмом вычислительного процесса
на отдельные этапы, возможность выполнения которых исполнителем (компьютером)
не вызывает сомнений.
Алгоритм должен быть
формализован по некоторым правилам посредством конкретных изобразительных
средств. К ним относятся следующие способы записи алгоритмов: словесный,
формульно-словесный, графический, язык операторных схем, алгоритмический
язык.
Наибольшее распространение
благодаря своей наглядности получил графический (блок-схемный) способ
записи алгоритмов.
Блок-схемой
называется графическое изображение логической структуры алгоритма, в котором
каждый этап процесса обработки информации представляется в виде геометрических
символов (блоков), имеющих определенную конфигурацию в зависимости от
характера выполняемых операций. Перечень символов, их наименование, отображаемые
ими функции, форма и размеры определяются ГОСТами.
При всем многообразии
алгоритмов решения задач в них можно выделить три основных вида вычислительных
процессов:
- линейный;
- ветвящийся;
- циклический.
Линейным
называется такой вычислительный процесс, при котором все этапы решения
задачи выполняются в естественном порядке следования записи этих этапов.
Ветвящимся
называется такой вычислительный процесс, в котором выбор направления обработки
информации зависит от исходных или промежуточных данных (от результатов
проверки выполнения какого-либо логического условия).
Циклом называется
многократно повторяемый участок вычислений. Вычислительный процесс, содержащий
один или несколько циклов, называется циклическим.
По количеству выполнения циклы делятся на циклы с определенным (заранее
заданным) числом повторений и циклы с неопределенным числом повторений.
Количество повторений последних зависит от соблюдения некоторого условия,
задающего необходимость выполнения цикла. При этом условие может проверяться
в начале цикла — тогда речь идет о цикле с предусловием, или в конце —
тогда это цикл с постусловием.
Как упоминалось в предыдущей статье, основные свойства алгоритма — массовость, конечность и однозначность. Кроме этих свойств упоминают еще такие свойства алгоритмов, как их понятность и результативность. Рассмотрим подробнее — что же это за свойства.
Массовость алгоритма
Ценность алгоритма возрастает, если его можно применить к решению не одной, а целого класса задач. Такое свойство алгоритма называется его массовостью. Известные из арифметики правила сложения и умножения чисел «столбиком» — массовые алгоритмы, применяемые к любым слагаемым или сомножителям.
Кулинарные рецепты и инструкции по применению того или иного товара, как правило, не обладают массовостью — они составляются для каждого конкретного случая, и от этого никуда не уйти. Ведь каждый кулинарный рецепт обладает персональными пошаговыми инструкциями приготовления и набором ингредиентов.
Однако компьютерный алгоритм, разработанный для решения только одной частной задачи, чаще всего бесполезен, поскольку за время, потраченное на его создание, кодирование и ввод в компьютер, можно было решить задачу вручную.
Вполне закономерно, что разработчики алгоритмов стремятся расширить область их применения, сделать как бы более массовыми. Идеально было бы найти универсальный алгоритм на все случаи жизни, но такое, к счастью, невозможно, хотя бы потому, что есть алгоритмически неразрешимые классы задач. А к счастью — потому, что программисты благодаря этому факту без работы никогда не останутся.
С другой стороны, массовые алгоритмы, в силу своей общности, не учитывают конкретные особенности каждой решаемой ими задачи. Поэтому для особо важных задач приходится разрабатывать специальные «персональные» алгоритмы. Этим объясняется великое разнообразие алгоритмов компьютерных задач.
***
Конечность
Алгоритм должен решить задачу за конечное число шагов. Мы не можем вечно ждать результата. Если же алгоритм по каким-то причинам не может решить задачу, он должен сообщить об этом и завершить работу.
Несмотря на очевидность этого требования, иногда приходится прикладывать значительные усилия для того, чтобы предотвратить зацикливание алгоритма. При этом зачастую приходится уменьшать его массовость, ограничивая область применения.
Иногда время решения задачи составляет несколько часов или даже несколько суток. В таком случае в алгоритм обычно вводят инструкции, которые время от времени передают сообщения пользователю, сигнализирующие о нормальной, как говорят — штатной работе алгоритма. Даже программа, работающая непрерывно всего несколько минут, как правило, выводит на экран графические индикаторы своего выполнения — песочные часы, «градусник», различные вращающиеся или бегущие предметы, надписи и т. п., успокаивая таким образом пользователя — «все ok, я не зависла, я работаю!»
Конечность алгоритма обычно связывают с еще одним свойством – результативностью. Под результативностью алгоритма подразумевается, что по завершении каждого шага (или всего алгоритма в целом) должна быть получена среда (результат), в которой все объекты однозначно определены и можно приступать к выполнению следующего шага или следующего алгоритма, либо анализировать полученный результат. Если алгоритм не может получить такую полностью определяемую среду, он должен сообщить пользователю, что порученная задача не имеет однозначного решения.
***
Однозначность
Действия, выполняемые алгоритмом, должны следовать одно за другим, при этом очередное действие начинается после окончания предыдущего. После окончания каждого действия компьютер должен точно знать, что делать дальше, каково следующее предписание.
Компьютеру не скажешь: «Купи что-нибудь: колбасу или ветчину» и уж тем более — «Сыграй что-нибудь грустное или романтическое». Посылая компьютеризированного робота за покупками (почему бы нет?), надо дать ему точную, однозначную инструкцию: «Если колбаса свежее ветчины, купи колбасу, в противном случае купи ветчину». И даже такая, казалось бы, подробная команда может оказаться недостаточной, если вдруг колбасы в магазине не окажется, либо окажется несколько сортов колбасы или ветчины. Ваш робот растеряется и надолго задумается (если замешательство робота можно считать мыслительным процессом) над неподдающейся его скудному «разуму» задачей.
Требование однозначности (иногда это свойство называют дискретностью) обычно учитывается уже при разработке алгоритмического языка. Сами конструкции языка исключают неоднозначное их толкование и выполнение. На стадии обдумывания программы следует помнить об однозначности применяемого алгоритма.
Часто в программах встречаются несколько вариантов продолжения работы алгоритма. В таком случае нужно тщательно продумать условия выбора одного и только одного варианта.
***
Понятность
Это свойство алгоритма означает, что он должен быть понятен конкретному исполнителю – вычислительной машине, роботу или человеку. Приведем простой пример – если необходимо объяснить рецепт какого-либо блюда профессиональному повару, то для того, чтобы он понял технологическую последовательность приготовления достаточно несколько довольно-таки общих фраз о шагах и ингредиентах. Школьнику, для того, чтобы он смог приготовить это блюдо, следует тщательно описывать порядок приготовления со всеми мельчайшими подробностями, иначе он просто испортит продукты. При этом даже самое подробное описание рецептуры не гарантирует, что блюдо, приготовленное новичком от кулинарии, получится таким же вкусным, как у профи, поскольку поварское искусство имеет столько нюансов, нарабатываемых годами стажа работы, что их сложно предусмотреть и учесть в виде алгоритмической последовательности действий по приготовлению блюда.
То же самое в отношении ЭВМ – необходимо быть уверенным, что программная начинка компьютера и его «железо» смогут выполнить последовательность действий, предусмотренных алгоритмом.
Каждый шаг алгоритма обязательно должен представлять собой какое-либо допустимое и выполнимое действие конкретного исполнителя. Это свойство алгоритма и называют понятностью.
***
Теперь, после рассмотрения основных свойств алгоритма, можно сформулировать его определение. По отмеченным выше причинам оно не отличается строгостью, но вполне пригодно для использования в среде специалистов по практическому программированию.
Алгоритм – это точное пошаговое описание в системе команд исполнителя последовательности действий, однозначно приводящей к результату за конечное число шагов.
Это определение свело вместе все отмеченные выше свойства алгоритма. Оно отвечает не на вопрос: «что такое алгоритм», а на вопрос: «что делает алгоритм». В практическом программировании второй вопрос возникает гораздо чаще и ответ на него для программиста-практика значительно важнее.
***
Языки программирования
Существует множество определений понятия «алгоритм»:
- «процедура, которая принимает любой из возможных входных экземпляров задачи и преобразует его в соответствии с требованиями, указанными в условии задачи» [1];
- «точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату» [2];
- «конечный набор правил, однозначно раскрывающих содержание и последовательность выполнения операций для систематического решения определенного класса задач за конечное число шагов» [3];
- «A computable set of steps to achieve a desired result» [4].
Из определений вытекают свойства алгоритма [5]:
- дискретность. В определениях 3 и 4 говорится, что алгоритм состоит из отдельных действий или правил. Алгоритм обладает дискретностью, если его можно разделить на отдельные этапы (части, команды);
- детерминированность (определенность). Алгоритм обладает свойством детерминированности, если для одних и тех же наборов исходных данных он будет выдавать один и тот же результат, т.е. результат однозначно определяется исходными данными (на это свойство указывается в определении 3);
- результативность. Свойство результативности означает, что алгоритм должен выдавать результат за конечное число шагов. О том, что число шагов должно быть конечным говорится в определениях 3 и 4;
- массовость. В определениях 1, 2, 3 говорится о некоторых классах задач (входных экземплярах задачи, варьируемых начальных данных) на которых алгоритм должен работать алгоритм. Это означает, что набор исходных данных, на которых алгоритм должен выдавать верное решение, заранее ограничен;
- правильность. Под правильностью понимается соответствие результатов работы алгоритма условию задачи (определение 1). Казалось бы, очень сомнительное свойство, ведь выше было описано свойство результативности, однако, программа должна не просто выдавать результат, а результат правильный.
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
Литература:
- Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил.
- ГОСТ 19781-74. Единая система программной документации. Термины и определения. Утв. пост. Госкомстата № 2051 от 08.05.08.
- Семененко В. А., Скуратович Э.К. Информатика и вычислительная техника: Учебное пособие. — М.: МГИУ, 2006. — 272 с
- Paul E. B. Dictionary of Algorithms, Data Structures, and Problems. [Электронный ресурс]/ Paul E. B. – режим доступа: https://xlinux.nist.gov/dads/HTML/algorithm.html. Дата обращения: 07.05.2017.
- Елабуга: изд-во ЕГПУ, 2009.- 72 с. 97 . Лизунова Е.М. Теория алгоритмов. Лекции 2007
- ГОСТ 19.701-90. ЕСПД. Схемы алгоритмов, программ, данных систем. Условные обозначения и правила выполнения
- Обзор литературы по алгоритмам