Алгоритмы, которые работают бесконечно

У каждого десятилетия свои увлекательные головоломки; и если в начале 1980-х годов бесспорное первое место среди математических развлечений занимал кубик Рубика, то «Тетрис» вызывает похожее чувство ностальгии по концу 80-х и началу 90-х годов.

У кубика Рубика и «Тетриса» есть кое-что общее: математический оттенок, базирующийся на стилизованных геометрических формах, — но пожалуй, различия между ними представляют еще больший интерес.

Эти отличительные признаки «Тетриса» напоминают аналогичные темы, про- явившиеся в недавних работах по анализу алгоритмов. Все чаще встречаются ситуации, в которых традиционные представления об алгоритмах — в начале выполнения алгоритм получает входные данные, выполняется за конечное количество шагов и выдает результат — уже неприменимы.

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

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

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