Войти
Разработка алгоритмов фокусируется на разработке, анализе, реализации, оптимизации, профилировании и экспериментальной оценке компьютерных алгоритмов, преодолевая разрыв между теорией алгоритмов и практическим применением алгоритмов в программной инженерии. Это общая методология алгоритмических исследований.
В 1995 г. 27>Семинар, спонсируемый NSF, «с целью оценки текущих целей и направлений сообщества Теории вычислений (TOC)» определил медленную скорость принятия теоретических выводов практиками как важную проблему и предложил меры по
Но также и многообещающие алгоритмические подходы игнорировались из-за трудностей математического анализа.
Термин «разработка алгоритмов» впервые был использован со специфичностью в 1997 году, когда был проведен первый семинар по разработке алгоритмов (WAE97), организованный Джузеппе Ф. Итальяно.
Разработка алгоритмов не намерена заменять теорию алгоритмов или конкурировать с ними, но пытается обогатить, усовершенствовать и усилить свои формальные подходы с помощью экспериментальная алгоритмика (также называемая эмпирической алгоритмикой).
Таким образом, он может по-новому взглянуть на эффективность и производительность алгоритмов в тех случаях, когда
Некоторые исследователи описывают методологию разработки алгоритмов как цикл, состоящий из алгоритмов проектирование, анализ, реализация и экспериментальная оценка, а также дополнительные аспекты, такие как модели машин или реалистичные исходные данные. Они утверждают, что отождествление разработки алгоритмов с экспериментальной алгоритмикой слишком ограничено, потому что рассмотрение проектирования и анализа, реализации и экспериментов как отдельных действий игнорирует критически важный цикл обратной связи между этими элементами разработки алгоритмов.
Хотя конкретные приложения выходят за рамки методологии разработки алгоритмов, они играют важную роль в формировании реалистичных моделей проблемы и лежащей в основе машины, а также предоставляют реальные входные данные и другие проектные параметры для экспериментов.
По сравнению с теорией алгоритмов, которая обычно фокусируется на асимптотическом поведении алгоритмов, разработчики алгоритмов должны учитывать следующие требования: простота алгоритма, возможность реализации в языках программирования на реальном оборудовании, и разрешение повторного использования кода. Кроме того, постоянные коэффициенты алгоритмов оказывают такое значительное влияние на реальные входные данные, что иногда алгоритм с худшим асимптотическим поведением работает лучше на практике из-за более низких постоянных коэффициентов.
Некоторые проблемы могут быть решены с помощью эвристики и рандомизированных алгоритмов более простым и эффективным способом, чем с помощью детерминированных алгоритмов. К сожалению, это затрудняет анализ даже простых рандомизированных алгоритмов, потому что необходимо учитывать тонкие зависимости.
Огромные семантические пробелы между теоретическими выводами, сформулированными алгоритмами, языками программирования и аппаратным обеспечением. проблема для эффективных реализаций даже простых алгоритмов, потому что мелкие детали реализации могут повлиять на поведение выполнения. Единственный надежный способ сравнить несколько реализаций алгоритма - это потратить значительное количество времени на настройку и профилирование, выполнение этих алгоритмов на нескольких архитектурах и просмотр сгенерированного машинного кода.
См.: Экспериментальная алгоритмика
Реализации алгоритмов, используемых для экспериментов, существенно отличаются от кода, используемого в приложениях. В то время как в первом случае приоритет отдается быстрому созданию прототипов, производительности и инструментарию для измерений во время экспериментов, для второго требуется тщательное тестирование, ремонтопригодность, простота и настройка для определенных классов входных данных.
Стабильно, хорошо Библиотеки протестированных алгоритмов, такие как LEDA, играют важную роль в передаче технологий, ускоряя внедрение новых алгоритмов в приложениях. Такие библиотеки снижают требуемые инвестиции и риски для практиков, поскольку снимают бремя понимания и применения результатов академических исследований.
Ежегодно организуются две основные конференции по разработке алгоритмов, а именно:
Семинар 1997 г. по разработке алгоритмов (WAE'97) проходил в Венеции (Италия) 11–13 сентября 1997 г. Третий международный семинар по разработке алгоритмов (WAE'99) был проведен в Лондоне, Великобритания, в июле 1999 года. Первый семинар по разработке алгоритмов и экспериментированию (ALENEX99) был проведен в Балтиморе, штат Мэриленд, 15–16 января 1999 года. Он был спонсирован DIMACS, Центр дискретной математики и теоретической информатики (в Университете Рутгерса ), при дополнительной поддержке SIGACT, Специальной группы ACM по Теория алгоритмов и вычислений и SIAM, Общество промышленной и прикладной математики.
