Как научить себя работать с алгоритмами

Многие головоломки Car Talk представляют собой классические примеры того, о чем думают компьютерщики, когда учатся строить алгоритмы. Выше, Клик и Клак (Рэй и Том Маглиоцци) из Car Talk.

Lane Turner/The Boston Globe via Getty Images

Вы когда-нибудь бросались словом “алгоритм”, не понимая, что оно означает? Когда люди жалуются на алгоритм Facebook, алгоритм Netflix или алгоритм поиска Google, они не всегда понимают, что это такое, даже если понимают последствия. Но поскольку алгоритмы приобретают все большее значение в нашей жизни, очень важно, чтобы каждый имел базовое представление о том, что они собой представляют.

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

Основные элементы алгоритмов

Каждый алгоритм имеет входы и выходы. Выход – это то, что вы обычно видите, это результат работы алгоритма. Это может быть Google Maps, находящий ваш маршрут домой, TurboTax, рассчитывающий ваш возврат, или Netflix, рекомендующий сериал. У алгоритмов также есть входы. Входные данные могут быть простыми, например, число, или они могут быть гораздо больше, чем кажется. Например, алгоритм, который находит маршрут из точки А в точку Б, использует в качестве исходных данных те точки, которые вы ему предоставили, но он также использует целую базу данных о дорогах, маршрутах других водителей и т. д. Когда вы думаете о входных данных, учитывайте все, что может быть использовано для решения проблемы.

Получив входные данные, алгоритмы выполняют ряд действий для получения выходных данных. Большинство алгоритмов строятся на основе других простых процессов. Фактически, все сложные вещи, которые вы делаете на компьютере, могут быть сделаны маленькой машинкой, которая считывает единицы и нули с полоски бумаги, смотрит что-то в таблице и корректирует цифру. (Обычные процессы включают сортировку списков, поиск элементов в списках и выполнение некоторых математических манипуляций – все это поддерживает множество более сложных алгоритмов.

Общие алгоритмические задачи

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

Давайте рассмотрим несколько алгоритмов поиска. Допустим, я даю вам колоду карт. Она отсортирована сначала по достоинству карт (двойки, затем тройки, четверки и т.д.), а затем по масти. Таким образом, мы получим

Один из алгоритмов может начинаться спереди и проверять каждую карточку, чтобы узнать, наша ли это карточка. Если да, то мы закончили! Если нет, мы переходим к следующей карте. В худшем случае, если я попрошу туз пик, вам придется перебрать все 52 карты, чтобы найти его. В лучшем случае я говорю “двойка треф”, и вы сразу же находите ее. Если вы посчитаете это для всех возможных карт, которые я прошу, то в среднем вам придется перебрать примерно половину колоды, или 26 карт, прежде чем вы ее найдете.

Более эффективный алгоритм называется бинарным поиском. Поскольку наша колода отсортирована, давайте начнем с того, что разделим ее пополам и посмотрим на центральную карту (это 26-я карта). Проверьте, та ли это карта, которую мы ищем. Если да, то отлично! Если нет, определяем, где находится нужная нам карта – раньше или позже в колоде. Допустим, что раньше. Тогда мы выбрасываем всю более позднюю половину колоды. Берем переднюю половину колоды, делим ее пополам (до 13-й карты) и смотрим, наша ли это карта. Повторяем этот процесс, пока не найдем нужную нам карту. Каждый раз мы делим колоду пополам. Это означает, что нам потребуется не более шести сравнений, чтобы найти нашу карту – гораздо быстрее, чем в первом случае.

Простые алгоритмы поиска и сортировки, подобные этому, являются основными строительными блоками, которые используются для решения сложных задач. Например, один из способов поиска в Интернете (при условии, что у вас есть доступ к каждой веб-странице) – это поиск каждой страницы, на которой есть ваш термин. Затем проведите небольшое математическое вычисление, чтобы подсчитать, насколько хорошо они соответствуют поисковому запросу. Затем отсортировать страницы по этому показателю и вернуть их в порядке от лучшего к худшему.

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

Эти проблемы называются NP-полными. Мы пропустим здесь формальное определение, но в основном это проблемы, в которых для нахождения наилучшего ответа необходимо проверить множество комбинаций. Например, есть одна NP-полная проблема, которая называется “Проблема ранца”. Я даю вам ранец, который может выдержать заданный вес (скажем, 20 фунтов). Затем я даю вам кучу предметов. Каждый из них имеет вес и ценность. Вы хотите уместить в рюкзаке наиболее ценную комбинацию предметов, но не превысить его вес. Какую коллекцию предметов вы выберете?

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

NP-полные задачи трудны (как мы думаем). Насколько трудны? Если я дам вам 100 городов в задаче о коммивояжере, то на ее решение уйдет больше времени, чем известный возраст Вселенной. Быстрый алгоритм может существовать, но мы, компьютерщики, считаем, что его, скорее всего, нет (подробнее об этом можно узнать из статьи “Проблема P vs. NP”). Более интересно то, что если у нас есть быстрый алгоритм для любой из этих задач, то этот алгоритм решит все эти задачи. Если вы придумаете быстрый способ решения задачи о ранце, вы сможете напрямую применить этот алгоритм к задаче о коммивояжере и наоборот. (Хотите доказательство? Посмотрите эти слайды). Распознавание того, что выглядит как NP-полная проблема, – важный шаг на пути к алгоритмической грамотности.

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

Они также знают, какие песни слушали и любили другие люди. Если это часть входных данных, алгоритм может найти самые популярные песни среди людей со вкусами, похожими на мои. Для этого нужно просмотреть все свои записи, чтобы найти информацию о том, кто что слушал, оценить мое сходство с этими людьми, затем оценить песни и отсортировать список песен по количеству баллов. Алгоритм может даже объединить информацию о предпочтениях других людей с информацией об исполнителе и жанре, чтобы получить оценку. Эти исходные данные влияют на результат работы алгоритма. Иногда люди говорят об алгоритмической предвзятости – это то, что может начаться с предвзятых входных данных. В данном случае это могут быть некачественные жанровые метки или набор пользователей с необычными привычками прослушивания.

Главное здесь – не выяснить, как именно работает алгоритм, а понять, что он может использовать в качестве входных данных, какие операции он может выполнять с этими данными и как он может генерировать выходные данные.

Создание собственного алгоритма

Наконец, попробуйте создать свой собственный алгоритм. Это хороший способ развить грамотность, так же как чтение – хороший способ стать лучшим писателем.

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

Если вы слушаете “Car Talk Puzzler”, то многие из них – это классические примеры, о которых мы, компьютерщики, думаем, когда учимся строить алгоритмы. Давайте рассмотрим одну из таких головоломок:

Мы собираемся сыграть в небольшую карточную игру. Я собираюсь разложить 21 карту из обычной колоды карт в стопку перед нами. Мы будем поочередно брать карты из кучи.

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

Например, если осталось шесть карт, и я беру три, вы возьмете последние три, потому что мы чередуемся, и вы выиграете. Итак, очевидно, что если бы осталось шесть карт, я бы не стал брать три.

Эта головоломка просит вас построить алгоритм для игры. Начните с рассмотрения основных случаев, а затем ищите закономерности. Здесь мы знаем, что я выиграю, если на столе будет одна, две или три карты, поскольку я могу взять их все. Я проиграю, если

Таким образом, это говорит нам о том, что это выигрышное предложение, если на столе одна, две или три карты, и проигрышное, если их четыре. Мы можем использовать это для построения схемы. Если я могу поставить своего противника в проигрышное положение (например, заставить его увидеть четыре карты), то я знаю, что выиграю. Я могу сделать это, если карт пять (взяв одну), шесть (взяв две) или семь (взяв три). Если карт восемь, то я ничего не могу сделать, чтобы мой противник увидел четыре карты, поэтому я проиграю (если только мой противник не ошибется).

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

Исходными данными здесь является количество карт на столе. Ваш алгоритм рассчитает, сколько карт нужно взять, чтобы общее количество карт было кратно четырем, а затем сделает этот ход. Соперник делает ход, а затем ваш алгоритм повторяет процесс.

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

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

Разговор о машинах