Тема: Эмпирический анализ трудоемкости алгоритма и средств программной реализации

Актуальность темы исследования обусловлена тем, что существует огромное количество различных компьютерных алгоритмов, в том числе и для решения одной и той же задачи, для которой необходимо проводить анализ их эффективности с последующим выбором наиболее подходящего алгоритма в той или иной области применения. На вход алгоритм может принимать раз-личные наборы данных и разные реализации могут хорошо и быстро работать с одними наборами, но очень плохо с другими. Проведение оценки эффективности позволяет определить, что именно будет работать лучше в конкретных условиях.
Целью работы является построение доверительных интервалов оцениваемой величины трудоемкости компьютерного алгоритма с заданной доверительной вероятностью.
 

Купить

Таким образом, в работе проведен эмпирический анализ алгоритма триангуляции Делоне, разработанного по методу “Разделяй и властвуй” с программной реализацией в библиотеке Triangle.NET [6], которая является портом программного обеспечения Triangle[7]. При этом эмпирический анализ проводился по методике, нацеленной на получение доверительной трудоемкости, которая позволяет значительно сузить оцениваемый сегмент варьирования трудоемкости. В качестве иллюстративного примера рассмотрено также применение данной методики к алгоритму пузырьковой сортировки.
В процессе выполнения предварительного этапа исследования с проверкой гипотезы о законе распределения значений трудоемкости алгоритма как дискретной ограниченной случайной величины была построена гистограмма относительных частот, которые наблюдаются в вычислительном эксперименте, и визуально оценен характер распределения. Гипотеза о возможности аппроксимации бета-распределением подтвердилась.
После выполнения основного этапа получено значительное отличие трудоёмкости в худшем случае и доверительной трудоёмкости, которая с коэффициентом доверия 95% не будет превышена.

Купить