Подборка алгоритмов, которые правят миром
Однажды на Reddit засветился интересный пост, написанный Джорджем Дворским под названием «10 алгоритмов, которые правят миром» (статья на русском языке). В нём автор попытался объяснить важность алгоритмов в наши дни и составил список самых важных для современной жизни алгоритмов. Если вы изучали алгоритмы, первое, что может прийти вам на ум после прочтения того поста: «Автор вообще знает, что такое алгоритм?» — или, может быть: «Новостной канал Facebook — алгоритм?» — потому что если новостной канал Facebook является алгоритмом, то в конечном итоге мы можем почти всё классифицировать как алгоритм. Чтобы внести ясность, в этой статье будет дано определение алгоритму, и будет составлен список из 10 (или больше) алгоритмов, которые на самом деле правят нашим миром. Что такое алгоритм? Неофициально алгоритмом является любая корректно определённая вычислительная процедура, на вход которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующую входные данные в выходные. Томас Х. Кормен, Чарльз И. Лейзерсон (2009), Алгоритмы: построение и анализ, 3-е издание Проще говоря, алгоритм представляет собой последовательность шагов, которая позволяет решить определённую задачу (да, алгоритмы используются не только машинами, но и людьми). Алгоритм должен обладать тремя важными характеристиками, чтобы иметь право так называться: Он должен работать за конечное количество времени. Если ваш алгоритм не может разобраться с проблемой, для которой он был создан, за конечное количество времени, то он бесполезен. Он должен иметь чётко определённые инструкции. Каждый шаг алгоритма должен быть точно определён. Инструкции должны быть однозначны для каждого случая. Он должен быть пригодным к использованию. Алгоритм должен решать проблему, для решения которой он был написан. Должна быть возможность продемонстрировать его работу при наличии только карандаша и бумаги. Также важно отметить, что алгоритмы используются не только в информатике, но и в математике. По факту, самые ранние математические алгоритмы — разложение на простые множители и извлечение квадратного корня — использовались вавилонянами уже в 1600 г. до н. э. Таким образом, мы имеем проблему, связанную с упомянутой ранее записью, которая рассматривает алгоритмы как компьютерные сущности. Однако, если применить формальный смысл слова, то одним из претендентов в десятку лучших алгоритмов может стать любая арифметическая операция (сложение, вычитание, произведение и т. д.). Поэтому в этой статье мы будем говорить о компьютерных алгоритмах. Тогда остаётся вопрос: какие 10 (или больше) алгоритмов правят нашим миром?