Об одном методе уточнения оценки сложности алгоритма (на примере алгоритма умножения в кольце многочленов)

Вид материала

Документы

Подобный материал:

• Урок Тема: Понятие алгоритма. Исполнитель алгоритма, 204.38kb.
• Понятие алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Черча., 17.86kb.
• Рабочая программа дисциплины: Теория алгоритмов для специальности 050202 «Информатика», 196.64kb.
• План урока Организационный момент(1 мин) Проверка материала прошлого урока(10 мин.), 53.54kb.
• Применение модифицированного волнового алгоритма для сжатия потокового видеосигнала, 33.24kb.
• Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
• Удк 004. 056. 53 Некоторые особенности реализации алгоритма защиты программного обеспечения, 54.51kb.
• Теоретические вопросы, 25.48kb.
• План урока Организационный момент (2 минуты). Актуализация знаний (5 минут). Изучение, 36.57kb.
• Контрольная работа «алгоритмы и исполнители» вариант 1 Закончите предложение: «Алгоритмом, 27.49kb.

С.Ю. ЖЕБЕТ

Научный руководитель – А.Б. ФРОЛОВ, д.т.н., профессор
Московский энергетический институт (технический университет)


ОБ ОДНОМ МЕТОДЕ УТОЧНЕНИЯ ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМА (НА ПРИМЕРЕ АЛГОРИТМА УМНОЖЕНИЯ В КОЛЬЦЕ МНОГОЧЛЕНОВ)


Часто возникает необходимость выбора оптимального алгоритма из набора алгоритмов определенного класса при известных ограничениях на размер исходных данных решаемой задачи. Асимптотические оценки позволяют сравнивать различные методы решения, но не дают однозначного критерия выбора наилучшего, в условиях поставленной задачи, алгоритма. Измерение времени выполнения дает результаты только для алгоритмов и параметров, при которых оно производилось, эти результаты не могут быть непосредственно использованы для определения наилучшего алгоритма, который не был реализован в условиях поставленной задачи. К тому же временная оценка сильно зависит от операционной системы, частоты процессора объема памяти и других параметров среды выполнения программы, а потому далека от теории.

Предлагается способ получения оценки сложности алгоритмов через оценку количества элементарных операций, на примере комбинированного алгоритма умножения в кольце многочленов, описанного в [1], с использованием идеи перехода к схемной реализации, изложенной в [2].

В получаемой описанным в [2,3] методом схеме умножения, можно выделить набор типовых операций.

1. Операция присваивания.
   
2. Операция сложения по модулю 2.
   
3. Операция наложения маски (логическое «И»).
   
4. Операция битового сдвига.
   
5. Операция адресации элемента в массиве.
   

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

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

,

где n₁, n₂ – параметры алгоритма, причем n=n₁n₂ – разрядность многочленов операндов, а С₁,…,С₅ – некоторые постоянные. Таким образом, задача получения оценки сводится к задаче определения постоянных С₁,…,С₅. Для чего необходимо произвести 5 построений схемы и решить систему линейных уравнений относительно С₁,…,С₅.

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



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


Список литературы

1. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы / А.А. Болотов, С.Б. Гашков, А.Б. Фролов, А.А. Часовских. М.: КомКнига, 2006.
   
2. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Программные и схемные методы умножения многочленов для эллиптической криптографии. // Известия Академии Наук: Теория и системы управления. 2000. № 5. С. 57-66.
   
3. Жебет С.Ю. Построение и анализ декомпозиционных схем по методу Карацубы // Науч. сессия МИФИ-2006: XIII всероссийская научная конференция «Проблемы информационной безопасности в системе высшей школы». Сб. науч. тр. М.: МИФИ, 2005.