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

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

Алгоритм это точная последовательность шагов, которая приводит к результату. Рецепт пирога, инструкция к шкафу из магазина, правило сложения в столбик: всё это алгоритмы. Важно, чтобы шаги были однозначными и их мог выполнить кто угодно, даже тот, кто не понимает смысла.

Слово происходит от имени персидского учёного IX века аль-Хорезми. Он написал книгу о том, как считать в десятичной системе, и в латинском переводе его имя превратилось в Algoritmi. От названия другой его книги произошло слово «алгебра».

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

Двоичный поиск: игра «угадай число»

Друг загадал число от 1 до 100. Вы называете число, он отвечает «больше» или «меньше». Как угадать быстрее всего?

Можно перебирать по порядку: 1, 2, 3… В худшем случае понадобится сто попыток. А можно каждый раз называть середину оставшегося промежутка: 50, потом 25 или 75, и так далее. Каждый ответ отбрасывает половину вариантов.

100 → 50 → 25 → 13 → 7 → 4 → 2 → 1

Хватит семи вопросов. Для чисел от 1 до 1000 хватит десяти, а от 1 до миллиона двадцати, потому что 2²⁰ чуть больше миллиона. Сто миллиардов потребуют всего 37 вопросов.

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

Сортировка: как разложить по порядку

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

Способ понятный, но медленный. Для n элементов нужно примерно n² сравнений. Для 30 человек это сотни сравнений, терпимо. Для миллиона чисел уже триллион.

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

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

Навигатор: кратчайший путь

Карта для навигатора это граф: перекрёстки служат вершинами, а дороги рёбрами, у каждого ребра своя длина или время проезда. Задача в том, чтобы найти путь с наименьшей суммой.

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

Современные навигаторы используют улучшенные версии этого алгоритма, учитывают пробки и заранее рассчитывают части маршрута между крупными узлами. Иначе построение пути через всю страну занимало бы слишком долго. Задачи на графы теперь есть и в ЕГЭ по информатике, об этом в статье о новом задании на графы.

Где ещё спрятаны алгоритмы

• Сжатие. Архиватор находит в файле повторы и записывает их коротко: вместо «ааааааа» хранит «7 раз а». Так работают и ZIP, и форматы картинок.
• Рекомендации. Лента видео подбирает ролики по тому, что смотрели люди с похожими вкусами. Подробнее в статье о ленте рекомендаций.
• Проверка ошибок. Последняя цифра номера банковской карты контрольная: по особому правилу она вычисляется из остальных, и опечатка в одной цифре сразу видна.
• Кубик Рубика. Доказано, что любую раскраску кубика можно собрать не больше чем за 20 поворотов. Для доказательства понадобились годы вычислений.

Задачи

Обратите внимание: во второй задаче мы делим не пополам, а на три части, потому что у весов три исхода. Это то же мышление, что в двоичном поиске, и оно отлично тренируется на олимпиадных задачах.

Частые вопросы