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

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

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

3. Понятность. Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Понятность алгоритма означает знание исполнителя алгоритма о том, что надо делать для его исполнения.

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

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

5. Конечность. Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут выполняться многократно.

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

6. Определенность.Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен допускать произвольной трактовки исполнителем. При исполнении алгоритма исполнитель должен действовать строго в соответствии с его правилами и у него не должно возникать потребности предпринимать какие-либо действия, отличные от предписанных алгоритмом. Иными словами, алгоритм рассчитан на чисто механическое исполнение. Это означает, что если один и тот же алгоритм поручить для исполнения разным исполнителям, то они придут к одному и тому же результату, лишь бы исполнители понимали алгоритм.

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

7. Эффективность.Алгоритм должен быть эффективен – значит, действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Кроме того, эффективность означает, что алгоритм может быть выполнен не просто за конечное, а за разумное конечное время(обычно важно, чтобы задача по разработанному алгоритму решалась как можно быстрее).Вот почему при разработке алгоритмов должны учитываться и возможности конкретных физических исполнителей алгоритма.

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

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

Построение такого формального определения было начато с формализации объектов (операндов) алгоритма, т.к. в интуитивном понятии алгоритма его объекты могут иметь произвольную природу. Ими могут быть, например, числа, показания счетчиков, фиксирующих параметры некоторого процесса и т.п. Однако, полагая, что алгоритм имеет дело не с самими реальными объектами, а их образами, можно считать, что операнды алгоритма есть слова в произвольном алфавите. Тогда получается, что алгоритм преобразует слова в произвольном алфавите в слова того же алфавита. Дальнейшая формализация понятия алгоритма связана с формализацией действий над операндами и порядка этих действий. Одна из таких формализаций была предложена в 1936 г. английским математиком А. Тьюрингом, который формально описал конструкцию некоторой абстрактной машины (машины Тьюринга) как исполнителя алгоритма и высказал основной тезис о том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга. Примерно в это же время американским математиком Э. Постом была предложена другая формальная алгоритмическая схема – машина Поста, а в 1954 г. советским математиком А.А. Марковым была разработана теория класса алгоритмов, названных им нормальными алгоритмами, и высказан основной тезис о том, что всякий алгоритм нормализуем.

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

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

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

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

I. Дискретность

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

II. Определённость

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

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

Формальному исполнителю здесь неясно, требуется ли трясти смесь, пока она вся не станет комом, и какой всё-таки величины кастрюля. Большая или маленькая? И до какой температуры надо подогреть коньяк. Так что такой алгоритм любому исполнителю выполнить довольно трудно, практически невозможно. Можно сказать, что в алгоритме не должны присутствовать не определённые слова: немного, чуть-чуть, слегка и т. д.

III. Результативность

Третье свойство – результативность алгоритма. Это свойство подразумевает, что каждый шаг (и алгоритм в целом) после своего завершения даёт среду, в которой все имеющиеся объекты однозначно определены. Если это по каким – либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует.

К примеру, в инструкции по применению лекарства от кашля сказано:
Если врач не прописал, то принимать 3-4 раза в день по 15-20 капель, лучше всего в горячей сладкой воде.
Здесь не определено, например, когда должен заканчиваться алгоритм – когда кашель пройдет или когда лекарство закончиться. Свойство результативности обычно подразумевает конечность алгоритма, т. е. завершение его работы за конечное число шагов (при этом количество шагов может быть заранее не известным и различным для разных исходных данных) .

IV. Понятность

Надо сказать, что алгоритм должен быть понятен не только автору, но и исполнителю. Если мы предложим исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т. к. такой программы в нём не заложено. Или, например, если мы предложим какому-нибудь мальчику испечь торт то у него, как правило, ни чего не получится, потому что этого они делать не умеют. Но если мы составим подробный алгоритм работы, разобьем его на элементарные шаги, такие, что он без труда поймёт и сможет выполнить каждый шаг, то он сможет успешно испечь любой торт. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Это свойство алгоритма называют понятностью.

V. Массовость

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