Разработка алгоритмов фокусируется на разработке, анализе, реализации, оптимизации, профилировании и экспериментальной оценке компьютерных алгоритмов , устраняя разрыв между теорией алгоритмов и практическим применением алгоритмов в разработке программного обеспечения . [1] Это общая методология алгоритмического исследования. [2]
Происхождение
В 1995 году в отчете организованного NSF семинара «с целью оценки текущих целей и направлений сообщества Теории вычислений (TOC)» отмечена медленная скорость принятия теоретических выводов практиками как важная проблема и предложены меры. к
- уменьшить неуверенность практикующих специалистов в том, приведет ли определенный теоретический прорыв к практическим достижениям в их области работы, и
- устранение недостатка готовых к использованию библиотек алгоритмов, которые обеспечивают стабильные, безошибочные и хорошо протестированные реализации алгоритмических проблем и предоставляют простой в использовании интерфейс для потребителей библиотеки. [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]
Рекомендации
- ^ a b «Разработка алгоритмов», Камил Деметреску, Ирен Финокки, Джузеппе Ф. Итальяно , веб-сайт: http://www.dis.uniroma1.it/~demetres/docs/ae.pdf
- ^ a b c d e f g «Разработка алгоритмов - попытка определения», Питер Сандерс , веб-сайт: http://algo2.iti.kit.edu/documents/definition.pdf
- ^ "Новые возможности теоретической информатики", Ахо, Джонсон, Карп, Косараджу, МакГеоч, Пападимитриу, веб-сайт: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160
- ^ Семинар по разработке алгоритмов
- ^ «К дисциплине экспериментальной алгоритмики», Бернард М. Э. Морет, Интернет: http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf
- ^ Разработка алгоритмов: 3-й международный семинар , Джеффри Скотт Виттер, Христос Д. Зарольягис, 1999, веб-сайт: BGoogle-sC .
- ^ a b «Семинар по разработке алгоритмов и экспериментам» (обзор), JHU.edu, 1999, веб-сайт: JHU-ALENEX99 .