Понятие алгоритм
Автор Zimniy задал вопрос в разделе Компьютеры, Связь
Что такое понятие алгоритма и свойства алгоритма? и получил лучший ответ
Ответ от Anna Andriyanenko[гуру]
Алгоритм -- одно из основных математических понятий. Однако с алгоритмами человеку приходится иметь дело не только в математике. Почти во всех сферах жизни мы повседневно сталкиваемся с инструкциями, предписаниями, рецептами, правилами, в соответствии с которыми происходит та или иная человеческая деятельность. Вот два простых примера.
(А)
1. Опустить жетон в щель телефонного автомата, снять трубку.
2. Услышав длинный гудок, набрать номер 22 44 45.
3. Если раздаются короткие гудки, то повесить трубку, взять жетон и повторить все заново.
(Б)
Растворить 1-2 чайные ложки порошка в горячей воде. Сахар и молоко добавлять по вкусу.
Похожим образом звучат руководства по эксплуатации стиральной и швейной машины, автомобиля, инструкции по конструированию моделей корабля или самолета.
Неформально алгоритм можно определить как точное и понятное, т. е. сформулированное на определенном языке, конечное описание общего способа решения некоторого класса задач с использованием элементарных исполнимых шагов.
Приведенная формулировка скорее поясняет, что такое алгоритм, чем дает точное определение, поскольку она использует весьма неоднозначные термины. Например, что значит "точное" описание? Для кого оно должно быть "понятным"?
Обычно требуют, чтобы алгоритм
-- представлял собой общий метод решения однотипных задач для любых исходных данных -- параметров алгоритма;
-- был составлен настолько точно, чтобы было возможным его однозначное понимание;
-- представлял собой конечное описание, иначе его передача исполнителю длилась бы бесконечно долго.
Кроме того, необходимо каким-то образом задать исполнителя, который вполне самостоятельно, без нашего участия, умел бы исполнять элементарные шаги некоторого фиксированного заранее набора, а также выстраивать друг за другом исполнение этих шагов в том порядке, как это предписано алгоритмом.
Приведенные выше примеры (А) и (Б) не вполне удовлетворяют всем требованиям, предъявляемым к алгоритму: во-первых, здесь нельзя говорить об общем методе, а кроме того, нет и достаточной точности.
От алгоритма требуют часто, чтобы он заканчивался, т. е. выполнял конечное число элементарных шагов при любых исходных данных. Такой алгоритм называют завершающимся. Хотя существуют и незавершающиеся алгоритмы, которые заканчиваются лишь при входных данных из некоторого непустого подмножества, называемого областью применимости алгоритма, мы почти всегда будем рассматривать только завершающиеся алгоритмы.
Простейшими алгоритмами являются известные правила, по которым выполняются арифметические действия в десятичной системе счисления. Например, для суммирования двух многозначных чисел исполнитель рассматривает слагаемые как строки цифр, расположенных "столбиком", и конструирует строку цифр результата справа налево при обработке пар соответствующих цифр слагаемых выполнением операций следующих двух типов: запись соответствующей цифры суммы, пометка о переносе над соседней слева цифрой. Эти операции рассматриваются как элементарные и выполняются исполнителем по раз и навсегда заданной таблице сложения цифр, которую мы в детстве заучиваем наизусть.
В качестве более сложного примера рассмотрим алгоритм Эвклида, решающий все задачи следующего типа: для данных двух натуральных чисел и найти их наибольший общий делитель. Очевидно, различных задач такого типа существует столько, сколько есть различных пар натуральных чисел и. Предписание, пригодное для решения студентом любой из этих задач, можно было бы задать в виде следующей последовательности указаний.
(B)
Если коротко, то заходим на ссылка, набираем в окошке поиска "алгоритм", давим на "ENTER" и читаем:
"Алгоритм - точное предписание исполнителю совеpшить определенную последовательность действий для достижения поставленной цели за конечное число шагов. "
Если длинно, то на википедию. Ссылочка приложена.
Слово алгоритм происходит от algorithml — латинской формы написания имени великого математика IX в. аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению поставленной задачи.
Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.
Алгоритм деления отрезка АВ пополам:
поставить ножку циркуля в точку А;
установить раствор циркуля равным длине отрезка АВ;
провести окружность;
поставить ножку циркуля в точку В;
провести окружность;
через точки пересечения окружностей провести прямую;
отметить точку пересечения этой прямой с отрезком АВ.
Каждое указание алгоритма предписывает исполнителю выполнить одно конкретное законченное действие. Исполнитель не может перейти к выполнению следующей операции, не закончив полностью выполнения предыдущей. Предписания алгоритма надо выполнять последовательно одно за другим, в соответствии с указанным порядком их записи. Выполнение всех предписаний гарантирует правильное решение задачи. Данный алгоритм будет понятен исполнителю, умеющему работать с циркулем и знающему, что такое поставить ножку циркуля, провести окружность и т, д.
Анализ примеров различных алгоритмов показывает, что запись алгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. После каждого шага исполнения алгоритма точно известно, какая команда должна выполняться следующей.
Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели. Разделение выполнения решения задачи на отдельные операции (выполняемые исполнителем по определенным командам) — важное свойство алгоритмов, называемое дискретностью.
Каждый алгоритм строится в расчете на некоторого исполнителя. Для того чтобы исполнитель мог решить задачу по заданному алгоритму, необходимо, чтобы он был в состоянии понять и выполнить каждое действие, предписываемое командами алгоритма. Такое свойство алгоритмов называется определенностью (или точностью) алгоритма.
Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя.
Еще одно важное требование, предъявляемое к алгоритмам, — результативность (или конечность) алгоритма. Оно означает, что исполнение алгоритма должно закончиться за конечное число шагов.
Приведем еще один пример алгоритма.
Игра Ваше (в игре участвуют двое) .
Рассмотрим частный случай этой игры. Имеется 15 предметов. Соперники ходят по очереди, за каждый ход любой из играющих может взять 1, 2 или 3 предмета. Проигрывает тот, кто вынужден взять последний предмет.
Алгоритм выигрыша для первого игрока имеет следующий вид:
взять два предмета;
второй и последующий ходы делать так, чтобы количество предметов, взятых вместе с соперником за очередной ход, в сумме составляло 4.
Данный алгоритм приводит к выигрышу для 7, 11, 15, 19, ..предметов.
Человек, пользующийся данным алгоритмом, всегда будет выигрывать в этой игре. Ему совершенно необязательно знать, почему надо поступать именно так, а не иначе. Для успешной игры от него требуется только строго следовать алгоритму.
Таким образом, выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В таком случае говорят, что исполнитель действует формально, т. е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции.
Это очень важная особенность алгоритмов. Наличие алгоритма формализовало процесс, исключило рассуждения. Если обратиться к примерам других алгоритмов, то можно увидеть, что и он