Разработка алгоритмов
-
Определение и методология разработки алгоритмов
- Разработка алгоритмов включает в себя разработку, анализ, оптимизацию, профилирование и экспериментальную оценку алгоритмов.
- Она направлена на устранение разрыва между теорией и практикой в области алгоритмики.
-
Истоки и проблемы
- В 1995 году была отмечена низкая скорость внедрения теоретических идей в практику.
- Проблемы включали неуверенность практиков в применимости теоретических прорывов и нехватку готовых библиотек алгоритмов.
-
Терминология и отличие от теории алгоритмов
- Разработка алгоритмов не заменяет теорию, но стремится обогатить её экспериментальной алгоритмикой.
- Она позволяет получить новое представление о быстродействии алгоритмов, которые трудно анализировать теоретически.
-
Методология разработки алгоритмов
- Разработка алгоритмов включает разработку, анализ, реализацию и экспериментальную оценку, а также может включать дополнительные аспекты, такие как машинные модели и реалистичные исходные данные.
- Важна обратная связь между этими элементами разработки алгоритмов.
-
Роль реалистичных моделей и реальных исходных данных
- Реальные приложения и данные играют важную роль в формировании моделей и проведении экспериментов.
-
Дизайн алгоритмов
- Разработчики алгоритмов должны учитывать простоту, реализацию на реальном оборудовании и возможность повторного использования кода.
- Постоянные коэффициенты могут влиять на эффективность алгоритмов в реальных условиях.
-
Анализ алгоритмов
- Эвристические и рандомизированные алгоритмы могут быть более эффективными, но их анализ затруднён.
-
Реализация алгоритмов
- Реализация алгоритмов на практике может быть сложной из-за семантических разрывов между теоретическими представлениями и реальным кодом.
-
Эксперименты и библиотеки алгоритмов
- Эксперименты важны для проверки эффективности алгоритмов, но их результаты могут отличаться от приложений.
- Стабильные библиотеки алгоритмов, такие как LEDA, ускоряют внедрение новых алгоритмов и снижают риски для практиков.
-
Конференции по разработке алгоритмов
- Проводятся две основные конференции: SEA и ALENEX.
- Первая конференция WAE’97 прошла в Венеции, а WAE’99 — в Лондоне.
- ALENEX99 прошла в Балтиморе и была спонсирована различными организациями.