Что такое алгоритм

Если ты уверенно отличаешь алгоритм от инструкции, которая только похожа на него, листай до «Теперь сам» в конце.

Как думаешь, что из этого алгоритм

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

1. «Разбей два яйца, добавь молока, посоли по вкусу, жарь до готовности».
2. «Даны два целых положительных числа. Пока они не равны, вычитай меньшее из большего. Когда станут равны, ответ - любое из них».
3. «Даны два целых положительных числа. Перебирай все числа подряд, пока не найдёшь то, на которое делятся оба».
4. «Дано целое число x. Пока x не равно нулю, вычитай из него 2».

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

На что это похоже

Представь, что диктуешь по телефону, как собрать шкаф, человеку, который шкафа никогда не видел. Он не переспрашивает и не додумывает: делает ровно то, что сказано, и только то, что умеет. «Прикрути полку где-нибудь посередине» он не выполнит - «где-нибудь» не команда. «Крути, пока не станет плотно» он выполнит, но если резьба сорвана, будет крутить, пока не отвалятся руки.

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

Механизм: исполнитель, команды и четыре свойства

Алгоритм всегда пишут ДЛЯ кого-то. Этот кто-то называется исполнителем.

Исполнитель - тот, кто выполняет алгоритм: человек, робот, процессор, программа. У него есть система команд - набор действий, которые он умеет делать без объяснений. Для процессора это сложение и пересылка чисел. Программу на Python выполняет не сам язык, а программа, которая его понимает, - чаще всего CPython, её запускает команда python3. Язык задаёт правила записи, CPython по ним работает, и в его систему команд входят присваивание, арифметика, if, while, for и вызовы функций.

Всё, что не входит в систему команд, приходится расписывать через то, что входит. Отдельного оператора «найди среднее» в Python нет, значит, среднее раскладывается на три действия, которые есть: сложить числа, посчитать, сколько их, и разделить. В квадратных скобках - список чисел, его можно заменить на любой свой; for x in chisla берёт числа из списка по одному:

chisla = [4, 8, 15, 16, 23, 42]
summa = 0
kolichestvo = 0
for x in chisla:
    summa = summa + x
    kolichestvo = kolichestvo + 1
print(summa / kolichestvo)

18.0

Сумма 108, чисел шесть. Деление / в Python всегда даёт дробное число, даже когда делится нацело, поэтому на экране 18.0, а не 18.

В стандартной библиотеке есть готовая statistics.mean, но это не команда языка, а функция, которую кто-то уже расписал через те же сложения и деление. Пока пишешь алгоритм, считай, что её нет: иначе непонятно, что именно ты придумал сам.

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

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

Слово «допустимом» в строке про конечность важно. Алгоритм, решающий задачу, обязан останавливаться не на тех входах, на которых его пробовали, а на всех, которые разрешены. Какие входы разрешены, записывают отдельно - об этом глава «Задача и модель стоимости».

Правило

Алгоритм - конечное описание однозначно определённых действий и правил их выполнения, понятное заданному исполнителю. Алгоритм решает задачу, если на каждом допустимом входе завершается за конечное число шагов и выдаёт результат, который удовлетворяет требованию задачи.

Требование задачи - какие входы допустимы и какой ответ на каждом считается верным - называется спецификациейРазбирается в разделе 1, глава «Задача и модель стоимости»: Задача - это вход и требование к выходу, и её разбирает та же глава «Задача и модель стоимости». Инструкция, в которой хоть один шаг требует от исполнителя догадки, недостаточно определена и алгоритмом не является. Алгоритм, который хоть на одном допустимом входе не останавливается или отвечает неверно, задачу не решает.

Теория вычислений рассматривает и процедуры, которые на части входов не останавливаются: без них не обойтись, потому что не существует общего способа, который для любой программы и любого входа заранее скажет, остановится ли она, - это проблема остановаРазбирается в разделе 21, глава «Проблема останова и неразрешимые задачи»: Проблема останова: вопрос, на который не отвечает ни одна программа. Для многих конкретных программ ответ при этом известен: про Евклида ниже его докажем. В этом курсе «алгоритм решает задачу» всегда значит оба требования сразу: остановку и верный ответ.

Разбор: вычитание меньшего из большего

Вторая инструкция из начала урока - алгоритм Евклида в самой старой форме. Он находит наибольший общий делитель - самое большое число, на которое оба числа делятся без остатка. Проверим все четыре свойства.

Дискретность: шаги - «сравни числа» и «вычти меньшее из большего», и они повторяются. Определённость: при неравных числах ясно, какое меньшее, при равных цикл кончается, третьего не бывает. Массовость: подходит любая пара целых положительных чисел. Конечность - самое интересное. Каждое вычитание уменьшает большее число хотя бы на единицу, а оба числа остаются положительными: из большего вычитается меньшее, которое строго меньше. Сумма двух положительных целых не может уменьшаться бесконечно, значит, цикл кончится.

Вот тот же алгоритм на Python и его работа на паре 84 и 36. Тело цикла и ветки if - это строки с отступом после двоеточия, != значит «не равно». Чтобы повторить запуск, сохрани текст в файл evklid.py и выполни python3 evklid.py в том же каталоге (есть ли Python 3, покажет python3 --version); блок под программой - то, что она напечатает:

a = 84
b = 36
shag = 0
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
    shag = shag + 1
    print(shag, a, b)
print("НОД =", a)

1 48 36
2 12 36
3 12 24
4 12 12
НОД = 12

Остановка - только половина дела, вторая половина - верность ответа. Здесь её держит одно наблюдение: общие делители пары не меняются ни на одном шаге. Число, которое делит оба числа, делит и их разность, значит, старые общие делители остаются в новой паре. И наоборот: число, которое делит разность и меньшее, делит и их сумму, то есть прежнее большее, - значит, новых общих делителей не появляется. Почему отсюда следует верный ответ, разберёт глава про правильностьРазбирается в разделе 1, глава «Правильность и инвариант цикла»: Что значит «алгоритм верен». Здесь важнее другое: все четыре свойства проверены рассуждением, а не запуском.

Разбор: остановилась - ещё не значит решила

Возьмём инструкцию, которой в начале урока не было: «Даны два целых положительных числа. Ответ - меньшее из них». Задача та же - наибольший общий делитель.

Каждый шаг однозначен, шаг всего один, остановка на любой паре мгновенная, подходит любая пара. По всем свойствам из таблицы это алгоритм, и он завершается на каждом допустимом входе. На паре (12, 36) он отвечает 12, на (7, 7) - 7, и оба ответа верны. На паре (84, 36) он отвечает 36, а 84 на 36 не делится: 84 = 2 · 36 + 12. Это вообще не общий делитель, не то что наибольший.

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

Разбор: три инструкции, которые только похожи

Первая - рецепт омлета. «По вкусу» и «до готовности» - не команды для исполнителя без вкуса и без опыта: он не знает, сколько соли и когда снимать сковороду. Но определённость меряется относительно исполнителя. Для опытного повара «до готовности» - привычное действие из его системы команд, и для него рецепт однозначен. Для робота-новичка - нет. Поэтому вопрос «алгоритм ли это» без вопроса «для кого» не имеет ответа.

Третья не говорит, откуда начинать перебор и в какую сторону идти. Начни с единицы и иди вверх - остановишься сразу на единице. И это честный ответ: инструкция просит число, на которое делятся оба, а на единицу делится любое целое. Бесполезным он становится, только если на самом деле нужен наибольший общий делитель, а этого в тексте инструкции нет - это дефект требования, а не перебора. Начни с большего из чисел и иди вверх - и при неравных числах не остановишься никогда: общий делитель не больше меньшего из чисел, а перебор уходит вверх без конца.

Неопределённость сама по себе бесконечности не создаёт: это два независимых свойства. Неоднозначная инструкция допускает несколько прочтений, и здесь среди них нашлось незавершающееся. Бывает и наоборот: четвёртая инструкция однозначна, а остановку ломает.

Четвёртая - алгоритм: каждый шаг понятен без догадок. Но задачу на входах «любое целое число» он не решает. На чётном неотрицательном x он дойдёт до нуля, а на x = -2 уйдёт вниз: -4, -6 и дальше. На x = 7 он пройдёт 5, 3, 1, -1, -3 и дальше вниз без конца: ноль он перепрыгнул. Запусти его на десятке чётных чисел - работает. Удачные примеры дефекта не находят. Его находит либо неудобный пример вроде x = 7, если догадаешься его взять, либо рассуждение «а что будет на нечётном», и только рассуждение охватывает все входы сразу.

Что ломается без этого

Нарушенная конечность в программе выглядит как операция, которая должна была закончиться и не закончилась: клиент ждёт ответа, пока не сдастся по таймауту, а обработчик на сервере крутится и после этого; ночной скрипт пересчёта отчётов не заканчивается к утру. Нагрузка процессора тут не признак. Цикл, который считает, занимает ядро целиком, а цикл «поспи секунду и проверь, не появился ли файл» на файле, который не появится никогда, висит почти без нагрузки. И бесконечная работа сама по себе не дефект: nginx и база крутят свой главный цикл, пока их не остановят, - так задумано. Конечным обязан быть каждый кусок работы, от которого ждут результата: обработка одного запроса, одна миграция.

Нарушенная определённость выглядит как «у меня работает»: поведение зависит от того, о чём описание молчит: какое из равных значений выбрать, в каком часовом поясе считать «сегодня». Каждый автор кода дописал недостающее по-своему, и на одних данных программы расходятся. Неверный ответ при честной остановке - самый тихий дефект: программа быстро и без единой ошибки в журнале отвечает не то. Все три находятся вопросом «а на каком допустимом входе это не так».

Зачем это в работе

Инструкция дежурному «если nginx упал, разберись и подними» - не алгоритм: «разберись» у каждого своё, и ночью разные люди сделают разное. Вот та же инструкция, которую дежурный выполнит без догадок, на случай «мониторинг сообщил, что служба nginx остановилась». Служба - программа, которую система держит запущенной в фоне; systemctl - команда, которой в Linux управляют службами, а nginx -t проверяет файлы настроек nginx, ничего не перезапуская. sudo выполняет команду с правами администратора и может спросить пароль твоей учётной записи. Система команд дежурного - «выполни команду в терминале и прочитай вывод», а допустимый вход оговорён заранее: он зашёл на сервер с nginx под учётной записью, которой разрешён sudo.

1. Выполни systemctl is-active nginx. Если напечатано active, службу уже подняли: запиши «nginx работает» и закончи, иначе переходи к пункту 2.
2. Выполни sudo nginx -t. Если в выводе нет слов test is successful, позвони владельцу и закончи, иначе переходи к пункту 3.
3. Выполни sudo systemctl restart nginx, затем снова systemctl is-active nginx. Если напечатано active, запиши «поднят перезапуском» и закончи, иначе позвони владельцу и закончи.

Каждая проверка называет точную команду и точные слова в выводе, у каждого «если» есть «иначе», и любой путь по пунктам кончается словом «закончи». Ровно эту работу ты делаешь, когда пишешь скрипт деплоя, разбираешь задачу на собеседовании или объясняешь коллеге, как воспроизвести ошибку.

Теперь сам

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