Алгоритмы

Что такое алгоритм? В старой трактовке алгори́тм это точный набор инструкций, описывающих последовательность действий некоторого исполнителя для достижения результата, решения некоторой задачи за конечное время. По мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми.

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

Определения алгоритма Единого «истинного» определения понятия «алгоритм» нет. «Алгоритм это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут) «Алгоритм это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров) «Алгоритм это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков) «Алгоритм строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович) «Алгоритм это последовательность действий, направленных на получение определённого результата за конечное число шагов». (ROXANstudio) «Алгоритм это строго определённая последовательность действий, направленная на достижение определённых целей за конечное число шагов». (Привалов Егор Николаевич) «Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображён схематически. Практически любое неслучайное повторяемое действие поддаётся описанию через алгоритм». ([grey_olli]) «Алгоритм однозначно, доступно и кратко (условные понятия названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».

Признаки алгоритмов ДетерминированностьПонятностьКонечностьМассовость

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

Понятность Понятность алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

Завершаемость (конечность) Завершаемость (конечность) при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

Массовость Массовость алгоритм должен быть применим к разным наборам исходных данных.

История термина «Алгоритм» Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Абу Абдулла (или Абу Джафар) Мухаммед ибн Муса аль-Хорезми

Алгоритмы ЛинейныеРазветвляющиесяЦиклические Основные виды алгоритмов

Основные способы записи алгоритма На формальном языке (языке программирования) В виде блок-схемы

Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном формальном языке.

Алгоритм действия пешехода, который позволит ему безопасно перейти улицу 1. Подойти к дороге. 2. Дождаться зелёного сигнала светофора. 3. Перейти дорогу. 4. Если впереди есть ещё одна дорога, то перейти к шагу 1.

Запись алгоритма в виде блок- схемы Запись алгоритма в виде блок схемы позволяет увидеть структуру алгоритма наглядно, без использования специфического языка. Часто такая запись позволяет выявить ошибки в алгоритме

Основные блоки алгоритмов Блок операции Начало и конец алгоритма Блок ввода/вывода Алтернативный блок (блок условия)

Разбить яйцо на сковороду Линейный алгоритм приготовления яичницы Начало Разогреть сковороду Налить масло на сковороду Взять яйцо Посолить яйцо Подождать 5 минут Конец

Подойти к дороге. Дождаться зелёного сигнала светофора. Перейти дорогу. Начало Впереди есть ещё одна дорога? Конец нет да Циклический алгоритм действия пешехода, который позволит ему безопасно перейти улицу

Условный алгоритм похода в магазин Начало Есть продукты? Взять деньги, одеться, выйти из дома, дойти до магазина Конец да Магазин работает? нет Идти к другому магазину Купить продукты Конец да нет

С развитием вычислительной техники и теории программирования возрастает необходимость построения новых экономичных алгоритмов, изменяются способы их построения, способы записи алгоритмов на языке, понятном исполнителю. Особый тип исполнителя алгоритмов – компьютер, поэтому необходимо создавать специальные средства, позволяющие, с одной стороны, разработчику в удобном виде записывать алгоритмы, а с другой – дающие компьютеру возможность понимать написанное. Такими средствами являются языки программирования или алгоритмические языки.