В этой статье будет рассмотрено происхождение понятия «Алгоритм», а также то, какими свойствами обладают современные рациональные алгоритмы и какие задачи они решают. Дополнительное внимание будет уделено видам математических алгоритмов, которые могут быть представлены в виде циклов, разветвлений и линейных последовательностей.
Алгоритмом является определенная конечная последовательность инструкций, выполнение которых приводит к достижению конкретной цели (решению поставленной задачи). Существует множество разнообразных вариантов этого определения, которые можно найти в учебной литературе (чаще всего, это математические книги, а также учебники по информатике и программированию). Основная мысль тут следующая: алгоритм — это некий замкнутый перечень действий, а также дискретный процесс, у которого есть входная и выходная точки. И результат исполнения (решение) достигается за счет пошагового выполнения конкретной последовательности (арифметической, логической и т. п.).
С какими значениями можно связать слово «алгоритм»:
— цикл;
— метод (способ);
— процесс;
— рецепт;
— инструкция.
Немного истории
Это сегодня данное понятие является фундаментальным как в информатике, так и в математике. Но сам термин появился очень давно — тогда, когда еще не было персональных компьютеров, смартфонов и прочей вычислительной техники.
Впервые термин Algorithm был широко озвучен в средние века — это произошло, когда ученые Европы узнали о методах вычислений, используемых математиком из Азии Мухаммедом аль-Хорезми. Как раз от его имени и образовалось слово «Алгоритм».
В течение следующих веков после того, как перевели его сочинения, возникло множество математических трудов, которые были посвящены искусству счета. Если посмотреть на описание алгоритма европейцами в те далекие годы, то можно увидеть следующее определение:
Еще несколько терминов
Поначалу алгоритмизация подразумевала выполнение вычислительных действий над десятичными числами. Спустя годы, этот термин стал использоваться при обозначении любой последовательности, позволяющей достигать конкретного результата. Но эти последовательности не являются абстрактными — они разрабатываются для определенного исполнителя:
— человека;
— механизма;
— компьютера;
— роботизированного устройства;
— языка программирования и т. п.
Такой исполнитель характеризуется способностью исполнять поставленные перед ним задачи в виде соответствующих команд. Это значит, что последовательность описывается на понятном для исполнителя языке, формируя программу.
Способы представления алгоритмов бывают разные:
Подробнее о способах читайте здесь, а о блок-схемах — тут.
Основные свойства
Основные свойства следующие:
1. Массовость. Она же универсальность. Хороший и рациональный алгоритм может эффективно использоваться для разных наборов входных данных. Даже подставляя в абстрактную последовательность новые значения снова и снова, пользователь должен получать верный результат.
2. Дискретность. Другое название — разрывность. Здесь речь идет о структуре. Алгори тм считают дискретным, если он делится на шаги, то есть решить задачу — значит последовательно выполнить эти простые шаги или этапы, причем исполнение каждого шага занимает определенный временной отрезок. Такой алгоритм и будет дискретным.
3. Определенность. У этого свойства есть два синонима: точность и детерминированность. Важный момент — шаги должны быть строго определены, причем каждый, то есть разные толкования не допускаются. Строго определен и порядок выполнения этих этапов. Если все хорошо, при условии одинаковых исходных данных и той же самой цепочки команд (последовательности арифметических действий) результат будет одинаков для разных исполнителей.
4. Понятность, ясность. Уже выше было сказано, что последовательность описывается на понятном для исполнителя языке, то есть команды входят в систему понятий исполнителя.
5. Формальность. «Приказы не обсуждают, а выполняют» — говорит директор. Так и разработчик алгоритма — он формирует задачу исполнителю, к примеру, компьютеру, которому не важен смысл, — он просто выполняет соответствующие команды (задания) и получает результат. Зачем и почему — не его вопросы.
6. Завершаемость и результативность. При корректности входных данных рациональный алгоритм должен без проблем завершать свою работу за определенное и установленное разработчиком число шагов, то есть он не должен «зависать» и работать бесконечно. И завершение работы (решение алгоритма) будет сопровождаться получением конкретных результатов.
Виды алгоритмов: цикл, разветвление, линейная последовательность
Сегодня алгоритмов существует огромное множество. Если говорить вкратце, то можно выделить три основные группы:
— линейные;
— разветвляющиеся;
— циклические (они же циклы).
Следует рассмотреть эти группы подробнее, начиная с линейного алгоритма.
Линейность предполагает последовательное выполнение действий, то есть друг за другом. Вот как это может выглядеть на практике в виде блок-схемы:
Когда речь идет о разветвлении, подразумевается наличие хотя бы одного условия. Это условие проверяется по ходу работы. По итогу возможно разделение на несколько ветвей. Пример:
Отдельного упоминания заслуживает цикл, он же циклический алгоритм. При наличии цикла обеспечивается многократное повторение одной и той же операции. В цикле могут быть и вычисления, и перебор вариантов.
У цикла программы есть тело цикла (серия команд). И это тело цикла выполняется до тех пор, пока не будет удовлетворено конкретное условие.
Пример цикла на блок-схеме:
Источники:
- https://urok.1sept.ru/articles/631785;
- https://www.sites.google.com/site/algoritmyvidyisvojstva/materialy/sposoby-opisania-vidy-algoritmov;
- https://math-it.petrsu.ru/users/semenova/Informatika/DOC/Sam_Izuch/Algoritm.pdf.
