Что такое алгоритм и его свойства

Знакомимся с понятием алгоритма — фундаментом всего программирования — и его обязательными свойствами.

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

Алгоритмы вокруг нас

Слово «алгоритм» звучит сложно, но ты пользуешься алгоритмами каждый день. Рецепт блинов — это алгоритм: смешай муку, яйца и молоко, разогрей сковороду, налей тесто, переверни. Инструкция по сборке шкафа — алгоритм. Даже путь от дома до школы можно описать алгоритмом: выйди из подъезда, поверни направо, дойди до перекрёстка, перейди дорогу.

Объединяет все эти примеры одно: есть чёткая последовательность шагов, которая приводит к цели. В этом и суть. А программирование — это, по сути, искусство составлять алгоритмы для компьютера.

Само слово пришло от имени средневекового математика аль-Хорезми, который описывал правила вычислений по шагам. Так что термину больше тысячи лет, а актуален он как никогда.

Исполнитель алгоритма

У любого алгоритма есть тот, кто его выполняет, — исполнитель. Рецепт блинов исполняет повар, инструкцию к шкафу — человек с отвёрткой, а программу — компьютер. Исполнителем может быть и человек, и робот, и машина.

Важно: каждый исполнитель умеет выполнять только определённый набор команд — его систему команд. Робот-пылесос понимает «вперёд», «поворот», «всосать пыль», но не поймёт «приготовь ужин». Если в алгоритме встретится команда не из системы команд исполнителя, он не сможет её выполнить.

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

Свойства алгоритма

Не всякое описание действий — алгоритм. Настоящий алгоритм обладает несколькими обязательными свойствами. Их стоит выучить — это любимый вопрос на проверочных.

Проверим на рецепте. «Жарь блин, пока не подрумянится» — точно? Не очень, ведь «подрумянится» каждый понимает по-своему. А вот «жарь блин 2 минуты с каждой стороны» — уже точно. Видишь разницу? Компьютер, в отличие от человека, не умеет догадываться, поэтому для него всё должно быть предельно точно.

Формальные исполнители: послушные, но «глупые»

Среди исполнителей особое место занимают формальные исполнители — те, кто выполняет команды строго и бездумно, не вникая в смысл. Робот-пылесос, светофор, банкомат, да и сам компьютер — всё это формальные исполнители. Они не догадываются, чего ты «на самом деле» хотел, а делают ровно то, что написано в командах. В этом и сила, и слабость. Сила — в надёжности: формальный исполнитель не устанет, не схитрит, не ошибётся «по невнимательности», он повторит алгоритм миллион раз одинаково. Слабость — в буквальности: если в алгоритме ошибка, исполнитель честно её выполнит и приведёт к неверному результату, даже не моргнув. Поэтому ответственность за правильность алгоритма целиком на том, кто его составил, — на тебе. Программисты шутят: «компьютер делает не то, что ты хочешь, а то, что ты написал». Эта мысль — ключ к пониманию всего программирования.

Когда описание — не алгоритм

Если нарушено хоть одно свойство, перед нами не алгоритм. Например, «иди вперёд, пока не надоест» нарушает точность (что значит «надоест»?). А инструкция, которая зацикливается и никогда не заканчивается, нарушает конечность. Хороший алгоритм всегда доводит дело до конца за разумное число шагов.

Попробуй сам

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

# Алгоритм: найти наибольшее из трёх чисел
a = 7
b = 15
c = 4

print("Шаг 1: считаем, что максимум — это a =", a)
maksimum = a

print("Шаг 2: сравниваем с b =", b)
if b > maksimum:
    maksimum = b

print("Шаг 3: сравниваем с c =", c)
if c > maksimum:
    maksimum = c

print("Результат: наибольшее число =", maksimum)

Вывод:

Шаг 1: считаем, что максимум — это a = 7
Шаг 2: сравниваем с b = 15
Шаг 3: сравниваем с c = 4
Результат: наибольшее число = 15

Поменяй числа a, b, c на любые другие — алгоритм всё равно найдёт наибольшее. Это свойство массовости: один алгоритм решает целый класс задач, а не один конкретный пример.

Один результат — разные алгоритмы

Важно понять ещё одну вещь: к одной и той же цели часто ведут разные алгоритмы. Чтобы попасть из дома в школу, можно пойти длинной дорогой через парк или короткой через двор — оба алгоритма приводят в школу, но один быстрее. То же и в программировании: одну задачу можно решить несколькими способами, и они отличаются по скорости, по количеству шагов, по понятности. Например, чтобы найти наибольшее из десяти чисел, можно сравнивать их по очереди (как в нашем примере), а можно сначала отсортировать список и взять последний элемент. Результат один, а путь разный. Искусство программиста как раз в том, чтобы выбрать хороший алгоритм — не просто работающий, а понятный и эффективный. Поэтому, решая задачу, всегда полезно спросить себя: а нет ли способа проще или быстрее?

Алгоритмы существовали задолго до компьютеров

Любопытно, что многие знаменитые алгоритмы придумали за тысячи лет до первого компьютера. Древнегреческий математик Евклид больше двух тысяч лет назад описал способ находить наибольший общий делитель двух чисел — этот «алгоритм Евклида» до сих пор работает в современных программах без единого изменения. Способ умножения столбиком, которому тебя учили в начальной школе, — тоже алгоритм: чёткая последовательность шагов, которая всегда приводит к ответу. И когда ты делишь уголком или решаешь уравнение по правилам — ты выполняешь алгоритм, просто исполнитель тут ты сам. Это важная мысль: алгоритм — не про компьютеры, а про порядок мышления. Компьютер лишь научился выполнять алгоритмы очень быстро и не уставая. Поэтому, учась составлять алгоритмы, ты тренируешь не «навык для машины», а собственное умение раскладывать любую задачу на ясные шаги — а это пригодится далеко за пределами информатики.

Частые ошибки

• Считать любую инструкцию алгоритмом. Если шаги неточные или дело не заканчивается — это ещё не алгоритм.
• Забывать про систему команд исполнителя. Алгоритм должен состоять только из понятных исполнителю команд.
• Путать массовость с одним примером. Хороший алгоритм работает для всех похожих задач, а не для одного набора чисел.

Запомни

• Алгоритм — точная последовательность шагов, ведущая к результату.
• Исполнитель выполняет алгоритм; он понимает только команды из своей системы команд.
• Свойства алгоритма: дискретность, точность, конечность, массовость, понятность.
• Если нарушено хоть одно свойство — это не алгоритм.