Что такое определенность в информатике
Алгоритм. Свойства алгоритма
Существует множество определений понятия «алгоритм»:
Из определений вытекают свойства алгоритма [5]:
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
какие бывают свойства алгоритма?
Одним из таких свойств является дискретность. Под дискретностью понимается то, что алгоритм состоит из описания последовательности шагов обработки, организованный таким образом, что в начальный момент задаётся исходная ситуация, а после каждого следующего шага ситуация преобразуется на основе данных, полученные в предшествующие шаги обработки. Дискретность алгоритма означает, что он исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Другое свойство принято называть определённостью. Оно означает, что на каждом шаге однозначно определено преобразование объектов среды исполнителя, полученных на предшествующих шагах алгоритма.
К примеру, в одном из кулинарных рецептов сказано:
Слегка потрясите, чтобы смесь стала комковатой. Подогрейте коньяк в маленькой кастрюльке и влейте её в смесь.
Формальному исполнителю здесь неясно, требуется ли трясти смесь, пока она вся не станет комом, и какой всё-таки величины кастрюля. Большая или маленькая? И до какой температуры надо подогреть коньяк. Так что такой алгоритм любому исполнителю выполнить довольно трудно, практически невозможно. Можно сказать, что в алгоритме не должны присутствовать не определённые слова: немного, чуть-чуть, слегка и т. д.
Надо сказать, что алгоритм должен быть понятен не только автору, но и исполнителю. Если мы предложим исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т. к. такой программы в нём не заложено. Или, например, если мы предложим какому-нибудь мальчику испечь торт то у него, как правило, ни чего не получится, потому что этого они делать не умеют. Но если мы составим подробный алгоритм работы, разобьем его на элементарные шаги, такие, что он без труда поймёт и сможет выполнить каждый шаг, то он сможет успешно испечь любой торт. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Это свойство алгоритма называют понятностью.
Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности
Свойства алгоритма
К алгоритму решения задач предъявляются высокие требования. Он должен обладать дискретностью, массовостью, компактностью, детерминированностью и результативностью.
Дискретность алгоритма определяет то, что всякий алгоритм имеет прерывистый, дискретный характер, т.е. представляет собой последовательность выполненных один за другим отдельно законченных шагов.
Массовостью алгоритма называется его способность быть пригодным для решения широкого класса задач данного типа. Алгоритм должен составляться не для решения отдельно взятой проблемы (задачи), а для создания возможности решения всех типов подобных проблем.
Детерминированность (определенность) алгоритма – это строгая определенность (однозначность предписываемых действий в каждой инструкции алгоритма), конкретность, чтобы в его записи не оставалось место двусмысленности и произвольному толкованию.
Результативностьюалгоритма называется свойство обеспечения нужного результата за конечное число шагов, если данные принадлежат области исходных данных, которыми определена массовость алгоритма.
Конечность определяет, что каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.
Понятность алгоритма – это обязательность составления алгоритма учетом системы команд исполнителя, т.е. алгоритм должен быть зафиксирован в той форме, которая будет понятна исполнителю. Значения всех приведенных действий в алгоритме должны быть ясными, точными и определенными.
Компактностью алгоритма называется его краткость, свойство минимальности инструкций. Наиболее удачно составленным алгоритмом считается алгоритм, обладающий компактностью и минимальностью количества вычислений при обязательной массовости алгоритма.
Каждый исполнитель должен однозначно понимать правило выполнения каждого действия алгоритма. Это называется свойством однозначности алгоритма.
Студентик.РФ
Алгоритмы
Свойства алгоритма
Алгоритм обладает следующими основными свойствами:
Дискретность – свойство алгоритма, которое характеризует его структуру. Любой алгоритм состоит из отдельных операций (этапов, действий), которые выполняются дискретно (по шагам). Это означает, что алгоритм обладает свойством дискретности.
Детерминированность – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не может допускать различных толкований. Также строго должен быть определен порядок выполнения отдельных шагов, то есть исполнитель должен точно знать последовательность выполнения операций. Любой алгоритм должен быть представлен таким образом, чтобы он мог быть однозначно (точно) реализован исполнителем. Это свойство алгоритма называют также определенностью, однозначностью или точностью.
Массовость (универсальность) – применимость алгоритма ко всем задачам рассматриваемого типа при любых допустимых множествах исходных данных. Здесь важно подчеркнуть, что массовость означает применимость алгоритма ко всем задачам рассматриваемого типа, то есть ко всем задачам, для решения которых он предназначен. Кроме того, здесь необходимо иметь в виду, что реализация алгоритма возможна при любых, но допустимых множествах исходных данных.
Формальность – свойство означающее, что любой исполнитель, выполняющий алгоритм (например, компьютер), действует формально, то есть строго выполняет инструкции предусмотренные разработчиком алгоритма.
Алгоритмизация | Лекция №1
Алгоритм и его свойства
Понятие алгоритма
Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение этого термина связано с математикой. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов.
Термин алгоритм происходит от имени средневекового персидского математика Мухаммеда Аль-Хорезми (787 – 850 гг.), который еще в IX в. (825 г.) дал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.
С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинировании четырех операций арифметического исчисления – сложения, вычитания, умножения, деления.
К 1950 г. алгорисмус стал алгорифмом. Смысл алгорифма чаще всего связывался с алгорифмами Евклида – процессами нахождения наибольшего общего делителя двух натуральных чисел, наибольшей общей меры двух отрезков и т.п.
Под алгоритмом понимали конечную последовательность точно сформулированных правил, которые позволяют решать те или иные классы задач. Это определение не является строго математическим, так как в нем не содержится точной характеристики того, что следует понимать под классом задач и под правилами их решения.
Первоначально для записи алгоритмов пользовались средствами обычного языка (словесное представление алгоритмов).
Примеры алгоритмов
Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгоритмами (первый алгоритм).
Алгоритмы, в соответствии с которыми решение поставленных задач сводится к логическим действиям, называются логическими алгоритмами (второй алгоритм, поиск пути в лабиринте и др.).
Алгоритм – это понятное и точное предписание (указание) исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи (приводящую от исходных данных к искомому результату).
Разработать алгоритм означает разбить задачу на определенную последовательность шагов. От разработчика алгоритма требуется знание особенностей и правил составления алгоритмов.
Каждое указание алгоритма предписывает исполнителю выполнить одно конкретное действие. Исполнитель не может перейти к выполнению следующей операции, не закончив полностью выполнения предыдущей. Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели. Разделение выполнения решения задачи на отдельные операции, выполняемые исполнителем по определенным командам – важное свойство алгоритмов, называемое дискретностью.
Алгоритм представляет собой последовательность команд (инструкций, директив), определяющих действия исполнителя (субъекта или управляемого объекта). Исполнитель, выполняя алгоритм, может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В этом случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и строго выполняет инструкции. Таким образом, возможность решения задачи, механически исполняя команды алгоритма в указанной последовательности, называется формальностью.
Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Для того чтобы алгоритм мог быть выполнен, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. Нельзя повару поручать работу токаря, какая бы подробная инструкция ему не давалась. У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Каждая команда алгоритма должна определять однозначно действие исполнителя. Такое свойство алгоритмов называется определенностью (или точностью) алгоритма.
Алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые он может выполнить. Это свойство алгоритма называется понятностью. Алгоритм не должен быть рассчитан на принятие каких-либо самостоятельных решений исполнителем, не предусмотренных алгоритмом.
Еще одно важное требование, предъявляемое к алгоритмам, – результативность (или конечность) алгоритма. Оно означает, что исполнение алгоритма должно закончиться за конечное число шагов.
Разработка алгоритмов – процесс творческий, требующий умственных усилий и затрат времени. Поэтому предпочтительно разрабатывать алгоритмы, обеспечивающие решения всего класса задач данного типа. Например, если составляется алгоритм решения кубического уравнения ax 3 + bx 2 + cx + d = 0, то он должен быть вариативен, т.е. обеспечивать возможность решения для любых допустимых исходных значений коэффициентов a, b, c, d. Про такой алгоритм говорят, что он отвечает требованию массовости.
Основные особенности и свойства алгоритмов:
Свойства дискретности, формальности, точности, понятности и конечности являются необходимыми (иначе это не алгоритм). Свойство массовости не является необходимым свойством алгоритма, оно скорее определяет его качество.
Алгоритмы можно записывать по-разному. Форма записи, состав и количество операций алгоритма зависит от того, кто будет исполнителем этого алгоритма.
Способы описания алгоритма:
Например: найти большее из трех чисел.
Алгоритм БИТ