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

Алексеенко Анна Станиславовна

Сравнительный анализ компьютерных алгоритмов на основе информационной чувствительности

05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

08460021

Москва 2010

004600212

Работа выполнена на кафедре прикладной математики и моделирования систем в Московском государственном университете печати

Научный руководитель:

доктор технических наук, профессор Ульянов Михаил Васильевич

Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Пылькин Александр Николаевич

кандидат технических наук, доцент Брейман Александр Давидович

Институт радиоэлектроники и информационных технологий Нижегородского государственного технического университета имени P.E. Алексеева

Защита состоится «29» апреля 2010 г. в 1330 на заседании диссертационного совета Д 212.147.03 в Московском государственном университете печати по адресу: 127550, г.Москва, ул. Прянишникова, 2А.

С диссертацией можно ознакомиться в библиотеке МГУП.

Автореферат разослан «26» марта 2010 г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В разное время вопросами анализа сложности алгоритмов, оценки качества программных средств и систем и их алгоритмического обеспечения занимались такие российские и зарубежные ученые, как: А. А. Марков, Г. Е. Цейтлин, Г. С. Цейтин, Ю. И. Янов, Л. А. Левин, В. Е. Котов, В. А. Горбатов, А. И. Мальцев, М. Ю. Мошков, В. А. Носов, Б. Я. Фалевич, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, М. Гэри, Д. Джонсон, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, А. Кобхем, и др.

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

В некоторых проблемных областях к программному обеспечению предъявляются специфические требования, связанные с их особенностями. Характерным примером могут служить системы реального времени, диалоговые системы с существенными временными ограничениями, в том числе поисковые системы. Программное обеспечение таких систем должно не только удовлетворять временным ограничениям, но и обладать стабильностью по времени — различные входы алгоритма при фиксированной длине входа не должны приводить к значительным изменениям времени выполнения (понятие стабильности по времени алгоритма введено М. В. Ульяновым в 2006 г.). Этот показатель является важным, т. к. обеспечивает, наряду с исполнительной аппаратурой, устойчивое время отклика программной системы на различные входы фиксированной длины.

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

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

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

Основные задачи исследования.

1. Анализ основных подходов к оценке качества и выбору компьютерных алгоритмов.

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

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

4. Разработка методики вычисления количественной характеристики информационной чувствительности при фиксированной длине входа.

5. Разработка методики вычисления количественной характеристики информационной чувствительности как функции длины входа.

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

Объект исследования. Компьютерные алгоритмы, принадлежащие классу количественно-параметрических по трудоемкости алгоритмов (класс NPR).

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

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

Научная новизна.

¡.Введена квантильная количественная мера информационной чувствительности компьютерных алгоритмов.

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

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

Практическая ценность результатов работы.

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

Реализация результатов. Разработано программное обеспечение «Вычисление информационной чувствительности и доверительной трудоемкости

компьютерных алгоритмов», на которое получено свидетельство о регистрации программы для ЭВМ Роспатента№ 2010611351.

Результаты исследования используются в учебном процессе Московского государственного областного университета, Московского государственного индустриального университета в рамках дисциплины «Теория алгоритмов», что подтверждено соответствующими актами о внедрении.

Апробация работы. Основные результаты диссертации были представлены на 4-х научных конференциях и семинарах:

• XV Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, 2009 г.);

• IX Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования» (Тамбов, 2009 г.);

• 52-ой Всероссийской научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук" (Москва, 2009 г.);

• III школе-семинаре «Задачи системного анализа, управления и обработки информации» (Москва, 2009 г.).

Публикации. Основные результаты по теме диссертации опубликованы в 4-х работах, из них 1 — в журнале, включенном в Перечень ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы (94 ссылки). Работа изложена на 122 страницах, включая рисунки и таблицы.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследования, сформулированы цели, задачи, объект, предмет, научная новизна и практическая ценность исследования, приводится краткая характеристика основных разделов диссертации.

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

Проанализированы основные подходы к решению задачи оценки качества алгоритмов и способы построения комплексных критериев (Б.А. Трахтенброт, М. Ю. Мошков, В. А. Носов, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, А. Кобхем и др.). Рассмотрены основные компоненты комплексного критерия качества алгоритма:

- оценка сложности самого алгоритма, как количество информации, содержащейся в записи алгоритма;

- оценка сложности вычислительного процесса, задаваемого алгоритмом;

- оценки ресурсной эффективности алгоритмов — временной и емкостной сложности алгоритма.

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

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

В аспекте исследования информационной чувствительности рассмотрена классификация алгоритмов по степени влияния особенностей входных данных на значения трудоемкости. Более детально рассмотрены алгоритмы класса ЛУД (количественно-параметрические по трудоемкости).

На основе проведенного в главе анализа сформулирована постановка задачи о необходимости введения новой количественной меры, обеспечивающей учёт требования стабильности по времени для компьютерных алгоритмов (класс Л7>Л), и позволяющей указать интервал значений трудоёмкости при заданной вероятности.

Во второй главе обоснован выбор вероятностного подхода к описанию трудоемкости алгоритмов.

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

на входах фиксированной длины РА как дискретную ограниченную случайную величину, для чего построена вероятностная модель на множестве входов фиксированной длины Бп:

— — выборочное пространство входов фиксированной длины С10 = Пп, при этом случайное событие со ■ е Пв состоит в том, что в качестве входных

данных алгоритма предъявляется вход 01 е £)„, ] = 1, Л/, где М — число различных допустимых входов алгоритма длины и;

— Рв (•) — вероятностная мера на , отражающая частотную встречаемость входов из Оп в рамках исследуемой проблемной области применения алгоритма в данной программной системе.

В качестве модельного примера приведены экспериментальные данные, полученные в результате исследования алгоритма умножения чисел «в столбик».

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

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

/;(«)=15/7+2.

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

(и) = 15я2 +21и+2.

Экспериментальное исследование алгоритма с целью определения частотной встречаемости значений трудоёмкости РУ3 состояло в проведении ряда экспериментов с его программной реализацией при фиксированной длине входа. Для каждого эксперимента генерировался случайный допустимый алгоритмом вход и, с помощью счётчика, фиксировалось число заданных алгоритмом базовых операций. В предположении о том, что для исследуемого алгоритма в теории получены функции трудоёмкости для лучшего и худшего случаев, теоретический размах варьирования /ЛЛ - разбивается на выбранное число полусегментов. Далее определяется частотная встречаемость значений трудоёмкости У/ъ для каждого из полученных полусегментов и строится экспериментальная гистограмма относительных частот.

Для алгоритма умножения длинных целых чисел «в столбик» при и = 100: /7 =1502, =152102, и теоретический размах варьирования равен 150600.

При разбиении размаха варьирования на равные полусегменты в большинстве из них экспериментальные частоты оказались равны нулю при 20000 экспериментов, что свидетельствует о малой вероятности входов, приводящих к таким значениям трудоёмкости. В связи с этим на рис. 1 показаны только ненулевые части гистограммы относительных частот трудоёмкости для алгоритма умножения длинных целых чисел «в столбик» при длине входа п =100, полученные по результатам обработки 20000 экспериментов.

; 0,25 к

496Э4 58498 Б7303 76107 84311 9371Б 102520 111324

Гтр

Рис. 1. Ненулевая часть гистограммы относительных частот значений трудоемкости алгоритма умножения длинных целых чисел «в столбик»

В рамках представленного вероятностного подхода к рассмотрению значений трудоемкости алгоритма введена в рассмотрение случайная функция FA(n), значения которой являются значениями функции трудоемкости алгоритма А на входах длины п.

Рассмотрены статистические точечные оценки функции трудоемкости: математического ожидания fA{n)= и дисперсии DF (и)=

В третьей главе введена квантильная-количественная мера информационной чувствительности компьютерных алгоритмов.

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

— быть эффективно вычислимой на основе экспериментальных данных, полученных в ходе исследования алгоритма;

— измеряться в единых единицах измерения в количественной шкале (шкала с естественным нулем, максимумом или минимумом);

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

— подчиняться единому для различных предметных областей принципу содержательной интерпретации;

— быть сопоставимостью, т.е. давать возможность решения на её основе задачи сравнения и выбора рациональных алгоритмов;

— обеспечивать возможность идентификации интервала трудоёмкости по заданной вероятности.

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

Предложен подход к рассмотрению информационной чувствительности Sj(y,n) как длины теоретического сегмента варьирования трудоемкости, в которой с заданной вероятностью у будут наблюдаться значения трудоемкости алгоритма на входах фиксированной длины п.

Для вычисления б ¡{у) предложено аппроксимировать функцию распределения вероятностей значений трудоемкости некоторой известной функцией распределения F{x), .re[0,1]. При подтвержденной гипотезе об аппроксимации квантильная количественная мера информационной чувствительности вычисляется следующим образом:

5,{У) = F-1 (д+§F"1 (д-0 при п = const,

где F~x(x) — функция, обратная к F(x).

В целях практического применения предложено рассматривать кван-тильную количественную меру информационной чувствительности не только как функцию доверительной вероятности, но и как функцию размерности 51 (у, п). Для случая аппроксимации частотной встречаемости значений трудоёмкости функцией плотности бета-распределения

где Г() — гамма функция Эйлера, а а и р — параметры функции плотности, предложена методика расчета значений ¿¡(у,»), включающая в себя следующие этапы:

— экспериментальное исследование алгоритма, построение гистограммы относительных частот трудоёмкости, нормирование значений трудоемкости

/•_ /-V

' ~ у-л у V' проверка гипотезы об аппроксимирующей функции плотности;

— определение актуального сегмента длин входов, сегмента длин для экспериментального исследования и шага изменения длины входа;

— идентификация параметров бета-распределения а и /7 методом моментов на основе данных выборки;

— задание доверительной вероятности у и расчёт 81 (у, п) на основе у¡2 -квантилей функции плотности бета-распределения относительно медианы распределения в сегменте экспериментального исследования:

— построение аппроксимирующей кривой значений квантильной количественной меры информационной чувствительности;

— прогнозирование значений для актуального сегмента длин входов.

Для рассмотренного алгоритма умножения длинных чисел в столбик был определен актуальный сегмент длин входов [100, 700], экспериментальный сегмент [100,400] и шаг изменения длины входа— 100.

Зависимость параметров бета-распределения а и ¡3 от длины входа п проиллюстрирована на рис.2.

и

Рис.2. Зависимость параметра а в зависимости от длины входа п. Экспериментаяьные данные и аппроксимирующая кривая.

II

Рис.3. Зависимость параметра р в зависимости от длины входа п. Экспериментальные данные и аппроксимирующая кривая.

На основе экспериментальных данных были получены значения Аппроксимирующая кривая для экспериментального сегмента показана на рисунке 4:

П

Рис.4. Экспериментальные значения количественной меры информационной чувствительности для сегмента длин входа [100, 400].

На основе полученного уравнения регрессии прогноз для и = 700 составил: д1 (0,95, 700)= 0,0735. Проведенный контрольный эксперимент показал, что реальное значение равно 0,0741 и ошибка прогноза не превысила 1%.

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

Содержательно введенная квантильная количественная мера 31 (у, п) представляет собой длину теоретического сегмента варьирования, в который значения функции трудоемкости попадают с заданной вероятностью у.

В предположении об аппроксимации частотной встречаемости значений трудоёмкости функцией плотности симметричного бета-распределения, кван-тильная количественная мера информационной чувствительности иллюстрируется рис. 5.

\

/. Г 4

1; 2 1:\

/: У 1 ■ \ ' V

О 0,5 1 ^

Рис.5. Квантилъная количественная мера информационной чувствительности

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

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

Для иллюстрации разработанной методики была выбрана задача поиска подстроки в строке и три алгоритма, решающие эту задачу: алгоритм Рабина-Карпа, алгоритм Кнута-Морриса-Пратта и алгоритм последовательного поиска. Для каждого из алгоритмов при длине строки и = 10000, длине искомой подстроки т = 20 была проведена серия в 20000 экспериментов, в которых фиксировались значения функции трудоемкости. По результатам опытов были построены гистограммы относительных частот значений функции трудоемкости (с использованием разработанного программного обеспечения).

0,12 0,10 0.08 0.06 0,04 0.02 -

0.00

11

I

220122 220180 220318 220430 220520 220810 220749 220886 221154

f т/>

Рис. 6. Ненулевая часть гистограммы относительных частот значений функции трудоемкости для алгоритма Рабина-Карпа.

0,2

0,15

0,1

0,05

1

I I

140333 142500 146250 157000 158450 158670 158860 158900

1 тр

Рис. 7. Ненулевая часть гистограммы относительных частот значений функции трудоемкости для алгоритма Кнута-Морриса-Пратта.

0,2 -

0,15 -0,1 0,05

О

100077 103300 108700 118000 129700 131200 131750 131850

1 тр

Рис.8 Ненулевая часть гистограммы относительных частот значений функции трудоемкости для алгоритма последовательного поиска.

Была выдвинута гипотеза об аппроксимации распределения относительный частот значений трудоёмкости функцией плотности бета-распределения.

Для проверки гипотезы была произведена нормировка экспериментальных значений трудоёмкости в сегмент [ОД]. Были определены границы полусегментов разбиения сегмента [ОД] и рассчитаны эмпирические частоты в полусегментах.

----: -г- : ■ - ^ - ^......г — .....'

По нормированным данным рассчитаны значения выборочной средней и выборочной исправленной дисперсии, на основе которых с помощью метода моментов были получены параметры а и /? аппроксимирующего бета-распределения. Интегрированием полученной функции плотности по полусегментам были вычислены теоретические частоты. Корректная проверка гипотезы о бета-распределении была выполнена с использованием критерия Пирсона при уровне значимости 0,05. Во всех случаях наблюдаемое значение критерия Пирсона было значимо меньше, чем критическая точка, что позволяет принять гипотезу о бета-распределении.

1 у

С доверительной вероятностью / = 0,95 на основе — квантилей полученного аппроксимирующего бета-распределения (очевидно с разными параметрами для разных алгоритмов) были вычислены следующие значения информационной чувствительности:

¿>, (0,95;10000;20) = 0,0002 для алгоритма Рабина-Карпа, (0,95; 10000; 20) = 0,2104 для алгоритма Кнута-Морриса-Пратта,

81 (0,95; 10000; 20) = 0,0123 для алгоритма последовательного поиска.

На основании полученных результатов был сделан вывод: в ситуации рационального выбора по критерию стабильности по времени при заданной размерности входных данных (длине строки « = 10000, длине подстроки т = 20) алгоритм Рабина-Карпа предпочтительнее из трех указанных как более стабильный по времени.

Для алгоритма Рабина-Карпа были также вычислены значения информационной чувствительности при других значениях доверительной вероятности: у = 0,9 и ^ = 0,99:

<5, (0,9;10000; 20) = 0,00016;

81 (0,99; 10000; 20) = 0,00027.

Сравнительно с другими исследованными алгоритмами отметим, что даже при у = 0,99 информационная чувствительность алгоритма Рабина-Карпа существенно (более чем в четыре раза) меньше, чем у других алгоритмов.

При вычислении статистической количественной меры для этого алгоритма было получено значение: 51%(10000,20)= 0,0021 3[5 = 0,00121, не учитывающее значение доверительной вероятности (по определению статистической меры). Вычисления проводились по формуле:

где:

(/»-/»)/ (/»+/;(«)) нормированный размах варьирования, а

у{п)=°ш!7Ап)

коэффициент вариации значений трудоёмкости.

Рис. 9. Изменение значений квантильной количественной меры информационной чувствительности 6, алгоритма Рабина-Карпа при изменении длины строки п и длины

подстроки т.

Аналогичные экспериментальные исследования были проведены при длине строки л 6 [5000; 30000] с шагом, равным 5000 и длине подстроки /ие[10;80] с шагом, равным 10. На рис.9 показано изменение значений квантильной количественной меры информационной чувствительности.

Рис. 10. Изменение значений квантильной количественной меры информационной чувствительности 51 алгоритма Кнута-Морриса-Пратта при изменении длины строки

п и длины подстроки т.

0,22 0,215 0,21 0,205 0,2 0,195

33000 25000 20000 15000 10000 5000

б

0,025

0,015

0,03

о,оа

0,02

0,0'

п

т

Рис. 11. Изменение значений квантильной количественной меры информационной чувствительности 81 алгоритма последовательного поиска при изменении длины строки п и

длины подстроки т.

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

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

2. Обоснован выбор вероятностного подхода к рассмотрению трудоемкости алгоритмов класса МРИ (класса алгоритмов количественно параметрических по трудоемкости).

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

4. Разработана методика вычисления квантильной количественной меры информационной чувствительности как функции длины входа.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

6. Разработано и программно реализовано алгоритмическое обеспечение методики вычисления информационной чувствительности. Получено свидетельство Роспатента о регистрации программы.

7. Результаты работы используются в учебном процессе Московского государственного областного университета и Московского государственного индустриального университета в рамках дисциплины «Теория алгоритмов».

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В журналах, входящих в Перечень изданий, рекомендованных ВАК РФ.

1. Алексеенко A.C., Ульянов М.В. Вероятностный подход к определению количественной меры информационной чувствительности компьютерных алгоритмов // Автоматизация и современные технологии.- 2009, №10.- С.24 - 32.

В других изданиях.

2. Алексеенко A.C., Ульянов М.В., Количественная мера информационной чувствительности компьютерных алгоритмов на основе квантилей аппроксимирующего распределения // Информационные системы и технологии. Материалы XV международной технической конференции - Нижний Новгород, НГТУ им. Р.Е.Алексеева, 2009.- С. 288-289.

3. Алексеенко A.C., Ульянов М.В. Трудоемкость алгоритма как случайная величина // Материалы докладов IX Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования», часть П.-Тамбов, Тамбовское высшее военное авиационное инженерное училище радиоэлектроники, 2009. - С. 203 - 208.

4. Алексеенко A.C. Анализ информационной чувствительности алгоритма Рабина-Карпа // Труды 52-ой Всероссийской научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук», часть IX. -Москва-Долгопрудный, Московский физико-технический институт, 2009. -С. 13-16.

Патенты, свидетельства на программы для ЭВМ:

5. Ульянов М.В., Кривенцов A.C., Алексеенко A.C. Вычисление информационной чувствительности и доверительной трудоемкости компьютерных алгоритмов - свидетельство об официальной регистрации программы для ЭВМ № 2010611351// Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. — 16.02.2010

Подписано в печать 23.03.2010. Формат 60x84/16. Бумага офсетная. Печать на ризографе. Печ. л. 1.00. Тираж 100 экз. Заказ №74/57. Отпечатано в РИЦ Московского государственного университета печати 127550, Москва, ул. Прянишникова, 2а

ВВЕДЕНИЕ.

ГЛАВА 1 .АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К ОЦЕНКЕ КАЧЕСТВА АЛГОРИТМОВ.

1.1. Понятие и определения алгоритма.

1.2. Требования к алгоритмам и их свойства.

1.3. Модели вычислений.

1.3.1.Основные компоненты модели вычислений.

1.3.2.Модель вычислений для языка процедурного программирования.

1.3.3 .Базовые операции механизма реализации.

1.4. Оценки ресурсной эффективности алгоритмов.

1.4.1.Классические методы оценки алгоритмов.

1.4.2.0ценки в теории сложности вычислений.

1.4.3.Терминология и обозначения в теории ресурсной эффективности.

1.4.4.Ресурсная характеристика и ресурсная сложность алгоритма.

1.5. Комплексные критерии качества алгоритмов.

1.6. Требование стабильности по времени.

1.7. Классификация компьютерных алгоритмов по степени влияния особенностей входов на трудоемкость.

1.8.Постановка задачи исследования.

ГЛАВА 2.ВЕРОЯТНОСТНЫЙ ПОДХОД К ОПИСАНИЮ ТРУДОЕМКОСТИ КОМПЬЮТЕРНЫХ АЛГОРИТМОВ.

2.1. Особенности трудоемкости алгоритмов в классе NPR

2.2. Трудоемкость алгоритма на входах фиксированной длины как дискретная ограниченная случайная величина.

2.3. Гистограмма относительных частот трудоёмкости для алгоритма умножения длинных целых чисел «в столбик».

2.4. Трудоемкость как случайная функция и её статистические точечные оценки.

2.5. Выводы.

ГЛАВА 3.ИНФОРМАЦИОННАЯ ЧУВСТВИТЕЛЬНОСТЬ

КОМПЬЮТЕРНЫХ АЛГОРИТМОВ И ЕЕ КОЛИЧЕСТВЕННАЯ МЕРА

3.1. Вычисление количественной меры информационной чувствительности на основе квантилей аппроксимирующей функции плотности.

3.2. Квантильная количественная мера информационной чувствительности как функция доверительной вероятности и функция размерности.

3.3. Методика вычисления квантильной количественной меры информационной чувствительности для случая аппроксимации гистограммы относительных частот функцией плотности бетараспределения.

ЗАВыводы.

ГЛАВА 4. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА ПОДСТРОКИ В СТРОКЕ НА ОСНОВЕ ИНФОРМАЦИОННОЙ ЧУВСТВИТЕЛЬНОСТИ.

4.1. Задача поиска подстроки в строке.

4.2. Минимум и максимум теоретической функции трудоемкости алгоритма Рабина-Карпа в случае однократного вхождения подстроки.

4.3. Теоретическая функция трудоемкости алгоритма Кнута-Морриса-Пратта в случае однократного вхождения подстроки.

4.4. Теоретическая функция трудоемкости алгоритма последовательного, поиска в случае однократного вхождения подстроки.

4.5. Сравнение алгоритмов Рабина-Карпа, Кнута-Морриса-Пратта и последовательного поиска по критерию стабильности по времени на основе экспериментальных данных.

4.5.1.Экспериментальное исследование алгоритма Рабина-Карпа. 101 4.5.2.Экспериментальное исследование алгоритма Кнута-Морриса

Пратта.

4.5.3.Экспериментальное исследование алгоритма последовательного поиска.

4.5.4. Сравнение алгоритмов Рабина-Карпа, Кнута-Морриса-Пратта и последовательного поиска по стабильности по времени.

4.6. Изменение значений количественной квантильной меры информационной чувствительности для алгоритмов поиска подстроки в строке при изменении длины строки и длины подстроки.

Актуальность исследования.

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

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

A. А. Марков, Г. Е. Цейтлин, Г. С. Цейтин, Ю. И. Янов, JI. А. Левин,

B. Е. Котов, В. А. Горбатов, А. И. Мальцев, М. Ю. Мошков, В. А. Носов, Б. Я. Фалевич, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, М. Гэри, Д. Джонсон, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, А. Кобхем, и др.

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

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

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

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

Основные задачи исследования.

1. Анализ основных подходов к оценке качества и выбору компьютерных алгоритмов.

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

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

4. Разработка методики вычисления количественной характеристики информационной чувствительности при фиксированной длине входа.

5. Разработка методики вычисления количественной характеристики информационной чувствительности как функции длины входа.

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

Объект исследования. Компьютерные алгоритмы, принадлежащие классу количественно-параметрических по трудоемкости алгоритмов (класс NPR).

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

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

Научная новизна.

1. Введена квантильная количественная мера информационной чувствительности компьютерных алгоритмов.

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

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

Практическая ценность результатов работы.

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

Реализация результатов. Разработано программное обеспечение «Вычисление информационной чувствительности и доверительной трудоемкости компьютерных алгоритмов», на которое получено свидетельство о регистрации программы для ЭВМ Роспатента № 2010611351.

Результаты исследования используются в учебном процессе - Московского государственного областного университета, Московского государственного индустриального университета в рамках дисциплины «Теория алгоритмов», что подтверждено соответствующими актами о внедрении.

Апробация работы. Основные результаты диссертации были представлены на 4-х научных конференциях и семинарах:

• XV Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, 2009 г.);

• IX Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования» (Тамбов, 2009 г.);

• 52-ой Всероссийской научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук" (Москва, 2009 г.);

• III школе-семинаре «Задачи системного анализа, управления и обработки информации» (Москва, 2009 г.).

Публикации. Основные результаты по теме диссертации опубликованы в 4-х работах, из них 1 — в журнале, включенном в Перечень ВАК РФ.

Результаты проведенных исследований подробно изложены в последующих четырех главах.

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

Проанализированы основные подходы к решению задачи оценки качества алгоритмов и способы построения комплексных критериев (Б.А. Трахтенброт, М. Ю. Мошков, В. А. Носов, Д. Э. Кнут, А. Ахо, Дж. Хопкрофт, Дж. Ульман, Р. Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, и др.). Рассмотрены основные компоненты комплексного критерия качества алгоритма.

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

В аспекте исследования информационной чувствительности рассмотрена классификация алгоритмов по степени влияния особенностей входных данных на значения трудоемкости. Более детально рассмотрены алгоритмы класса NPR (количественно-параметрические по трудоемкости).

На основе проведенного в главе анализа сформулирована постановка задачи о необходимости введения новой количественной меры, обеспечивающей учёт требования стабильности по времени для компьютерных алгоритмов класса NPR, и позволяющей указать интервал значений трудоёмкости при заданной вероятности.

Во второй главе обоснован выбор вероятностного подхода к описанию трудоемкости алгоритмов.

Предложено рассматривать значения трудоемкости алгоритма класса NPR на входах фиксированной длины FA как дискретную ограниченную случайную величину, для чего построена вероятностная модель на множестве входов фиксированной длины Dn:

Q.d — выборочное пространство входов фиксированной длины Qd = Dn, при этом случайное событие C0j е Q.D состоит в том, что в качестве входных данных алгоритма предъявляется вход D} е Dn, j = 1,М, где М — число различных допустимых входов алгоритма длины п;

PD0 — вероятностная мера на QD, отражающая частотную встречаемость входов из Dn в рамках исследуемой проблемной области применения алгоритма в данной программной системе.

PF{FA=fi) = YJPD{Dj\ Dj : Dj е Dn, fA (Dj ) =

В качестве модельного примера приведены экспериментальные данные, полученные в результате исследования алгоритма умножения чисел «в столбик».

В третьей главе введена квантильная количественная мера информационной чувствительности компьютерных алгоритмов.

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

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

Предложен подход к рассмотрению информационной чувствительности 5j{y,n) как длины теоретического сегмента варьирования трудоемкости, в которой с заданной вероятностью у будут наблюдаться значения трудоемкости алгоритма на входах фиксированной длины п.

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

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

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

8.Результаты работы используются в учебном процессе Московского государственного областного университета, Московского государственного индустриального университета в рамках дисциплины «Теория алгоритмов».

ЗАКЛЮЧЕНИЕ

Проведенное диссертационное исследование позволило получить следующие результаты:

1. Проведен анализ основных подходов к оценке качества и выбору компьютерных алгоритмов. Определена исследуемая характеристика алгоритмов — стабильность по времени.

2. Сформулирована задача о вычислении количественной характеристики стабильности по времени компьютерных алгоритмов.

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

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

5. Разработана методика вычисления квантильной количественной меры информационной чувствительности как функции длины входа.

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

7.Разработано и программно реализовано алгоритмическое обеспечение методики вычисления информационной чувствительности.

Получено свидетельство Федеральной службы по интеллектуальной собственности, патентам и товарным знакам о регистрации программы для ЭВМ.

1. Алексеев В. Е., Таланов В. А. Графы и алгоритмы. Структуры данных. Модели вычислений: Учебник. — М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006. —320 с.

2. Алферова 3. В. Теория алгоритмов. — М.: Статистика, 1973. — 163 с.3." Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров— М.: Высшая школа, 1994. — 93 с.

3. Андерсон Дж. Дискретная математика и комбинаторика: Пер. с англ. — М.: Издательский дом «Вильяме». 2003. — 960 с.

4. АсановМ.О., Баранский В.А., Расин В.В. Дискретная математика. Графы, матроиды, алгоритмы,- Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001г., 288 с.

5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах. Т. 1. Синтаксический анализ: Пер. с англ.: — М.: Мир, 1978. — 612 с.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ.: —М.: Мир, 1979. — 546 с.

7. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.: — М.: Издательский дом «Вильяме», 2001. — 384 с.

8. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. —М.: Лаборатория Базовых Знаний, 2001 г. — 632 с.

9. Беркли Э. Символическая логика и разумные машины— М.: Издательство иностранной литературы, 1961. — 260 с.

10. ВалееваА. Ф., Гареев И. Р., Мухачева Э. А. Задача одномерной упаковки: рандомизированный метод динамического перебора и метод перебора с усечением // Приложение к журналу «Информационные технологии». 2003. № 2. — 24 с.

11. Ван дер Варден Б.Л. Математическая статистика М.: Издательство иностранной литературы, 1960. — 120 с.

12. ВиртН. Алгоритмы и структуры данных: Пер. с англ. -2-е изд., испр. — СПб.: Невский диалект, 2001. — 352 с.

13. Гасанов Э.Э., Кудрявцев В.Б. Теория хранения и поиска информации—М.: ФИЗМАТ ЛИТ, 2002. — 288 с.

14. Гасфилд Д. Строки, деревья и последовательности в алгоримах: Информатика и вычислительная биология. — СПб.:Невский диалект, БХВ Санкт-Петербург, 2003. — 654 с.

15. Гашков С. Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений: Учеб. пособие для вузов / Под ред. В. А. Садовничего. 2-е изд., перераб. — М.: Высшая школа, 2000. — 320 с.

16. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы / Под ред. В.М. Курейчика. 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

17. ГмурманВ. Е. Теория вероятностей и математическая статистика: Учеб. пособие для вузов, 9-е изд., стер.— М.: Высшая школа, 2003.—479 с.

18. Головешкин В.А., Ульянов М. В. Теория рекурсии для программистов. —М.: ФИЗМАТЛИТ, 2006. — 296 с.

19. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика М.: Наука. ФИЗМАТЛИТ, 2000, — 544с.

20. Горбатов В А. Синтез логических схем в произвольном базисе.// Теория дискретных автоматов, Рига, Зинатне. 1967. - С.71-82.

21. Грин Д., Кнут Д. Математические методы анализа алгоритмов1. М.: Мир, 1987. — 120 с.

22. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. — М.: Мир, 1998. — 703 с.

23. Гудман С., Хидетниеми С. Ведение в разработку и анализ алгоритмов. — М.: Мир, 1981. — 368 с.

24. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 с.

25. Жуков О. Д. Методы контроля ошибок для компьютерных модулярных вычислений // Информационные технологии. 2003. № 2. С. 33-40.

26. Ильин В. А., Садовничий В. А., Сендов Бл. X. Математический анализ. — М.: Наука. Главная редакция физико-математической литературы, 1979. —720 с.

27. Кнут Д. Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2002.720 с.

28. Колмогоров А. Н., Драгалин А.Г., Математическая логика М.: Едиторал УРСС, 2005. 240с.

29. Колмогоров А. Н., Успенский В. А. К определению алгоритма // Успехи математических наук.' 1958. Т. 13. № 4. С. 3-28.

30. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-ое издание: Пер. с англ. — М.: Издательский дом «Вильяме», 2005. — 1296 с.

31. Королюк B.C., Портенко Н.И., Скороход А.В., Турбин А.Ф. Справочник по теории вероятностей и математической статистике. — М.: Наука, 1985.

32. Котов В. Е., Сабельфельд В. К. Теория схем программ. — М.: Наука, 1991. — 231 с.

33. Кульбак С. Теория информации и статистика— М.: Наука, 1967. — 134 с.

34. Лагутин М. Б. Наглядная математическая статистика: Учебное пособие. — М.: БИНОМ. Лаборатория знаний, 2007. — 472 с.

35. Лесин В.В., Лисовец Ю.П. Основы'методов оптимизации. М.: МАИ, 1998.

36. Липаев В. В. Методы обеспечения качества крупномасштабных программных средств. СИНТЕГ, 2003. - 520 с. (Серия «Управление качеством»)

37. Липаев В. В. Обеспечение качества программных средств. — М.: СИНТЕГ. 2001. — 384 с.

38. Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. — М.: Техносфера, 2004. — 368 с.

39. Мальцев А.И.Алгоритмы и рекурсивные функции. — М.: Наука, 1986. —367 с.

40. Марков А. А., Нагорный Н. М. Теория алгорифмов. — М.: Наука, 1984. — 432 с.

41. Маркова Н. А. Качество программы и его измерения // Системы и средства информатики. Вып. 12. — М.: Наука, 2002. С. 170-188.

42. Математическая энциклопедия. Под ред. И.М. Виноградова. — М.: Сов. энциклопедия, 1977 г.

43. Матиясевич Ю. В. Десятая проблема Гильберта. — М.: Наука, 1993.

44. Методы классической и современной теории автоматического управления: Учебник в 3 т. Т. 3: Методы современной теории автоматического управления / Под ред. Н. Д. Егупова. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. — 748 е.: ил.

45. Миз К., Джеймс Т. Теория фотографического процесса. — JL: Химия, 1973. —576 с.

46. Минский М. Вычисления и автоматы. М.: Мир, 1971.- 146 с.

47. Нивергельт Ю., Фаррар Дж., Рейнгольд Э. Машинный подход к решению математических задач — М.: Мир, 1977. — 298 с.

48. Ноден П., Китте К. Алгебраическая алгоритмика: Пер. с франц. — М.: Мир, 1999. — 720 с.

49. Носов В. А. Основы теории алгоритмов и анализа их сложности (http: // rrc.dgu.ru/res/intsys.msu.ru/staff/vnosov/theoralg.htm).

50. Офман Ю. П. Об алгоритмической сложности дискретных функций // Доклады АН СССР. 1962. Т. 45. Вып. 1. С.48-51.

51. Петрушин В. Н., Ульянов М. В. Планирование экспериментального исследования трудоёмкости алгоритмов на основе бета-распределения // Информационные технологии и вычислительные системы. 2008. №2. С.81-91.

52. Проблемы Гильберта // Сб. под общ. ред. П.С. Александрова, — М.: Изд. "Наука", 1969.

53. Прохоров Ю. В., Розанов Ю. А. Теория вероятностей (Основные понятия. Предельные теоремы. Случайные процессы). — М.: Наука, 1973. —494с.

54. Рейнгольд Э. Комбинаторные алгоритмы./ Рейнгольд Э., Нивергельдт Ю., Део Н.- М.:Мир, 1980.

55. Системная компьютерная биология / Отв. ред. Н.А. Колчанов и др. — Новосибирск: Из-во СО РАН, 2008. — 769 с.

56. Трахтенброт Б. А. Сигнализирующие функции и табличные операторы // Записки Пензенского ГПИ. 1956. Вып. 4.

57. Трахтенброт Б. А. Сложность алгоритмов и вычислений. — Новосибирск: Изд-во НГУ, 1967. — 243 с.

58. Тюрин Ю.Н. Макаров А.А. Анализ данных на компьютере / Под ред. В.Э. Фигурнова. — М.: ИНФРА-М, 2003. — 544 с.

59. Ульянов М.В. Архитектуры процессоров. Учебное пособие. М.: МГАПИ, 2002. — 68 с.

60. Ульянов М. В. Исследование и классификация вычислительных алгоритмов на основе чувствительности функции трудоемкости // Системы управления и информационные технологии. 2004. № 4 (16). С. 97-104.

61. Ульянов М. В. Классификация и методы сравнительного анализа вычислительных алгоритмов. Научное издание. — М.: Издательство физико-математической литературы, 2004. — 212 с.

62. Ульянов М.В. Метод прогнозирования временных оценок программных реализаций алгоритмов на основе функции трудоемкости // Информационные технологии. 2004. № 5. С. 54-62.

63. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ. — М.: ФИЗМАТЛИТ, 2008. — 304 с.

64. Ульянов М. В. Система обозначений в анализе ресурсной эффективности вычислительных алгоритмов // Вестник МГАПИ. Серия: Естественные и инженерные науки. 2004 №1(1). С.42-49.

65. Ульянов М. В. Типизация алгоритмов по количественной мере размерностной чувствительности функции трудоемкости // Интеллектуальные системы: Труды Шестого международного симпозиума — М.: РУСАКИ, 2004. С. 371-374.

66. Ульянов М.В., Алексеенко А.С. Вероятностный подход к определению количественной меры информационной чувствительности компьютерных алгоритмов // Автоматизация и современные технологии-2009.-№10.-С.24 32.

67. Ульянов М. В., Гурин Ф. Е., Исаков А. С., Бударагин В. Е. Сравнительный анализ табличного и рекурсивного алгоритмов точногорешения задачи одномерной упаковки // Exponenta Pro Математика в приложениях. 2004. №2(6). С. 64-70.

68. Ульянов М. В., Петрушин В. Н., Кривенцов А. С. Доверительная трудоёмкость — новая оценка качества алгоритмов // Информационные технологии и вычислительные системы. 2009. №2. С.64-77.

69. Успенский В.А. Машина Поста -— М.: Наука. Главное издательство физико-математической литературы, 1988. — 96 с.

70. Успенский В А., Семенов АЛ. Теория алгоритмов: основные понятия и приложения М.: Наука. Главное издательство физико-математической литературы, 1987. — 288 с.

71. Фалевич Б. Я. Теория алгоритмов: Учебное пособие. — М.: Машиностроение, 2004. — 160 с.

72. Хаггарти Р. Дискретная математика для программистов— М.: Техносфера, 2005. — 400 с.

73. Хопкрофт Дж., Мотовани Р., Ульман Дж. Ведение в теорию автоматов, языков и вычислений, 2-е изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2002. — 528 с.

74. Цейтин Г. С. Оценка числа шагов при применении нормального алгоритма. // Математика в СССР за 40 лет. — М., 1959. Т. 1.

75. Чечкин А.В. Математическая информатика / Чечкин.- М.: наука, 1991-416с.

76. Чжун К. Л., АитСахлиа Ф. Элементарный курс теории вероятностей. Стохастические процессы и финансовая математика. — М.: БИНОМ. Лаборатория знаний, 2007. —455 с.

77. Aho A. Algorithms for finding patterns in strings // Handbook of Theoretical Computer Science / Ed.:J.Van Leeuwen. MIT Press / Elsevier. 1990. Vol. A.P. 257-300

78. Crochemore M., Rytter W. Text Algorithms. New York: Oxford Univ. Press, 1994

79. Gonnet G.H., Bayeza-Yates R. HandBook of Algorithmsand Data Structures. 2nd ed. Reading. M.A. Addison-Wesley, 1991

80. Kleene S.C. Introduction to Metamathematics.-Princeton (N.J.), 1952

81. Knuth D.E., Morris J.H., Pratt V.B. Fast pattern matching in strings // SIAM J.Comput. 1977, Vol.6, P.323-350

82. Motwani R., Raghavan P. Randomized Algorithms. Cambridge Univ. Press, 1995

83. Post E. L. Finite combinatory process — formulation 1 // J. Symbolic Logic (1936) 1, pp. 103-105.

84. Rabin M.O. "Probablistic Algorithms" in Algorithms and Complexity: Resent Rezults and New Directions (J.F.Traub ed.) pp.21-39, Academic Press, New York, 1976

85. Shannon С. A universal Turing machine with two internal states.- In. Automata Studies, Princeton, 1956

86. Tarjan R.E. Amortized computational complexity / Tarjan R.E. // Slam J. on Algebraic and Discret Methods.-1985.-6(2).-P.306-318.

87. Turing A. M. On Computable Numbers, whiz an Application to the Entsheidungsproblem // Proc. London Math. Soc. (1937) 42, Ser 2, pp. 230-235.

88. Wang Hao A variant to Turing's theory of computermachines.-J.Assoc.Comp.Mach., 1957, 4, №1, P.63-92