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

• Алексеенко, Анна Станиславовна
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Алексеенко, Анна Станиславовна

ВВЕДЕНИЕ.

ГЛАВА 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.Разработано и программно реализовано алгоритмическое обеспечение методики вычисления информационной чувствительности.

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

Список литературы диссертационного исследования кандидат технических наук Алексеенко, Анна Станиславовна, 2010 год

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