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

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