Алгоритмическая инженерия
Алгоритмическая инженерия фокусируется на проектировании, анализе, реализации, оптимизации, профилировании и экспериментальной оценке компьютерных алгоритмов , устраняя разрыв между теорией алгоритмики и практическим применением алгоритмов в разработке программного обеспечения . [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]
Ссылки [ править ]
- ^ Jump up to: а б «Алгоритмическая инженерия», Камиль Деметреску, Ирен Финокки, Джузеппе Ф. Итальяно , веб-сайт: http://www.dis.uniroma1.it/~demetres/docs/ae.pdf
- ^ Jump up to: а б с д и ж г «Алгоритмическая инженерия – попытка определения», Питер Сандерс , веб-сайт: http://algo2.iti.kit.edu/documents/definition.pdf
- ^ «Новые возможности для теоретической информатики», Ахо, Джонсон, Карп, Косараджу, МакГеоч, Пападимитриу, веб-сайт: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160
- ^ «Практикум по алгоритмической инженерии» . Архивировано из оригинала 27 сентября 2018 г. Проверено 14 сентября 2009 г.
- ^ «К дисциплине экспериментальной алгоритмики», Бернар М.Е. Море, веб-сайт: http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf
- ^ Разработка алгоритмов: 3-й международный семинар , Джеффри Скотт Виттер, Христос Д. Зарольягис, 1999 г., веб-сайт: BGoogle-SC .
- ^ Jump up to: а б «Практикум по алгоритмической разработке и экспериментам» (обзор), JHU.edu, 1999, веб-сайт: JHU-ALENEX99 .