Разработка алгоритмов - Algorithm engineering

Разработка алгоритмов фокусируется на разработке, анализе, реализации, оптимизации, профилировании и экспериментальной оценке компьютера алгоритмы, устраняя разрыв между теорией алгоритмов и практическим применением алгоритмов в программная инженерия.^[1]Это общая методология алгоритмического исследования.^[2]

Происхождение

В 1995 г. NSF -спонсируемый семинар «с целью оценки текущих целей и направлений сообщества Теории вычислений (ТОС)» определил медленную скорость принятия теоретических идей практиками как важную проблему и предложил меры по

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

Но также пренебрегли перспективными алгоритмическими подходами из-за трудностей математического анализа.^[2]

Термин «разработка алгоритмов» впервые был использован с определенной спецификой в 1997 году, когда был проведен первый семинар по разработке алгоритмов (WAE97), организованный Джузеппе Ф. Итальяно.^[4]

Отличие от теории алгоритмов

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

Таким образом, он может по-новому взглянуть на эффективность и производительность алгоритмов в тех случаях, когда

данный алгоритм менее поддается теоретическому анализу алгоритмов,
формальный анализ пессимистично предлагает границы, которые вряд ли появятся для входных данных, представляющих практический интерес,
алгоритм основан на тонкостях современных аппаратных архитектур, таких как локальность данных, прогнозирование ветвлений, задержки выполнения инструкций, задержки выполнения инструкций, которые модель машины, используемая в теории алгоритмов, не может уловить в требуемых деталях,
необходимо определить пересечение конкурирующих алгоритмов с разными постоянными затратами и асимптотическим поведением.^[1]^[5]

Методология

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

Реалистичные модели и реальные исходные данные

Хотя конкретные приложения выходят за рамки методологии разработки алгоритмов, они играют важную роль в формировании реалистичных моделей проблемы и лежащей в основе машины, а также предоставляют реальные входные данные и другие параметры проектирования для экспериментов.^[2]

Дизайн

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

Анализ

Некоторые проблемы можно решить с помощью эвристики и рандомизированных алгоритмов более простым и эффективным способом, чем с помощью детерминированных алгоритмов. К сожалению, это делает даже простые рандомизированные алгоритмы сложно анализировать, потому что есть тонкие зависимости, которые необходимо учитывать.^[2]

Выполнение

Огромные семантические пробелы между теоретическими выводами, сформулированными алгоритмами, языками программирования и оборудованием создают проблему для эффективных реализаций даже простых алгоритмов, поскольку мелкие детали реализации могут влиять на поведение выполнения. Единственный надежный способ сравнить несколько реализаций алгоритма - это потратить значительное количество времени на настройку и профилирование, выполнение этих алгоритмов на нескольких архитектурах и просмотр сгенерированного машинного кода.^[2]

Эксперименты

Видеть: Экспериментальная алгоритмика

Разработка приложений

Реализации алгоритмов, используемых для экспериментов, существенно отличаются от кода, используемого в приложениях. В то время как первый отдает приоритет быстрому прототипированию, производительности и инструментам для измерений во время экспериментов, второй требует тщательное тестирование, ремонтопригодность, простота и настройка для определенных классов входных данных.^[2]

Библиотеки алгоритмов

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

Конференции

Ежегодно организуются две основные конференции по разработке алгоритмов, а именно:

Симпозиум по экспериментальным алгоритмам (SEA), основанный в 1997 году (ранее известный как WEA).
Совещание SIAM по разработке алгоритмов и экспериментам (ALENEX), основанное в 1999 году.

Семинар 1997 года по разработке алгоритмов (WAE'97) проходил в Венеции (Италия) 11–13 сентября 1997 года. Третий международный семинар по разработке алгоритмов (WAE'99) прошел в Лондоне, Великобритания, в июле 1999 года.^[6]Первый семинар по разработке алгоритмов и экспериментированию (ALENEX99) прошел в Балтиморе, штат Мэриленд, 15–16 января 1999 г.^[7] Это было спонсировано DIMACS, то Центр дискретной математики и теоретической информатики (в Университет Рутгерса ), при дополнительной поддержке со стороны SIGACT, Специальная группа ACM по алгоритмам и теории вычислений и SIAM, Общество промышленной и прикладной математики.^[7]