Какое свойство алгоритма детерминированность

Существует множество определений понятия «алгоритм»:

«процедура, которая принимает любой из возможных входных экземпляров задачи и преобразует его в соответствии с требованиями, указанными в условии задачи» [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].

check-brackets-flowchart Рис 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. ЕСПД. Схемы алгоритмов, программ, данных систем. Условные обозначения и правила выполнения
Обзор литературы по алгоритмам

Источник

На этом шаге мы рассмотрим основные свойства алгоритма.

Приведем перечень наиболее важных свойств алгоритма.

Дискретность.
Элементарность шагов.
Определенность (детерминированность).
Конечность (финитность).
Массовость.

Дадим краткую характеристику каждого свойства.

Дискретность означает, что алгоритм состоит из конечного числа описаний шагов и эти шаги
выполняются в дискретном времени, т. е. любые два последовательных шага
разделены при исполнении конечным, ненулевым отрезком времени. Можно считать,
что шаги выполняются мгновенно в моменты времени t0, t1, t2, …
-, а между этими моментами ничего не происходит.

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

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

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

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

Понятие данных (значений) — исходных,
промежуточных и результата также требует некоторого ограничительного
толкования. Наиболее общее интуитивное понимание состоит в том, что данными в
алгоритме могут служить самые разнообразные конструктивные объекты.

Конструктивный объект — это строгое
математическое понятие. Можно пока считать, что конструктивный объект — это
элемент какого-либо конечного множества (например, один из дней недели), либо
объект, вычисленный каким-либо алгоритмом. Конструктивными объектами являются
символы, логические значения, целые и вещественные числа, представимые в
машине, массивы конструктивных объектов. Алгоритм (его текст) также является
конструктивным объектом и, значит, может рассматриваться как данные для другого
алгоритма: текст программы (алгоритма) является входными данными для
программы-транслятора.

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

Замечание об определенности и
конечности: иногда считают, что алгоритм может заканчиваться без получения
результата (безрезультатная остановка) или даже не заканчиваться вовсе при
некоторых исходных данных (неприменимость к этим исходным данным). Взгляд на
это с точки зрения теории — машины Тьюринга — обсудим позже. С практической
точки зрения такая ситуация тоже требует внимания: операционная система (ОС)
вычислительной машины, являясь совокупностью алгоритмов, при нормальной работе
не предполагает остановки и выдачи каких-либо результатов; она лишь
добросовестно получает периодически входные данные-задания и запускает их;
задания-алгоритмы сами получают результаты. Таким образом, ОС не выдает
продукции, если не считать протокола ее работы. Другие диалоговые программные
системы также требуют для своего описания более широкой интерпретации понятия
алгоритма: они не получают входные данные сразу и не всегда можно говорить об
априорной ограниченности объема данных некоторой константой. Однако все
сказанное не умаляет важности приведенного понятия алгоритма, а говорит лишь о
богатстве проблематики компьютерных наук.

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

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

Рассмотрим такую проверку на примере
следующего текста (отыскание максимального и минимального элементов массива):

«Исходные данные — положительное число N, определяющее количество элементов массива
A, и целочисленные элементы A[1], A[2], …, A[N] массива A.
Значения всех чисел находятся в пределах непосредственно представимых в вычислительной машине. Кроме исходных
данных вводятся целочисленные переменные Max, Min, i. Первые две по окончании работы
алгоритма определяют его результаты, третья является вспомогательной. Действия
алгоритма состоят в выполнении следующих шагов:

Установить значения Мах = A[1], Min = A[1], i = 2.
Пока i <= N повторять шаги с 3 по 5.
Если Мах < A[i], то положить Мах = A[i].
Если Мin > A[i], то положить Мin = A[i].
Увеличить i на 1.
Вывести результаты Мах и Min.
Остановиться».

Проверим выполнение основных свойств.

Дискретность очевидна.

Элементарность шагов. Шаг 1 содержит три присваивания
значений; шаг 2 содержит одно сравнение чисел; шаги 3-5 содержат два сравнения
чисел, два присваивания значений (выполняется каждый раз только одно из них),
одно увеличение значения на единицу; шаг 6 — вывод на экран или на печать
данных ограниченного объема.

Определенность. Каждый шаг и алгоритм в целом
заканчивается определенным результатом; строго определена последовательность
шагов.

Конечность. Шаги 1 и 6 выполняются по одному
разу. Количество выполнений шагов 2-5 зависит от значений переменной
i и уровня N. Поскольку
i монотонно возрастает, то ее значение достигнет уровня N через
конечное число шагов. Если начальное значение переменной i
больше уровня N, то шаг 2 выполняется один раз, а шаги
3-5 не выполняется ни разу. Таким образом, в любом случае выполнение алгоритма
завершится через конечное число шагов.

Массовость. Алгоритм может воспринимать в
качестве исходных данных различные массивы разной длины.

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

Если k = 1, то остановиться.
Если k четное, то положить k = k/2; если k нечетное, то положить k = 3k+1.
Повторить, используя новое значение k.

Как следует из текста алгоритма,
имеется некоторый процесс изменения значения k, начинающийся
с определенного начального значения, затем на каждом шаге
k либо увеличивается, либо уменьшается и, наконец, возможно, приходит к
значению 1, на котором и останавливается. В общем случае процесс немонотонный.
Например, для k = 40:

k = 40, 20, 10, 5, 16, 8, 4, 2, 1 (8 шагов).

Решить вопрос о конечности данного
алгоритма — это значит доказать одно из двух утверждений:

для любого k процесс заканчивается единицей;
для некоторого k процесс не заканчивается.

Если k равно
степени двойки (2, 4, 8, 16, 32, …), то процесс будет монотонно убывающим и
завершится за число шагов, равное этой степени. В противном случае на некотором
промежуточном шаге значение k станет нечетным, но не равным единице,
и на следующем шаге значение k увеличится. Оба варианта (алгоритм заканчивается, алгоритм не заканчивается)
не кажутся очевидными. С одной стороны, увеличение k происходит в три раза, а уменьшение только в два раза и, если шаги увеличения и
уменьшения строго чередуются, то для такого процесса имеется общая тенденция к
возрастанию. С другой стороны, за шагом увеличения обязательно следует шаг
уменьшения, но обратное неверно, т. е. шагов уменьшения может быть и больше,
чем шагов увеличения. Потенциально возможно также зацикливание процесса, когда
на очередном шаге получается уже встречавшееся ранее значение. Вот типичный
пример с чередованием шагов:

k = 127, 382, 191, 574, 287, 862, 431, 1294, 647, 1942,
971, 2914, 1457, 4372, 2186, 1093, 3280, 1640, 820, 410, 205, 616, 308, 154,
77, 232, 116, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8,
4, 2, 1.

До значения k = 4372 шаги строго чередуются, затем начинается отрезок нерегулярного изменения,
на котором имеется 20 четных и 8 нечетных чисел, и заканчивается процесс «хвостом» из степеней двойки.

Можно показать, что для всех нечетных k = 2j — 1 или даже для
k = n2j — 1,
где n — нечетное натуральное число, начальный участок
последовательности является строго чередующимся до достижения величины
2(n3j — 1); причем длина участка строгого чередования шагов
пропорциональна величине j. Это плохая тенденция, поскольку
k удаляется от 1. С другой стороны, для
многих сочетаний n и j величина n3j — 1 = m2p —
пропорциональна степени двойки. В этом случае вслед за возрастанием
k идет группа операций деления на 2,
«сбрасывающая» значение k
до величины m.

В целом вопрос о конечности этого алгоритма должен
решаться методами теории чисел. Несмотря на ряд усилий, предпринимавшихся
математиками, решение пока не найдено. Более подробный анализ задачи можно
найти в книге Ю. Нивергельт, Дж. Фаррар, Э. Рейнгольд «Машинный подход к
решению математических задач» (М.: Мир, 1977. С. 298).

На следующем шаге мы рассмотрим понятие исполнителя алгоритма.

Источник

ПОНЯТИЕ АЛГОРИТМА.
СВОЙСТВА АЛГОРИТМА. ВИДЫ АЛГОРИТМОВ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

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

Основными свойствами
алгоритма являются:

детерминированность
(определенность). Предполагает получение однозначного результата вычислительного
процecca при заданных исходных данных. Благодаря этому свойству процесс
выполнения алгоритма носит механический характер;
результативность.
Указывает на наличие таких исходных данных, для которых реализуемый
по заданному алгоритму вычислительный процесс должен через конечное
число шагов остановиться и выдать искомый результат;
массовость. Это
свойство предполагает, что алгоритм должен быть пригоден для решения
всех задач данного типа;
дискретность.
Означает расчлененность определяемого алгоритмом вычислительного процесса
на отдельные этапы, возможность выполнения которых исполнителем (компьютером)
не вызывает сомнений.

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

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

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

При всем многообразии
алгоритмов решения задач в них можно выделить три основных вида вычислительных
процессов:

линейный;
ветвящийся;
циклический.

Линейным
называется такой вычислительный процесс, при котором все этапы решения
задачи выполняются в естественном порядке следования записи этих этапов.

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

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

Источник