VII Международная студенческая научная конференция Студенческий научный форум - 2015

В основе любого процесса проектирования и моделирования лежит математический аппарат, который в настоящее время включает в себя широкий спектр методов для решения любой задачи.

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

Перед специалистами в области моделирования рано или поздно встает вопрос, какой алгоритм или метод использовать для выполнения необходимых расчетов – более быстрый или более медленный, но требующий меньших ресурсов компьютера, более требовательный к известным начальным условиям или абсолютно неприхотливый.

Для ответов на эти вопросы можно пользоваться личными предпочтениями и опытом предыдущей работы, а можно произвести сравнительный анализ эффективности алгоритмов.

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

• метод перебора с постоянным шагом;

• метод дихотомии;

• метод золотого сечения.

Для сравнения алгоритмов разработана программа, имеющая интерфейс, показанный на рис. 1. Он состоит из двух частей:

1. панель, предназначенная для ввода необходимых параметров (границы интервала неопределенности – промежуток, на котором находится предполагаемый экстремум, степень точности, число «замеров» для метода перебора и т.д.);

2. панель, предназначенная для вывода параметров алгоритмов: степень приближения к экстремуму, число итераций, график, иллюстрирующий зависимость близости к экстремуму от номера итерации.

Рис. 1. Главное окно программы

Диаграмма поведения разработанной программы показана на рис. 2.

Рис. 2. Диаграмма поведения программы

Проанализируем влияние начальных условий на эффективность следующих алгоритмов нахождения экстремума функции.

Основными параметрами сравнения в нашем случае являются время выполнения алгоритма и количество шагов, затрачиваемых на вычисление (счетчик). Остановимся поподробнее на первом пункте – времени выполнения алгоритма.

Он реализован с помощью ассемблерной вставки, запоминающей номер текущего такта процессора. Для того чтобы с высокой степенью точности вычислить время работы в данной программе используется ассемблерная инструкция rdtsc, читающая счётчик TSC (Time Stamp Counter) и возвращающая в регистрах EDX:EAX 64-битное количества тактов с момента последнего сброса процессора. Именно этот способ позволяет вычислить с точностью практически до тика время выполнения алгоритма.

Оценим, как влияет увеличение диапазона неопределенности на исследуемые параметры. Меньше всего это сказалось на способе последовательного перебора, т.к. фактически расстояние от начала поиска до искомого значения не изменилось. Сравнительные показатели данных методов приведены в таблице 1.

Таблица 1. Сравнительные показатели зависимости от длины диапазона

Увеличим точность вычислений, оставив длину диапазона равной 10. В методах дихотомии и золотого сечения длительность измерений изменяется, хотя и незначительно. Разрыв в случае нескольких запусков не столь заметен, как в случае с методом перебора (таблица 2).

Таблица 2. Сравнительные показатели зависимости от точности вычислений

Этот дефект метода перебора можно преодолеть, задавая конкретное число шагов перебора. Однако заметим, что в этом случае точность и длительность вычислений будет напрямую зависеть от введенного параметра: увеличивая количество шагов можно всё больше приближаться к искомому значению.

Анализируя полученные данные, можно сформулировать следующие выводы:

1. Метод золотого сечения, являющийся частным случаем метода дихотомии, более ресурсоемкий;

2. Метод прямого перебора, несмотря на кажущуюся нерациональность, в отдельных случаях более экономичен по времени выполнения и числу итераций.

В результате можно сделать вывод, что для решения каждой задачи имеет смысл рассматривать не один вариант решения, а несколько и, анализируя решение, выбирать оптимальный из них.

Код для цитирования: Скопировать