Аноним

Экспериментальные методы анализа алгоритмов: различия между версиями

Материал из WEGA
(Новая страница: «== Ключевые слова и синонимы == Экспериментальная алгоритмистика; [[эмпирические алгори…»)
 
 
(не показана 1 промежуточная версия 1 участника)
Строка 24: Строка 24:


== Применение ==
== Применение ==
Экспериментальный анализ алгоритмов используется для изучения исследовательских задач, имеющих корни в теории вычислительных систем. К примеру, они могут возникать при анализе алгоритмов для среднего случая в одномерной задаче об упаковке контейнеров. Результатами экспериментального анализа являются открытие новых теорем об эффективности оптимального алгоритма; получение новых асимптотических границ на эффективность алгоритмов аппроксимации для среднего случая; расширение теоретических результатов на новые модели входных данных; а также создание новых алгоритмов с более строгими гарантиями аппроксимации. Еще одним примером может служить экспериментальное обнаружение типа поведения при фазовом переходе для случайных экземпляров задачи выполнимости 3КНФ-формул, которое привело к нахождению новых способов характеризации сложности экземпляров задачи.
Экспериментальный анализ алгоритмов используется для изучения исследовательских задач, имеющих корни в теории вычислительных систем. К примеру, они могут возникать при анализе алгоритмов для среднего случая в одномерной задаче об упаковке контейнеров. Результатами экспериментального анализа являются открытие новых теорем об эффективности оптимального алгоритма; получение новых асимптотических границ на эффективность аппроксимационных алгоритмов для среднего случая; расширение теоретических результатов на новые модели входных данных; а также создание новых алгоритмов с более строгими гарантиями аппроксимации. Еще одним примером может служить экспериментальное обнаружение типа поведения при фазовом переходе для случайных экземпляров задачи выполнимости 3КНФ-формул, которое привело к нахождению новых способов характеризации сложности экземпляров задачи.
   
   


Строка 59: Строка 59:


8. WEA. Beginning in 2001, the annual Workshop on Experimental and Efficient Algorithms is sponsored by EATCS. Workshop proceedings are published in the Springer LNCS series
8. WEA. Beginning in 2001, the annual Workshop on Experimental and Efficient Algorithms is sponsored by EATCS. Workshop proceedings are published in the Springer LNCS series
[[Категория: Совместное определение связанных терминов]]