Энциклопедия информационной безопасности. По всем вопросам обращайтесь по адресу swan@wikisec.ru
Алгоритм: различия между версиями
Wikiadmin (обсуждение | вклад) м (1 версия импортирована) |
Wikiadmin (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
«Алгоритм — это точное предписание, которое задает вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и напрвленный на получение полностью определяемым этим исходным данным результата». | «Алгоритм — это точное предписание, которое задает вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и напрвленный на получение полностью определяемым этим исходным данным результата». | ||
| − | Часто в качестве исполнителя выступает | + | Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек. |
== Формальные признаки алгоритмов == | == Формальные признаки алгоритмов == | ||
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований: | Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований: | ||
| − | * Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный | + | * Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного. |
* Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд. | * Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд. | ||
* Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0. | * Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0. | ||
| Строка 39: | Строка 39: | ||
* Алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных | * Алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
[[Категория: Определения]] | [[Категория: Определения]] | ||
Текущая версия на 19:37, 23 ноября 2019
Определения алгоритма
Единого «истинного» определения понятия «алгоритм» нет.
«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Дональд Эрвин Кнут)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (Колмогоров, Андрей Николаевич)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (Марков, Андрей Андреевич (младший))
«Алгоритм — точное предписание о выполнении в определенном порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
«Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов».
«Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».
«Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи».
«Алгоритм — это некоторый конечный набор рассчитанных на определённого исполнителя операций в результате выполнения которых через определённое число шагов может быть достигнута поставленная цель или решена задача определённого типа».
«Алгоритм — это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».
«Алгоритм — это точная, однозначная, конечная последовательность действий, которую должен выполнить пользователь для достижения конкретной цели либо для решения конкретной задачи или группы задач».
«Алгоритм — это точное предписание, которое задает вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и напрвленный на получение полностью определяемым этим исходным данным результата».
Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.
Формальные признаки алгоритмов
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
- Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
- Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
- Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
- Массовость — алгоритм должен быть применим к разным наборам исходных данных.
- Результативность — завершение алгоритма определенными результатами.
- Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не дает результатов вовсе.
- Алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных
