АЛГОРИТМ
Алгори́тм (лат. algorithmi — от имени среднеазиатского математика Аль-Хорезми) — конечная совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Ранее в русском языке писали «алгорифм», сейчас такое написание используется редко, но тем не менее имеет место исключение (нормальный алгорифм Маркова).
Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам — так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек (а может быть и некоторый механизм, например, ткацкий или токарный станок с числовым управлением).
Можно выделить алгоритмы вычислительные (далее речь в основном идёт о них) и управляющие. Вычислительные алгоритмы, по сути, преобразуют некоторые начальные данные в выходные, реализуя вычисление некоторой функции. Семантика управляющих алгоритмов существенным образом может отличаться и сводиться к выдаче необходимых управляющих воздействий либо в заданные моменты времени, либо в качестве реакции на внешние события (в этом случае, в отличие от вычислительного алгоритма, управляющий может оставаться корректным при бесконечном выполнении).
Понятие алгоритма относится к первоначальным, основным, базисным понятиям математики. Вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. Однако в явном виде понятие алгоритма сформировалось лишь в начале XX века.
Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem), которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений или «эффективного метода»; среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ-исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга.
В широком смысле алгоритм — это последовательность действий, которые нужно выполнить, чтобы получить определённый результат.
Слово «алгоритм» произошло от имени персидского математика Абу Абдуллаха аль-Хорезми. В своём труде «Китаб аль-джебр валь-мукабала» учёный впервые дал описание десятичной системы счисления. А наука алгебра получила своё название в честь его книги.
Мы часто пользуемся алгоритмами в повседневной жизни. Например, когда хотим приготовить кофе в капсульной кофемашине, руководствуемся примерно таким алгоритмом:
1. Устанавливаем капсулу.
2. Проверяем уровень воды в специальном отсеке.
3. Если воды недостаточно — доливаем.
4. Ставим чашку под кран кофемашины.
5. Запускаем кофемашину.
6. Выключаем кофемашину, когда чашка наполнилась.
7. Достаём кружку.
Если не перепутать порядок шагов, то с помощью такой инструкции любой сможет порадовать себя чашкой горячего кофе. Достаточно лишь знать, как установить капсулу и включить/выключить кофемашину.
С компьютерами намного сложнее. Им неизвестно, что значит «установить капсулу», «долить воду», «запустить кофемашину» и так далее. Чтобы запрограммировать робота-баристу под определённую модель бытовой техники, алгоритм придётся расписать более детально:
1. Возьми штепсельную вилку шнура питания кофемашины.
2. Вставь штепсельную вилку в розетку.
3. Проверь, есть ли вода в отсеке для воды.
4. Если воды недостаточно:
4.1. Подними крышку отсека.
4.2. Возьми кувшин с водой.
4.3. Лей воду из кувшина в отсек, пока он не заполнится.
4.4. Закрой крышку отсека.
4.5. Поставь кувшин с водой на стол.
5. Открой крышку кофемашины.
6. Возьми из коробки капсулу с кофе.
7. Вставь капсулу в отсек для капсулы.
8. Закрой крышку кофемашины.
9. Поверни рычаг кофемашины вправо.
10. Когда чашка наполнится, поверни рычаг кофемашины влево.
11. Возьми кружку.
12. Принеси кружку хозяину.
Конечно, если мы собираем робота с нуля, то даже такой детализации будет недостаточно. Каждую процедуру ещё нужно будет реализовать на языке программирования (например, на C++ или Python), что само по себе — нетривиальная задача. Тем не менее описание стало более точным и формальным.
C научной точки зрения определение алгоритма, которое мы дали выше, не совсем точное. Ведь не всякую последовательность действий, приводящую к результату, можно назвать алгоритмом.
Алгоритм в информатике — это понятный исполнителю набор правил для решения конкретного множества задач, который получает входные данные и возвращает результат за конечное время.
Для чего нужны алгоритмы
У алгоритмов есть два замечательных качества: они позволяют эффективно решать задачи и не изобретать решения, которые кто-то уже придумал до нас. Это справедливо как для повседневной жизни, так и для IT.