Алгоритм - История изменений

Wikiadmin в 16:37, 23 ноября 2019

2019-11-23T16:37:46Z

Wikiadmin: 1 версия импортирована

2019-10-29T11:01:45Z

1 версия импортирована

wikisec>Swan: /* Ссылки */

2009-09-27T11:26:49Z

Ссылки

Новая страница

== Определения алгоритма ==
Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Дональд Эрвин Кнут)

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (Колмогоров, Андрей Николаевич)

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

«Алгоритм — точное предписание о выполнении в определенном порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)

«Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов».

«Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».

«Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи».

«Алгоритм — это некоторый конечный набор рассчитанных на определённого исполнителя операций в результате выполнения которых через определённое число шагов может быть достигнута поставленная цель или решена задача определённого типа».

«Алгоритм — это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».

«Алгоритм — это точная, однозначная, конечная последовательность действий, которую должен выполнить пользователь для достижения конкретной цели либо для решения конкретной задачи или группы задач».

«Алгоритм — это точное предписание, которое задает вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и напрвленный на получение полностью определяемым этим исходным данным результата».

Часто в качестве исполнителя выступает [[компьютер]], но понятие алгоритма необязательно относится к [[Компьютерная программа|компьютерным программам]], так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.

== Формальные признаки алгоритмов ==
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

* Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный [[Граф алгоритма|граф]]. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
* Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
* Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
* Массовость — алгоритм должен быть применим к разным наборам исходных данных.
* Результативность — завершение алгоритма определенными результатами.
* Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не дает результатов вовсе.
* Алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных

Профессор Дейкстра первым показал в своих статьях и книге «Дисциплина программирования» как составляются алгоритмы и программы без ошибок с доказательствами их правильности.

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

Важную роль играют [[Рекурсивный алгоритм|рекурсивные алгоритмы]] (алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения). Начиная с конца XX - начала XXI века активно разрабатываются [[параллельные алгоритмы]], предназначенные для вычислительных машин, способных выполнять несколько операций одновременно.

== Наличие исходных данных и некоторого результата ==

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

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

Для разработки алгоритмов и программ используется '''алгоритмизация''' — процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально важны детерминированность, результативность и массовость, а также правильность результатов решения поставленных задач.

== Форма алгоритмов ==
Алгоритм может быть записан словами и изображён схематически. Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, [[машинный код]]). Например, для описания алгоритма применяются [[Блок-схема алгоритма|блок-схемы]]. Другим вариантом описания, не зависимым от языка программирования, является [[псевдокод]].

== Эффективность алгоритмов ==
Хотя в определении алгоритма требуется лишь конечность числа шагов, требуемых для достижения результата, на практике выполнение даже хотя бы миллиарда шагов является слишком медленным. Также обычно есть другие ограничения (на размер программы, на допустимые действия). В связи с этим вводят такие понятия как [[сложность алгоритма]] ([[Временная сложность алгоритма|временна́я]], по размеру программы, [[Сложность вычисления (битовая)|вычислительная]] и др.).

Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной [[Информатика|информатики]]. В 50-х гг. XX века появилась даже отдельная её область — [[быстрые алгоритмы]]. В частности, в известной всем с детства задаче об умножении десятичных чисел обнаружился ряд алгоритмов, позволяющих существенно (в [[Асимптотическая оценка|асимптотическом смысле]]) ускорить нахождение произведения. См. [[быстрое умножение]]

== Ссылки ==
* [http://algolist.manual.ru Алгоритмы, методы, исходники] — сайт по алгоритмам и методам программирования
* [http://rain.ifmo.ru/cat/view.php/ Дискретная математика: Алгоритмы] — список алгоритмов
* [http://www.geometrictools.com Геометрические алгоритмы]
* [http://www.krugosvet.ru/articles/125/1012581/1012581a1.htm о Алгоритме] в энциклопедии «Кругосвет»
* [http://www.scholar.ru/catalog.php?topic_id=18 Статьи по алгоритмам из научных библиотек]
[[Категория: Определения]]

@@ Строка 26: / Строка 26: @@
 «Алгоритм — это точное предписание, которое задает вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и напрвленный на получение полностью определяемым этим исходным данным результата».
-Часто в качестве исполнителя выступает [[компьютер]], но понятие алгоритма необязательно относится к [[Компьютерная программа|компьютерным программам]], так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.
+Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.
 == Формальные признаки алгоритмов ==
 Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
-* Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный [[Граф алгоритма|граф]]. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
+* Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
 * Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
 * Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
@@ Строка 39: / Строка 39: @@
 * Алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных
 [[Категория: Определения]]

← Предыдущая	Версия 11:01, 29 октября 2019
(нет различий)