Свойства алгоритмов

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

Обратимся к примеру: алгоритм «Разжигание костра при хорошей погоде» Выберите место для костра в отдалении от деревьев и кустов. Соберите сухие ветки. Сложите их недалеко от выбранного для костра места. На месте костра сложите «шалашиком» тонкие сухие ветки. Положите под ветки бумагу для растопки. Пожгите бумагу. По мере разгорания, подкладывайте более толстые сухие ветки, соблюдая расстояние между ними для вентиляции. Конец алгоритма.

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

Приведенный алгоритм обладает свойством ДИСКРЕТНОСТИ, которое предполагает, что любой алгоритм должен состоять из последовательности шагов, следующих друг за другом. Следующий шаг выполняется только после завершения предыдущего.

Следующее свойство – ДЕТЕРМИНИРОВАННОСТЬ (точность), указывает, что любое действие в алгоритме должно быть строго и недвусмысленно определено и описано для каждого случая. Алгоритм «Разжигание костра при хорошей погоде» также обладает свойством детерминированности, т.к. все действия однозначно определены и отсутствует неопределенность в их выполнении.

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

1. Возьмите линейку. 2. Вытяните руку с линейкой. 3. Направьте руку на хорошо просматриваемый предмет. 4. Установите линейку вертикально. 5. Запомните количество делений линейки, соответствующих изображению предмета. 6. Умножьте длину руки на примерную высоту предмета. 7. Разделите получившееся число на измеренное в пункте 5 количество делений. Это и есть примерное расстояние до предмета.

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

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

Про такой алгоритм говорят, что он обладает свойством МАССОВОСТИ, которое подразумевает, что один и тот же алгоритм может применяться для решения целого класса задач, отличающихся исходными данными. Алгоритм «Разжигание костра при хорошей погоде» также обладает свойством массовости, т.к. в качестве исходных данных здесь используются сухие ветки (любых деревьев) и любой источник огня (спички, зажигалка и т.д.)

Представим, что в походе двое заядлых рыбаков принесли неплохой улов. Необходимо написать алгоритм определения победителя с учетом свойства массовости. Для этого следует представить алгоритм в общем виде и ввести переменные: В1 – вес рыбы, пойманный первым рыбаком; В2 – вес рыбы, пойманный вторым рыбаком.

Назовем алгоритм «Кто победил». 1.Определите В1. 2.Определите В2. 3.Если число В1 больше числа В2, то сообщите, что первый рыбак – победитель. 4.Если число В1 меньше числа В2, то сообщите, что второй рыбак – победитель. Конец алгоритма. По этому алгоритму можно определить победителя не только в рыбалке, но и в собирании грибов, ягод и т.д.

При всей простоте и очевидности алгоритма не каждый сразу поймет его ошибочность. В этом алгоритме не рассмотрена ситуация равенства чисел В1 и В2, которую следует учесть, добавив в алгоритм еще один пункт: 5. Если число В1 равно В2, то сообщите: «победила дружба». В уточненном алгоритме рассмотрены все возможные ситуации и для каждой из них получен результат. В таких случаях говорят, что алгоритм обладает свойством – РЕЗУЛЬТАТИВНОСТИ.

Из свойства результативности следует свойство КОНЕЧНОСТИ алгоритма, которое определяет завершение каждого действия в отдельности и алгоритма в целом за конечное число шагов.

АЛГОРИТМ ДискретностьДетерминированность Конечность Результативность Массовость Обобщим выводы рассмотренных примеров. Алгоритм характеризуется следующими свойствами: