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

На правах рукописи

УЛЬЯНОВ Михаил Васильевич

РЕСУРСНАЯ ЭФФЕКТИВНОСТЬ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ: ТЕОРИЯ И ПРИМЕНЕНИЕ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов, систем и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва 2005

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

Официальные оппоненты: доктор технических наук, профессор

ВЕРМИШЕВ Ю.Х.

доктор технических наук, профессор ЛЬВОВИЧ Я.Е.

доктор технических наук, профессор СОЛОДОВНИКОВ И.В.

Ведущая организация: Институт программных систем РАН

(г. Переяславль-Залесский)

Защита состоится 5 апреля 2005 г. в 12 часов на заседании диссертационного Совета Д 212.119.02 в Московской государственной академии приборостроения и информатики (107996 Москва, Стромынка, 20)

С диссертацией можно ознакомится в библиотеке

Московской государственной академии приборостроения и информатики Автореферат разослан 2 марта 2005 г.

Ученый секретарь диссертационного йпиега Д 212.119.02

д. т. н., проф.

Слепцов В.В.

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

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

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

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

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

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

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

Отметим в данном контексте работы В В Липаева по системе оценок качества программных средств и систем, теоретические результаты по анализу задач информационного поиска полученные Э Э Гасановым и В Б Кудрявцевым в Московском государственном университете, исследования, проводимые в Томском политехническом университете по экспериментальному определению временной эффективности алгоритмов (под руководством В 3 Ямпольского), в Ярославском государственном университете по полиэдральным графам задач (В А Бондаренко)

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

Объект исследования. Объектами исследования диссертационной работы являются вычислительные (компьютерные) алгоритмы в рамках модели вычислений машины с произвольным доступом к памяти (RAM) в аспекте их ресурсной эффективности при ограничениях, налагаемых особенностями и спецификой их применения в разрабатываемых программных средствах и системах

В работе под термином вычислительный алгоритм понимается реализуемый на ЭВМ алгоритм (компьютерный алгоритм), соответствующий RAM модели вычислений, под ресурсной эффективностью алгоритма — его временная эффективность и ресурсоем кость, определяющие соответствующие показатели качества программных средств (ГОСТ 28195)

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

Основные задачи исследования Достижение поставленной цели предпотага-ет решение следующих основных задач

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

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

— системы определений и обозначений, ориентированной на задачи анализа ресурсной эффективности,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Возможности использования теоретических и практических результатов работы в учебном процессе ВУЗов в дисциплинах «1 еория алгоритмов», «Разработка эффективных алгоритмов», как в лекционных курсах, так и для проведения практических и лабораторных работ

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

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

— система конечно-элементного аначиза « Гсрмоупругость 3D», внедренная в РКК «Энергия» в составе НИР «Программа для расчета и тепловых испытаний тур-бонасосного агрегата и оценки их резучьтатов», — разработаны комбинированные ресурсно-эффективные алгоритмические решения для компонента формирования глобальной матрицы,

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

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

На основе результатов диссертационного исследования разработана «Система экспериментального анализа алгоритмов», зарегистрированная в Федеральной стужбе по интеллектуальной собственности, патентам и товарным знакам (№ 2004612709 от 20 12 04) Практически значимые методы и методики, предложенные в диссертационной работе, составляют основу для выполнения научно-исследовательской работы «Разработка методов получения вычислитетьных алгоритмов и оценки их трудоемкости» (№ госрегистрации 01 2 00410094), выполняемой в МГАПИ по заданию Министерства образования РФ Теоретические и практически значимые результаты работы внедрены в учебный процесс Санкт-Петербургского государственного университета (факультет прикладной математики — процессов управления), Рязанской радиотехнической академии, Московского автодорожного института (технический университет), Московской государственной академии приборостроения и информатики Использование результатов диссертационной работы при разработке программных систем и в учебном процессе подтверждено актами о внедрении

Основные результаты, выносимые на защиту:

1 Основы теории ресурсной эффективности вычислительных алгоритмов

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

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

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

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

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

2 Метод прогнозирования временной эффективности программных реализаций алгоритмов на основе функции трудоемкости и функциональной зависимости среднего времени выполнения обобщенной базовой операции от длины входа

3 Ресурсно-эффективные комбинированные алгоритмы в составе алгоритмического обеспечения сложных наукоемких программных систем, разработанные на основе предложенных методов и методик

Апробация работы Основные положения и результаты диссертационной работы докладывались на международных и всероссийских конференциях и семинарах XI Международном научно-техническом семинаре «Современные техноло! ии в задачах управления автоматики и обработки информации», А тушта, 2002 г, VI Всероссийской научно-технической конференции «Новые информационные технологии», Москва, 2003 г, VI Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2003 г, VII Всероссийской научно-технической конференции «Новые информационные технопогии», Москва, 2004 г, XIII Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 2004 г, VII Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2004 г , VI Международном симпозиуме «Интечлектуальные системы», Саратов, 2004 г научных семинарах кафедр «Персональные компьютеры и сети» под рук д т и, проф Б М Михайлова и «Управление и моделирование систем» под рук д т н , проф С Н Музыкина

Публикации По материалам диссертации опубликованы 33 печатных работы, 11 из которых — в центральных изданиях [монография (издательство «Физмат-лит»), 9 статей в ведущих научных журналах, рекомендованных ВАК РФ >чебное пособие (дополнение к книге издательства «Техносфера»)], 11 публикаций в журналах и межвузовских сборниках научных трудов 8 публикаций в научных трудах международных и всероссийских конференций Ряд результатов диссертации лег в основу учебных пособий по теории алгоритмов и разработке эффективных алгоритмов для студентов МГАПИ

Структура и объем работы Диссертация состоит из введения, пяти глав, заключения, приложения и библиографического списка Общий объем работы — 309 страниц текста, из них 288 страниц — основное содержание вктючая 41 рисунок и 12 таблиц, 7 страниц — приложение (акт о внедрении результатов работы в РКК «Энергия», акты о внедрении и использовании результатов диссертационной работы в ряде ВУЗов РФ, свидетельство об официальной регистрации программы дтя ЭВМ), 14 страниц — библиографический список (211 наименований)

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

В главе 1 «Оценки качества алгоритмов и ал1 оритмического обеспечения программных систем» обобщены подходы к оценке качества алгоритмического обеспечения программных систем рассмотрены методы оценки в классической теории алгоритмов, в теории сложности вычислений и специальные модели вычислений для оценки сложности алгоритмов

Исследованы особенности разработки алгоритмического обеспечения в аспекте результатов теории ал1 оритмов, рассмотрены требования к программным средствам и системам, и их алгоритмическому обеспечению (В В Липаев Н А Маркова. Ю М Лисецкий) На основе анализа характеристик качества программных средств и существующих подходов к оценке алгоритмов по эффективности использования ресурсов сделан вывод о необходимости разработки ф\нкций ресурсной эффективно-

сти алгоритмов, учитывающих зависимость ресурсных требований от характеристик множества входов

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

Рассмотрены специальные модели вычислений для оценки сложности алгоритмов алгебраические деревья вычислений, информационные графы для теоретического исследования задач поиска, полиэдральные графы задач (М Бен-Ор, М Ю Мошков, Э Э Гасанов, В Б Кудрявцев, В А Бондаренко)

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

В главе 2 «Основы теории ресурсной эффективности вычислительных алгоритмов» сформулированы основные цели и задачи теории ресурсной эффективности, введена система понятий и обозначений, предложены функции ресурсной эффективности, описан теоретико-множественный подход к определению функции трудоемкости, введены понятия объектного и алгоритмического базисов предложены классификационные признаки и разработаны новые классификации вычислительных алгоритмов

Проведено исследование терминологии в области анализа алгоритмов, и на этой основе введена система понятий и обозначений ресурсных функций и характеристик, ориентированных на задачи анализа ресурсной эффективности вычислительных алгоритмов /А(0) — трудоемкость алгоритма — количество базовых операций в принятой модели вычислений, задаваемых алгоритмом на конкретном

входе О, где ОеВ( — вход алгоритма А, представляющий собой конечное упорядоченное множество из п элементов </,£)., — множество допустимых конкретных проблем задачи, решаемой алгоритмом А Выделим в DA подмножество Д,, состоящее из входов размерности п, тогда /,"(«) — худший случай — наибольшее количество операций, задаваемых алгоритмом А на входах размерности я — лучший случай — наименьшее количество операций,

задаваемых алгоритмом А на входах размерности п —

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

входа D для анализируемой области применения алгоритма В принятых обозначениях временная сложность алгоритма есть асимптотическая оценка в классах функций, определяемых обозначениями О или 0, функции трудоемкости алгоритма для худшего случая — — функция, за-

дающая класс О или

Функция объема памяти У„{0) для входа D определена как функция, задающая максимальное число ячеек памяти модели вычислений, задействованных в ходе выполнения алгоритма По аналогии, для функции объема памяти введены обозначения для лучшего, худшего и среднего случая на различных входах размерности п У*(п),

УЛ{п) Емкостная сложность алгоритма есть асимптотическая оценка в классах функций, определяемых обозначениями О или , функции объема памяти алгоритма для худшего случая — — функция, задающая класс О или 0 ДЛЯ ^"(п)

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

пара асимптотических оценок ресурсных функций 9ф)={0Ыя))Ю(й(и))} или я:М=(0(е1(«»®И«))>, где *(») /;(«)=ОШ). К") у;(п)=о(к(п)) ё\(п) /'(л)-0(£1(л)). М(л) Р,'(л) = в(Л1(я)), где *е{\\ } — обозначение худшего, лучшего и среднего случая ресурсной функции

Проведен анализ ресурсов компьютера требуемых алгоритмом, и на згой базе в рамках стоичосгною подхода предложена функция ресурсной эффективности алгоритмов в виде (п) = Cv V'A (л) + Cf f'A (п) и функция ресурсной эффективности программной реализации в виде 4V(«) = C„, V„XnbCr<m-Vrm{n) + C„-V„{n)+C, 7», где Vm (п) — ресурс оперативной памяти, требуемый под размещение машинного кода, реализующего данный алгоритм, Vram (и) — ресурс оперативной памяти, требуемый алгоритмом под входные, выходные и временные ячейки, массивы и структуры; К, (и) — ресурс оперативной памяти в области стека, требуемый алгоритмом для организации вызова процедур и функций, в том числе рекурсивных вызовов; ТА(п) — требуемый алгоритмом ресурс процессора — временная оценка алгоршма, связанная с /,(и); конкретные значения коэффициентов задают стоимости ресурсов, определяемые условиями применения алгоритма и спецификой программной системы Функция ресурсной эффективности У, (л) может быть определена для лучшего, среднего или худшего случая при использовании соответствующих ресурсных функций

Для выбора рационального алгоритма из множества А - {А, | г -1. m } вводш-ся функция R(n), значением которой является номер алгоритма г R(n) = r,r е{ 1,m = arg min}^ (и)}

На исследуемом сегменте размерностей [л,, п7 \ возможны следующие случаи — либо функция R(n) принимает одинаковые значения

тем самым anropmw с номером к из анализируемою множества Аг является рациональным по функции У, (и) на всем сегменте размерное! ей входа, либо функция R(n) принимает различные значения на [и,, и2] 3 n:,nl е [л,, л2]. /?(л,)/ R{n,), тем самым несколько алгоритмов являются рациональными для различных размерностей входа В этом случае на сегменте п.. | можно выделить подсегменты, в которых значение Я(л,) = const, и реализовать выбор рационального алгоритма, в смысле функции ресурсной эффективности У,(л), адаптивный по размеру входа Таким образом, на основе функции ресурсной эффективности можно выбрать алгоритм, имеющий мини-

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

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

двухмерное пространство. Обозначим через V и Г* ограничения технического задания на максимально допустимый объем оперативной памяти и время выполнения. При условии, что минимальные значения равны нулю, прямоугольник за-

дает область Ж допустимых ресурсных характеристик. На основе расчета компонент функции для значений размерности входа п1,пг,п3,п4 и для различных компью-

теров р\,р2 возможно определение верхней границы размерности задачи в области Ж, что проиллюстрировано на рис. 1.

7-* т

Рис. 1.

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

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

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

где 1А — информационная алгебра модели вычислений, Р — абстрактный процессор (механизм реализации) Информационная алгебра 1Л представляется в виде

где — информационная структура, представляющая собой множество ячеек памяти и ассоциированных с ними посредством нумератора адресов, — множество объектов хранения, как слов фиксированной дчины к в атфавите 5 = {О,1} Ее В*, — сигнатура информационной алгебры, представляющая собой набор из т операций доступа (в частности, штрих операции), записи и чтения к эле-метам множества объектов хранения, размещенным в информационной структуре Механизм реализации • — абстрактный процессор формализован в виде

где ц1 — операция добавления элемента г во множество Е для которой определена функция нумерации ц, Л — механизм реализации, С — множество базовых операций абстрактного процессора Для определения трудоемкости алгоритма с каждой операцией с, последовательно упорядоченной парой, связана операция \fceC с —>(с, Ц1) Пусть А есть запись алгоритма в базовых операциях сеС, вход алгоритма D есть расположение определенных слов из X в определенных ячейках I, тогда механизм реализации, выполняя алгоритм А на входе D, после каждой операции с выполняет связанную с ней операцию р' После останова алгоритма функция трудоемкости определима в виде при условии, что в момент

запуска механизма реализации

Предложен формальный переход от модели вычислений машины с произвольным доступом к памяти к базису операций процедурного языка высокого уровня Для теоретического обоснования такого перехода введены понятия и определения объектного и алгоритмического базисов и определение их <9(1) — эквивалентности, и на этой основе введены базовые операции в алгоритмическом базисе процедурного языка высокого уровня для получения функции тр> доемкости

С целью теоретического исследования возможности повышения временной эффективности алгоритмов введена новая классификация задач, основанная на сравнении теоретической нижней границы временной сложности задачи — (л) и оценки лучшего алгоритма ее решения — Определяется множество F,„, со-

стоящее из функций f,m:

IV Л б V л > 0, /;(«) = £>(/„„(«))}, где /;(л) — функция трудоемкости для худшего случая; Л, — множество алгоритмов, решающих задачу Z ; тогда /»/„(«)= SUP где -< — обозначение асимпто-

-<

тической иерархии функций. Оценка лучшего алгоритма вводится через формальное определение множества алгоритмов Аи ={Лт} как подмножества известных алгоритмов Ая. обладающих минимальной асимптотической оценкой трудоемкости, и выделения во множестве Аи одного алгоритма:

Au={Am\-3AeAR-.ft (я) ■< Д, (я)}, \АМ \ * 1, Ат,„ е Аи,

трудоемкость этого алгоритма обозначается как /А„„(и).

Введены следующие классы задач: класс THCL , как класс задач, для которых

fMm(n) существует, и /,„,„(л)=в(/,ы,*("))■ класс теоретически (по временной сложности) закрытых задач, т. к. существует алгоритм, решающий данную задачу с временной сложностью, равной теоретически доказанной нижней границе. Разработка новых или модификация известных алгоритмов из этого класса может лишь преследовать цель улучшения коэффициента при главном порядке в функции трудоемкости; класс PROP, как класс задач, для которых fMm(п) существует, и /лтЛп)у /мт(п)- Для задач из этого класса возможна разработка алгоритма, обладающего доказанной теоретической нижней границей временной сложности. В случае разработки такого алгоритма данная задача будет переведена в класс THCL-, класс задач ТНОР, как класс задач, для которых оценка /Мш (л) не доказана, а f/miA") у /,(")• ГДС /,(") — оценка тривиальной нижней границы сложности задачи. Для задач этого класса имеет место теоретическая проблема либо доказательства оценки fMm (п), переводящего задачу в класс PROP, либо доказательства глобальной оптимальности наиболее эффективного из существующих алгоритмов, переводящего задачу в класс THCL, либо возможна разработка алгоритма с оценкой f„{n).

Доказаны три леммы и теорема (совместно с В. А Головешкиным) об угловой мере асимптотического роста функций, составляющие теоретическую базу новой классификации алгоритмов по временной (вычислительной) сложности.

Теорема Пусть дана функция / = /(*), монотонно возрастающая, и lim/(л) = со.

X—КС

Определим меру тг{/(х)) асимптотического (на бесконечности) роста функции fix): «(/(*)) = *-2-arctgM.

dz

где R = lim —, параметрически заданная функция ф) определена в виде i-*50 as (s-a)

/*) N , а функция Нх) задана в виде h(x) = 1п(/(*))+——х, z = arctg[—— ], 1п(/(дг))+1пде

UmJ

тогда если

1) f(x) = е*(1 + К*)), где 1>0, у(х) = о(1), у\х) = о{1), при л -> оо, ю iz'ß<iz(j(x))<x\

2) /(*) = *1(1 + yW), где у(х) = (<1),у'(х) = о(1), г^Ь 0(1), при х->«>, то О <*(/(*))< я/2;

3) /(*) = Inто *(/(*)) = я/2.

Вид функции z(s) для полинома fix) = х1 и экспоненты fix) - е* приведен на рис. 2.

0,000

0,020 0,040

0,080 ОДОО

-j-x-x

■ f-cxpfi)

-г s

Рис.2

На основе данной теоремы определяются следующие множества функций'

FZ = {fix) | fix) ■<xt,Vk> 0 } с мерой ж (/(;)) = 0,

FP = {f{x) 13 к > 0: fix) = © (хк)}, для которого 0 < тг(/(*)) < я/2,

fl = {f(x)\x" -< f(x)-< e", Vi>О, V A>0 } с мерой ir(f(x)) = гг/2, га = {/(л) 13 x > О: f(x) = е(е")}, ДЛЯ которого ж/2 < ж(/(х)) < ж, ff = {f(x)\е" -< f(x), V i > 0 } с мерой *(/(*)) = *

Укажем одно из свойств введенной меры: ж(х)+ ж(е:')= ж. На базе введенных множеств функций предложена новая классификация алгоритмов по сложности функции трудоемкости (временной сложности):

1. Класс згО (пи ноль) — алгоритмы, функции трудоемкости которых принадлежат множеству fz и имеют меру ноль: жо={л\ («))= 0о Л* (")е ь

2. Класс жр — класс полиномиальных алгоритмов, функции трудоемкости которых принадлежат множеству fp: жр = {л10<ж{/а(п))< г/2 = 0о/а(п)е ff }> доказано утверждение о том, что введенный класс алгоритмов жр является подклассом алгоритмов, определяющих класс задач Р в теории сложности вычислений;

3. Класс kL — класс субэкспоненциальных алгоритмов — функции трудоемкости принадлежат множеству fl\ nl = {а \ х(/а(п))-ж/2 о f'a(n)e fl }. Этот класс образуют алгоритмы с более чем полиномиальной, но менее чем экспоненциальной сложностью;

4. Класс жЕ — класс экспоненциальных алгоритмов — функции трудоемкости принадлежат множеству fe : же ~{а\ж/2< х[/'а(п))<к о f'a(n)£ fe };

5. Класс жР — класс надэкслоненциальных алгоритмов — функции трудоемкости принадлежат множеству ff: жЕ = {а \ n{f'a(n)}= ж о f'a{n) е ff }.

Проведено исследование влияния характеристических особенностей множества исходных данных (количества элементов, их значений и порядка) на функцию трудоемкости. Выделены количественная — /„(л) и параметрическая — gp(D) составляющие в функции трудоемкости, при этом рассмотрены случаи, когда функция /л(п, D) предсгавима как мультипликативная fA(n, D) = f„(n)• g'p(D) или аддитивная /л(п, D) = fjn)+ g*(D) композиция этих составляющих. В силу конечности множества Dr существует худший случай для функций р'(Л) и g*(D) Гоответствуюшие функции обозначены через

В зависимости or влияния разтичных характеристик множества исходных данных на функцию трудоемкости алгоритма пред южена новая классификация имеющая практическое значение для ресурсного анализа алгоритмов

1 Класс N — класс количественно-зависимых по трудоемкости алюритмов, функция трудоемкости которых зависит только от размерности конкретного входа g» = 0 => g'(n):= 1 => />, D) = /„(и), при этом /;{«) = U (") - /»•

2 Класс PR — класс параметрически-зависимых по трудоемкости алгоритмов, трудоемкость которых определяется конкретными значениями всех или некоторых элементов из входного множества D /„ {п) = const = с, => fjn, D) - с g (п)

3 Класс A PR — класс количественно-параметрических по грудоемкости алгоритмов Это широкий к часе алгоритмов, т к в ботьшинстве случаев функция грудоемкости зависит как от длины входа, так и от значений элементов множества D В этом случае fn(n)* const, g'(n)*\, ft(n)* fA(n, D) = /„(и) g'(n) или

/>>a)=/»+g+(»)

В к iacce NPR выделены дополнительные подклассы алгоритмов отражающие степень влияния g'{n) на /А(п, D) NPRL — со слабым влиянием, NPRH — с сильным влиянием и подклассы по характеристическим особенностям множества DA, а именно подкласс NPRS с порядково-зависимой функцией трудоемкости и подкласс NPRV с функцией трудоемкости, сильно зависящей от значении элементов в D, при этом g'{n)> /Ди)

Проведен анализ алгоритмов класса NPR с точки зрения изменения функции трудоемкости при изменении размерности входа и при обработке различных входов фиксированной размерности Введены понятия информационной и размерностной чувствительности функции трудоемкости алгоритмов, предтожены их количественные меры Количественная мера информационной чувствительности определена в виде §,(«) = V(n) Rf,(n), 0<8»<1,1де

V(n)=*JM/f », 0 < К(л) < 1, а (п) — среднеквадратическое отклонение функции трудоемкости, как дискретной случайной величины, при фиксированной размерности входа, RN(n) — нормированный размах варьирования, определяемый по формуле

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

+ V}

/»

где * — обобщенное обозначение функции трудоемкости для худшего, среднего и лучшего случаев

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

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

класс и/ Малочувствительные алгоритмы 0 < Ь*(л)< и V« > 1, класс п2 Слабочувствительные алгоритмы л°(л)= к п ', V л > 1, fc > I, класс пЗ Чувствительные алгоритмы

я-'н hm 8„ (л) - 0,

л->а

класс п4 Сильночувствительные алгоритмы 8,1(п)=соп?1 или lim Ъ'„(п)'-,Х:

Л-> СО

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

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

класс;/ Нечувствительные алгоритмы 8((л) = 0, класс ¡2 Слабочувствигельные алгоритмы 0 < 5,(л) < 0,05, класс /3 Чувст вительные алгоритмы 0,05 < 6, (л) < 1/3,

класс U Сильночувствительные алгоритмы 1/3 < 5((п) < 1,00

Показано, что на основе размерностной чувствительности алгоритмов по функции трудоемкости могут быть допочнительно обоснованы введенные подклассы алгоритмов в количественно-параметрическом классе (класс WR)

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

В главе 3 «Функции трудоемкости вычислительных алгоритмов: методы получения и сравнительный анализ» рассматриваются методы получения функций трудоемкости в процедурной и рекурсивной реализациях алгоритмов, рассматривается методика анализа ресурсных функций на конечном интервале (на примере функции трудоемкости) и проводится исследование областей эквивалентной ресурсной эффективности алгоритмов.

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

Для анализа этого алгоритма введены специальные функции: задающая количе-

ство бит в двоичном представлении числа, и задающая количество единиц в

этом представлении. Для алгоритма сортировки вставками

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

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

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

явление количества внутренних, порождающих рекурсию, вершин дерева — Vr(п) и кочичества листьев дерева — V (и), связанных с остановом рекурсии, и анализ трудоемкости в этих вершинах В общем виде трудоемкость определяется по форм\ ле

к 1

где v,, к = 1, КДп) — нумерация вершин, g{vt ) — трудоемкость алгоритма в вершине v,, /г — трудоемкость алгоритма на реализацию одного рекурсивного вызова, / — трудоемкость при останове рекурсии в одной вершине Приведен пример применения разработанного метода для получения функции трудоемкости рекурсивного алгоритма сортировки слиянием — fA(n)=l& п 1п(л)+92 л - 71

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

п(а, b) = arctg ~ - arctg-, где а = fin,), Ь = g(«,) Ь а

На основании этой меры введены следующие соотношения между функциями и соответствующие обозначения в анализе ресурсных функций на конечном интер-

я я

вале исследуемых значении п относительно принятого порога р -— < <р < —

Л") = <4(?("))>если min{jr(/(n),g(n))}>(p \/ne(a,b), f(n) = 0v(g(n)),ecm max|{^(/(«),g(«))jk<{. Vne(a,b), /(")=<?,(«(")),если max{ic(f(n\ g(n))}S Vne(a,é) Разработанная методика анализа ресурсных функций (на примере функции трудоемкости) на конечном интервале позволяет выявить алгоритмы рациональные в определенных областях размерностей входа Поскольку при значениях n(fA(x), g»), близких к нулю, алгоритмы могут быть использованы эквивалентно, то ведено понятие об частей эквивалентной ресурсной эффективности — -области, и показано, что возможно существование нескотьких таких обпастей на рассматриваемом конечном интервале размерностей Введено определение (-)ф-обтасти в рамках предложенной меры по отношению к функциям /,(*)« g,, (х) в предположении

о переходе к непрерывности аргумента (от п к при пороге ср на ишервале (а, Ь) существует 0t-область /, (х) = 0, ,(.г)), ec.iи max, {x(f,{x\ £,(.*))} <Ф V*e(a,b) Если 0,-область существует, то она может быть как зависима, так и не зависима от значения порога <р, при этом независимая (по q>) ©ф-область существует, если функции имеют на интервале (a, b) либо точки пересечения, либо

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

Ш 8л(п) Мп)

/М-вМп))

Рис 3

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

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

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

Проведен теоретический анализ влияния размерности задачи на экспериментальное среднее время выполнения обобщенной базовой операции, показано, что такое влияние связано с различием средних времен обобщенных операций для главного и асимптотически более «слабых» аддитивных компонентов функции трудоемко -сти, а само среднее время определяется по формуле

где к — количество аддитивных компонентов функции /л{п), а < — среднее время

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

Предложен метод определения коэффициентов функции 1тл{п) на основе

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

а = а Р = ак]/а,— отношение коэффициентов аддитивных компонентов

функции Примерный вид графика функции в зависимости от пара-

метра а приведен на рис 4

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

функции (опДя). Временная оценка получается по формуле Тл(п) - /г,„/(и) • /,(«)■ Полученные экспериментальные результаты по алгоритмам сортировки показывают, что использование зависимости («Дл) позволяет уменьшить ошибку прогноза с 5% до 0,6% в исследованном диапазоне размерностей входа

Рис. 4.

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

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

В системе конечно-элементного анализа «Термоупругость 3D» на основе предложенных рациональных ресурсно-адаптивных алгоритмических решений по компоненту формирования глобальной матрицы удалось снизить в среднем время счета для тепловых нестационарных задач на 20-30 минут при общем расчетном времени порядка 3-5 часов. Предложен ресурсно-адаптивный алгоритм формирования гло-

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

3456789ЮТ11213'И1516

Рис. 5.

Сформулирована задача упаковки с динамической внутренней 1раницей объема для рациональной организации данных аналитического компонента индивидуальных информационных систем, разработаны точный и эвристический алгоритмы ее решения Постановка задачи связана с необходимостью хранения ан&титической БД в ограниченном объеме памяти. Поскольку разным запросам требуется наличие данных, агрегированных по разным измерениям, то часть выделенной памяти можно отвести под хранение квазистатического раздела многомерной БД. Оставшуюся память можно использовать для построения динамического раздела многомерной БД, хранящего агрегированные данные, использованные в последнем «редком» запросе, который не мог быть удовлетворен за счет информации квазистатического раздела. Таким образом, возникает задача разбиения доступного объема ресурса общей памяти V, выделенного для хранения аналитической БД, и размещения в квазистатическом разделе агрегированных данных в соответствии со статистикой запросов.

Математическая постановка имеет вид- максимизировать линейную форму

■ р, ->тах, 1де X - {jc,}, х, е {0,1} — вектор упаковки,р, — частоты

запросов, yt — объекты упаковки, при выполнении следующего динамиче-

ского условия:

N

-v, + шах{(*, + l)mod2-v, } < V,

которое не является типичным для классической задачи оптимальной упаковки Эта задача получила в работе название — задача оптимальной упаковки с динамической внутренней границей объема

Показано, что ее точное решение может быть получено на основе решений классической задачи упаковки для всех объемов от У1 = У шах {V} до

У2 = V - ш т {V} ( = 1, N Обозначим вектор оптимальной упаковки для объема V

элементами уг1 = \,к, через Х\ и рассмотрим специальную функцию ¿{у),

задающую остаток свободного пространства в оптимально упакованном объеме V

V

с1(\1)-\V, х" еXI, и функцию Жу), задающую необходимый объем для

размещения максимального по V, неупакованного элемента Л(у)=шах{у}, ( х"=0 Оптимальное решение задачи упаковки с динамической внутренней границей объема задается тем вектором X*, для которого значение V* удовлетворяет условию

| кг-+ ¿(V-) **(/) .

Получена оценка вычислительной сложности этого алгоритма — разработаны рекомендации по определению рационального дискрета объема, предложен быстрый (со сложностью 0(ы 1пЛ')) эвристический алгоритм ее решения и даны рекомендации по рациональному выбору алгоритмов на основе анализа статистики обращений к аналитическому компоненту индивидуальной информационной системы

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

Л N

Рч(Х)=^х Р "♦"•ах, при ^х V < У,

< I -I

на заданном множестве типов грузов У = {у }, |У| = А/, у = ¡V ,с},; = 1, N в объеме V Характеристический вектор X = {х} описывает количество эхментов типа у в обь-

еме У Точное решение задачи может быть получено методом динамического программирования, допускающим рекурсивную и процедурную реализацию

Проведено исследование табличного и рекурсивного алгоритмов получения точного решения задачи, реализующих метод динамического программирования. Поскольку функции трудоемкости алгоритмов зависят от значений Л'.К,^, ,.,ул (алгоритмы принадлежат классу ЛТО), то предлагается ввести параметр к - У/у, харак-

теризующий количество грузов среднего объема V = 1/М ■ £ V,, размещаемых в У.

ы

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

/Лт№,У,к) = \3,5-У-Ы1 + 4,5-Ы-У к + 2\,5У N + 0,5-Аг1 -16-К +10,5-ЛГ-9 и рекурсивного (р(*) — поправочная функция):

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

Сравнительный анализ позволяет построить семейство (по У) разграничивающих кривых, определяющих предпочтения выбора алгоритма по функции трудоемкости. Вид функций трудоемкости и кривая разграничения рационального выбор: (для У = 10000) приведены на рис. 6 и рис. 7 соответственно.

рекур теор

Рис. 6.

Рис 7.

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

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

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

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

В Приложении приведены акты о внедрении и использовании результатов диссертационной работы в программных системах и в учебном процессе ряда ВУЗов Российской Федерации

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

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

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

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

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

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

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

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

6 Разработан метод прогнозирования временной эффешивности программных реализаций алгоритмов на основе функции трудоемкости и функциональной зависимости среднего времени выполнения обобщенной базовой операции от длины входа

7 На основе методов и методик теории ресурсной эффективности разработаны комбинированные ресурсно-эффективные алгоритмы, входящие в сложные программные системы эффективный комбинированный алгоритм решения задачи упаковки с динамической внутренней границей объема для аналитического компонента индивидуальных информационных систем, ресурсо-эффективный алгоритм поиска по ключу в структуре хранения разреженной глобальной матрицы для программной системы конечно-элементного анализа «Термоупругость 3D» и рекомендации по выбору рациональных алгоритмов на конечном интервале размерностей входа.

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

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

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

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

2 Ульянов М В Дополнение к книге Дж Макконелла «Основы современных алгоритмов» — М Издательство «Техносфера», 2004 С 303-366

3 Ульянов М В Классификация алгоритмов в целях практического анализа // Информационные технологии 2003 № 11 С 29-36

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

5 Александров А Е , Ульянов М В Общие подходы к повышению ресурсной эффективности алгоритмического обеспечения систем конечно-элементного анализа // Автоматизация и современные технологии 2004 № 9 С 18-24

6 Александров А Е , Востриков А А, Ульянов М В Эффективные алгоритмы формирования глобальной матрицы для комплекса конечно-элементного анализа // Автоматизация и современные технологии 2004 № 10 С 32-36

7 Брейман А Д, Ульянов М В Рациональная организация данных аналитического компонента в индивидуальных информационных системах с использованием алгоритма упаковки с динамической внутренней границей объема // Автоматизация и современные технологии 2004 № 12 С 17-22

8 Ульянов М В Учет специальных требований к алгоритмическому обеспечению в комплексной оценке качества ачгоритмов // Вестник Рязанской радиотехнической академии 2004 № 2 С 25-32

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

10 Ульянов М В Теоретико-множественный подход к определению функций трудоемкости алгоритма // Информация и безопасность 2004 № 2 С 53-58

11 Михайлов Б М, Ульянов М В Инструментальные средства для исследования эффективности алгоритмов концепция и основные принципы построения // Информационные технологии 2005 № 2 С 54-57

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

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

14 Ульянов М В Определение объектного и алгоритмического базисов // Программное и информационное обеспечение систем различного назначения на базе ПЭВМ Межвузовский сборник научных трудов — М МГАПИ, 2000 Вып 3 С 159 161

15 Ульянов М В Комплексный критерий оценки качества алгоритмов // Программное и информационное обеспечение систем различного назначения на базе ПЭВМ Межвузовский сборник научных трудов / Под ред д т н, проф Михайлова Б М — М МГАПИ, 2002 Вып 5 С 146-148

16 Ульянов М В Функция р,(и) и ее применение для анализа алгоритма быстрого возведения числа в целую степень // Программное и информационное обеспечение систем различного назначения на базе ПЭВМ Межвузовский сборник научных трудов /1 Юд ред д т н, проф Михайлова Б М — М МГАПИ, 2003 Вып 6 С 253-255

17 Ульянов MB Основные проблемы организации экспериментального исследований и генерации входов алгоритмов // Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ Межвузовский сборник научных трудов / Под ред д т н, проф Михайлова Б М — М МГАПИ, 2004 Вып 7 С 267-269

18 Ульянов М В Классификация вычислительных алгоритмов по характеристическим особенностям множества исходных данных // Современные технологии в задачах управления, автоматики и обработки информации Труды XI международного научно-технического семинара (сентябрь 2002 Алушта) — М МГАПИ 2002 С 397-399

19 Головешкин В А, Ульянов М В Уыовая мера асимптотического роста и разграничение функций сложности алгорш мов для классов Р и ЕХР // Новые информацион-

ные технологии Сборник трувдв VI Всероссийской научно-технической конференции (Москва. 23-24 апреля 2003) В 2 т / Под общ ред А П Хныкина — М МГАПИ, 2003 Т 2 С 88-93

20 Ульянов М В Классы открытых и закрытых задач и теоретическая нижняя граница временной сложности // Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права Научные труды VI Международной научно-практической конференции (Сочи, октябрь 2003) Книга «Информатика» — М МГАПИ, 2003 С 246-250

21 Ульянов М В Основные задачи сравнительного анализа вычислительных алгоритмов // Современные технологии в задачах управления, автоматики и обработки информации Труды XIII международного научно-технического семинара (сентябрь 2004 , Алушта) — М Издательство МГУ 2004 С 465-467

22 Головешкин В А, Ульянов М В Информационная чувствительность функции трудоемкости алгоритмов к входным данным // Новые информационные техно чогии Сборник трудов VII Всероссийской научно-технической конференции (Москва, 2425 марта 2004) /Под общ ред А П Хныкина —М МГАПИ 2004 С 19-26

23 Ульянов М В Типизация алгоритмов по информационной чувствительности функции трудоемкости к входным данным // Новые информационные техно тогии Сборник трудов VII Всероссийской научно-технической конференции (Москва, 24-25 марта 2004) / Под общ ред А П Хныкина — М МГАПИ, 2004 С 48-52

24 Ульянов М В Сравнительный анализ алгоритмов в многомерном пространстве характеристик на основе комплексной оценки качества // Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права Научные труды VII Международной научно-практической конференции (Сочи октябрь 2004) — М МГАПИ, 2004 С 223-227

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

26 Утьянов М В К тарификация алгоритмов по их трудоемкости // Программное и информационное обеспечение систем разтичного назначения на базе ПЭВМ Межвузовский сборник научных трудов — М МГАПИ, 2000 Вып 3 С 157-159

27 Ульянов М В Мера 71^) и интервальный анализ функций // Программное и информационное обеспечение систем различного назначения на базе ПЭВМ Межвузовский сборник научных трудов / Под ред д т н , проф Михайлова Б М — М МГА-ПИ,2002 Вып. 5 С 143-146

28 Ульянов М В Этапы решения проблемных задач на ЭВМ в аспекте применения аппарата анализа алгоритмов // Программное и информационное обеспечение систем различного назначения на базе ПЭВМ Межвузовский сборник научных трудов / Под ред д т н , проф Михайлова Б М — М МГАПИ, 2003 Вып 6 С 256-258

29 Ульянов М В Методика расстановки счетчика элементарных операций для экспериментального определения функции трудоемкости // Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ Межвузовский сборник научных трудов / Под ред д т н, проф Михайлова Б М — М МГА-ПИ, 2004 Вып 7 С 264-266

30 Ульянов М В Планирование экспериментального исследования алгоритма по функции трудоемкости // Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ Межвузовский сборник научных трудов / Под ред д т н , проф Михайлова Б М — М МГАПИ, 2004 Вып 7 С 270-275

31 Ульянов М В, Шептунов М В. Математическая логика и теория алгоритмов, часть 2 Теория алгоритмов — М МГАПИ, 2003 — 80 с

32 Ульянов М В, Родина Н В Разработка эффективных алгоритмов Учебное пособие — М МГАПИ, 2004 —112 с

33 Ульянов М В, Беседин А В, Кондратьева Т В Система экспериментального анализа алгоритмов // Свидетельство об официальной регистрации программы для ЭВМ № 2004612709 от 20 12 2004

ЛР № 020418 от 08 октября 1997 г.

Подписано к печати 25.02.2005 г. Формат 60x84. 1/16 Объем 2,25 п.л. Тираж 100 экз. Заказ № 9

Московская государственная академия приборостроения и информатики

107996, Москва,ул. Стромынка, 20

05.11 - OS. /J

953

ВВЕДЕНИЕ.

ГЛАВА 1 ОЦЕНКИ КАЧЕСТВА АЛГОРИТМОВ И АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ ПРОГРАММНЫХ СИСТЕМ .12 Введение.

1.1 Общие подходы к оценке качества алгоритмического обеспечения программных систем.

1.2 Методы оценки алгоритмов в классической теории.

1.3 Оценки алгоритмов в теории сложности вычислений.

1.4 Специальные модели вычислений для оценки сложности алгоритмов.

2.1 Основные задачи и элементы теории ресурсной эффективности вычислительных алгоритмов.51

2.2 Операции в моделях вычислений и теоретико-множественный подход к определению функции трудоемкости.73

2.3 Теоретические основы классификации алгоритмов.86

2.4 Заключение.133

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

Введение.135

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

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

3.3 Сравнительный анализ алгоритмов по ресурсным функциям.175

3.4 Заключение.191

ГЛАВА 4 ВРЕМЕННАЯ ЭФФЕКТИВНОСТЬ ПРОГРАММНЫХ

РЕАЛИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ.192

Введение.192

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

4.2 Метод прогнозирования временной эффективности программных реализаций алгоритмов на основе функции трудоемкости.203

4.3 Заключение.218

ГЛАВА 5 ПРИМЕНЕНИЕ ЭЛЕМЕНТОВ ТЕОРИИ РЕСУРСНОЙ ЭФФЕКТИВНОСТИ ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ ВЫБОРА РАЦИОНАЛЬНЫХ АЛГОРИТМОВ.219

Введение.219

5.1 Рациональные ресурсно-адаптивные алгоритмические решения по компоненту формирования глобальной матрицы для программной системы «Термоупругость 3D».220

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

5.3 Сравнительный анализ ресурсной эффективности алгоритмов решения классической задачи одномерной упаковки.246

5.4 Основные принципы построения инструментальных средств для исследования ресурсной эффективности алгоритмов.266

5.5 Заключение.283

ЗАКЛЮЧЕНИЕ.286

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.289

ПРИЛОЖЕНИЕ.303

ВВЕДЕНИЕ

Актуальность темы

Актуальность исследований в области ресурсной эффективности вычислительных алгоритмов определяется, прежде всего, рядом существующих сегодня тенденций развития наукоемких технологий в области программных средств и систем и особенностями решаемых проблемных задач. Практически значимыми и актуальными в наукоемких технологиях становятся сегодня сложные задачи большой размерности и вычислительной сложности, программные системы обработки потоков задач и обслуживания потоков запросов со значительными объемами обрабатываемых данных, эффективные программные средства для вычислительных систем, работающих в режиме реального времени в условиях ограниченных вычислительных ресурсов. Примерами могут служить программные системы, использующие методы конечно-элементного анализа для задач расчета деформаций и тепловых полей в сложных объектах [3], программы моделирования сложных систем [33, 104, 130], программное обеспечение информационно-телекоммуникационных систем и компьютерных сетей [26], в том числе информационно-поисковые системы Интернета и др. Актуальность этой тематики отражена и в приоритетных направлениях развития науки России — в перечне критических технологий РФ.

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

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

В настоящее время при создании программных средств и систем, выборе их организационно-функциональной структуры отсутствуют количественные оценки качества алгоритмического обеспечения, определяющие выбор вычислительных алгоритмов в области реального множества входов. Разработка эффективных алгоритмических решений всегда привлекала внимание ученых и программистов. Разнообразные алгоритмические решения получены для целого ряда задач в теории графов [27, 52, 75, 101, 150, 151, 161, 172, 173], комбинаторике [73, 97, 162], линейном и целочисленном программировании [120, 128, 131, 157, 160], информационном поиске [35, 149, 170], и т. д. Активно разрабатываются направления, связанные с математическим и алгоритмическим обеспечением сжатия изображений и звука [154], приближенного решения NP - трудных задач [83, 154]. В результате сегодня известно достаточно большое количество разнообразных по своим характеристикам вычислительных алгоритмов решения актуальных практических задач. При разработке алгоритмического обеспечения программных средств и систем возникает практическая необходимость исследования, оценки и сравнительного анализа ресурсной эффективности различных вычислительных алгоритмов, предназначенных для решения некоторой задачи в области множества входов, характеристики которых определяются спецификой области их применения. Результаты такого сравнительного анализа и исследования позволяют обосновать, в принятой системе количественных оценок, выбор рациональных ресурсно-эффективных алгоритмов и сформулировать рекомендации по их совершенствованию.

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

Состояние проблемы

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

Несмотря на интенсивные исследования в области классической теории алгоритмов, и асимптотического анализа сложности вычислительных алгоритмов некоторые вопросы остаются нерешенными. В первую очередь это касается как вопросов сравнительного анализа ресурсной эффективности алгоритмов в реальном диапазоне длин входов, где результаты асимптотического анализа не всегда могут быть использованы, так и методов получения теоретических оценок ресурсной эффективности в этих диапазонах в виде функциональных зависимостей. Отметим в данном контексте работы В.В. Липаева [71,72] по системе оценок качества программных средств и систем, теоретические результаты по анализу задач информационного поиска, полученные Э.Э. Гасановым и В.Б. Кудрявцевым [34, 35] в Московском государственном университете, исследования, проводимые в

Томском политехническом университете по экспериментальному определению временной эффективности алгоритмов (под руководством В.З. Ямпольского) [22], в Ярославском государственном университете по полиэдральным графам задач (В.А. Бондаренко) [23, 24].

Тем не менее, большинство публикаций по тематике практического исследования алгоритмов свидетельствуют о том, что разработчики алгоритмического обеспечения ограничиваются в основном экспериментальным исследованием временной эффективности программных реализаций претендующих алгоритмов [22, 49, 89, 115, 126, 129]; теоретические исследования по этим вопросам представлены немногочисленными работами.

Объект исследования

Объектами исследования диссертационной работы являются вычислительные (компьютерные) алгоритмы в рамках модели вычислений машины с произвольным доступом к памяти (RAM) в аспекте их ресурсной эффективности при ограничениях, налагаемых особенностями и спецификой их применения в разрабатываемых программных средствах и системах.

В работе под термином вычислительный алгоритм понимается реализуемый на ЭВМ алгоритм (компьютерный алгоритм), соответствующий RAM модели вычислений, под ресурсной эффективностью алгоритма — его временная эффективность и ресурсоемкость, определяющие соответствующие показатели качества программных средств (ГОСТ 28195).

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

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

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

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

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

3. Возможности использования теоретических и практических результатов работы в учебном процессе ВУЗов в дисциплинах «Теория алгоритмов», «Разработка эффективных алгоритмов», как в лекционных курсах, так и для проведения практических и лабораторных работ.

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

На основе результатов диссертационного исследования разработана «Система экспериментального анализа алгоритмов», зарегистрированная в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (№ 2004612709 от 20.12.04). Практически значимые методы и методики, предложенные в диссертационной работе, составляют основу для выполнения научно-исследовательской работы «Разработка методов получения вычислительных алгоритмов и оценки их трудоемкости» (№ госрегистрации 01.2.00410094), выполняемой в МГАПИ по заданию Министерства образования РФ. Теоретические и практически значимые результаты работы внедрены в учебный процесс Санкт-Петербургского государственного университета (факультет прикладной математики — процессов управления), Рязанской радиотехнической академии, Московского автодорожного института (технический университет), Московской государственной академии приборостроения и информатики. Использование результатов диссертационной работы при разработке программных систем и в учебном процессе подтверждено актами о внедрении.

Основные результаты, выносимые на защиту:

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

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

3. Ресурсно-эффективные комбинированные алгоритмы в составе алгоритмического обеспечения сложных наукоемких программных систем, разработанные на основе предложенных методов и методик.

Апробация работы

Основные положения и результаты диссертационной работы докладывались на международных и всероссийских конференциях и семинарах: XI Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 2002 г.; VI Всероссийской научно-технической конференции «Новые информационные технологии», Москва, 2003 г.; VI Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2003 г.; VII Всероссийской научно-технической конференции «Новые информационные технологии», Москва, 2004 г.; XIII Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 2004 г.; VII Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2004 г.; VI Международном симпозиуме «Интеллектуальные системы», Саратов, 2004 г., научных семинарах кафедр «Персональные компьютеры и сети» под рук. Б.М. Михайлова и «Управление и моделирование систем» под рук. С.Н. Музыкина Московской государственной академии приборостроения и информатики.

Основные результаты работы

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

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

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

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

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

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

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

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

7. На основе методов и методик теории ресурсной эффективности разработаны комбинированные ресурсно-эффективные алгоритмы, входящие в сложные программные системы: эффективный комбинированный алгоритм решения задачи упаковки с динамической внутренней границей объема для аналитического компонента индивидуальных информационных систем, ресурсо-эффективный алгоритм поиска по ключу в структуре хранения разреженной глобальной матрицы для программной системы конечно-элементного анализа «Термоупругость 3D» и рекомендации по выбору рациональных алгоритмов на конечном интервале размерностей входа.

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

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

Перспективы развития исследований

Предложенные в работе основы теории ресурсной эффективности вычислительных алгоритмов могут быть развиты в части разработки новых методов получения ресурсных функций, их сравнительного анализа и обоснования выбора рациональных алгоритмов на конечном интервале длин входов. С точки зрения автора представляют интерес следующие направления развития исследований по теории ресурсной эффективности: обоснование выбора рациональных аппаратных средств для реализации программных систем на основе анализа компонентов их алгоритмического обеспечения по показателю среднего тактового времени выполнения обобщенной базовой операции; детальный анализ алгоритмов, не входящих в класс PSPASE, с целью получения оценок их емкостной сложности и функции объема памяти; расширение разработанных методов получения ресурсных функций программных реализаций алгоритмов на объектно-ориентированную технологию программирования, где особый интерес представляет оценка вычислительной и емкостной сложности доступа к методам объектов; исследование возможности модификации аппарата марковских случайных процессов [60], используемого в настоящее время для получения численных значений трудоемкости алгоритма в среднем, с целью получения функциональной зависимости трудоемкости от длины входа; применение методов интервального анализа [5] для получения областей эквивалентной ресурсной эффективности алгоритмов с учетом их информационной чувствительности; применение предложенного аппарата анализа ресурсной эффективности для исследования параллельных алгоритмов и их реализаций в различных моделях параллельных вычислений.

ЗАКЛЮЧЕНИЕ

1. Авен О.И., Гурин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. — М.: Наука, 1982. — 231 с.

2. Азаров А.В. Анализ распределения ресурсов программного обеспечения для моделирования нестандартных систем управления // Тезисы док. III Всероссийской научно-технической конференции «Будущее технической науки» — Нижний Новгород, 2004.

3. Александров А.Е. Эволюционная методология разработки и сопровождения математического и программного обеспечения технических систем. — М.: Машиностроение, 2001. —195 с.

4. Александров А.Е., Катков Р.Э. Параметрическая оптимизация технических объектов на основе базового варианта с использованием программной системы «Термоупругость-ЗБ» // Информационные технологии. 2002. № 9. С. 21-24.

5. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления — М.: Мир, 1987. —360 с.

6. Алферова З.В. Теория алгоритмов. — М.: Статистика, 1973. — 163 с.

7. Амамия М., ТанакаЮ. Архитектура ЭВМ и искусственный интеллект: Пер. с японск. — М.: Мир, 1993. — 400 с.

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

9. Андреева К.Г., Никитов С.А. Оптимизация использования сырья в задаче линейного раскроя // Информационные технологии. 2003. № 11. С. 24-29.

10. АнишинН.С., Булатникова И.Н., ГершунинаН.Н. САРП алгоритмического обеспечения микропроцессорных систем // Новые информационные технологии: Сборник трудов VI Всероссийской научно-технической конференции: В 2 т. — М.: МГАПИ, 2003. Т. 1. С. 197-201.

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

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

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

14. Барский А.Б., Шилов В.В. Оптимизация ветвления при решении задач сортировки на процессоре EPIC-архитектуры // Информационные технологии. 2005. № 1.С. 26-34.

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

16. БеллманР., Дрейфус Р. Прикладные задачи динамического программирования: Пер. с англ. — М.: Наука, 1965. — 457 с.

17. Белов В.В. Алгоритмические методы повышения верности информации в распределенных информационно-управляющих системах / Под ред. Л.П. Коричнева. — М.: Радио и связь, 1999. — 238 с.

18. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. В. С. Зарубина, А.П. Крищенко. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. —744 с.

19. Березняцкий А.В. Интеллектуализация конструирования информационных систем на базе адаптивных агентных моделей // Автореферат дисс. . кандидата технических наук. — Томск, 2004. — 19 с.

20. Бондаренко В.А. О сложности дискретных задач (http: //edu.yar.ru/russian /pedbank/ sor-pro/bondarenko).

21. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. —Ярославль: Ярославский госуниверситет, 1995. — 126 с.

22. Брейман А.Д. Функциональные особенности современных систем автоматизированного администрирования баз данных. // Научные труды IV Всероссийской конференции «Новые информационные технологии». — М.: МГАПИ, 2003. С. 71-73.

23. Бройдо В.Л. Вычислительные системы, сети и телекоммуникации. — СПб.: Питер, 2002. — 688 с.

24. БурдоновИ.Е. Обход неизвестного ориентированного графа конечным роботом // Программирование. 2004. № 4. С. 11-34.

25. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд. / Пер. с англ. — М.: Издательство Бином, — СПб.: Невский диалект, 1999. — 560 с.

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

27. Ведерников Ю.В., Сафронов В.В. Оптимизация сложной технической системы по совокупности критериев, заданных интервалами значений // Информационные технологии. 2000. № 8. С. 16-22.

28. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. — М.: МЦНМО, 1999. — 128 с.

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

30. Галанин М.П. Компьютерное моделирование в задачах конвертирования электромагнитной и кинетической энергии // Информационные технологии и вычислительные системы. 2003. № 1-2. С. 112-127.

31. Гасанов Э.Э. Оценки сложности одного метода решения задачи включающего поиска // Дискретная математика. 2000. Т. 12, № 2. С. 118-139.

32. Гасанов Э.Э., Кудрявцев В.Б. Теория хранения и поиска информации. — М.: Физматлит, 2002. — 288 с.

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

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

35. ГлушковВ.М., Цейтлин Г.Е., Ющенко E.J1. Алгебра. Языки. Программирование. — Киев: Наукова думка, 1978. — 318с.

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

37. Голубятников И.В. Основные принципы проектирования и применения мультимедийных обучающих систем. — М.: Машиностроение, 1999. — 320 с.

38. Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов вузов. — М.: Высш. шк., 1986. — 311 с.

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

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

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

42. Гулд X., Тобочник Я. Компьютерное моделирование в физике: в 2 частях. Часть 2: Пер. с англ. — М.: Мир, 1990. — 400 с.

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

44. ДебеловВ.А. Разработка технологических систем машинной графики // Автореферат дисс. доктора технических наук. — Новосибирск, 2003. — 36 с.

45. Дейт К.Д. Введение в системы баз данных. — 7-е изд.: Пер. с англ. — М.: Вильяме, 2001. — 1072 с.

46. Диденко С.В. Разработка алгоритмического и программного обеспечения системы сопровождения подвижных объектов // Автореферат дисс. кандидата технических наук. — Томск, 2004. — 20 с.

47. Долгов Ю.А. Статистическое моделирование: Учебник для вузов. — Тирасполь: РИО ПГУ, 2002. — 280 с.

48. Дьяконов В.П. «Закон Мура» и компьютерная математика // Exponenta Pro. Математика в приложениях. 2003. № 1. С. 82-86.

49. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука, 1994.

50. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. — М.: Наука, 1981. — 344 с.

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

52. Зенкевич О. Метод конечных элементов в технике. — М.: Мир, 1975. —547 с.

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

54. Карп P.M. Сводимость комбинаторных проблем // Кибернетический сборник (новая серия). — М.: Мир, 1975. № 12. С. 123-148.

55. Карпов Ю.Г. Теория автоматов. — СПб.: Питер, 2002. — 224 с.

56. КемениДж., СнеллДж. Конечные цепи Маркова: Пер. с англ. М.: Наука,1970.

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

58. Когаловский М.Р. Энциклопедия технологий баз данных. — М.: Финансы и статистика, 2002. — 800 с.

59. Колмогоров А.Н. Три подхода к определению понятия количества информации // Проблемы передачи информации. Вып. 1. 1965.

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

61. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999. — 960 с.

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

63. Кренке Д. Теория и практика построения баз данных. — 8-е изд.: Пер. с англ. — СПб.: Питер, 2003. — 800 с.

64. Кук С.А. Сложность процедур вывода теорем // Кибернетический сборник (новая серия). — М.: Мир, 1975. № 12. С. 149-174.

65. Куликов А.В. Исследование и разработка алгоритмов обобщения на основе теории приближенных множеств // Автореферат дисс. . кандидата технических наук. — Москва, 2004. — 20 с.

66. Левин Л.А. Универсальные проблемы упорядочения // Проблемы передачи информации. 1973. —Т. 9. № 3. С. 115-117.

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

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

69. Липский В. Комбинаторика для программистов: Пер. с польск. — М.: Мир, 1988. —213 с.

70. Лисецкий Ю.М. Алгоритмы и методы комплексной количественной оценки качества систем // Автореферат дисс. кандидата технических наук. — М., 2003. —26 с.

71. Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981.

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

73. Макконнел Дж. Анализ алгоритмов. Вводный курс. — М.: Техносфера,2002. —304 с.

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

75. Марков АА. Теория алгоритмов // Труды математического института АН СССР им. В. А. Стеклова. — М.,1954. Т. 42.

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

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

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

79. Морозов В.А. Алгоритмические основы методов решения некорректных задач // Вычислительные методы и программирование. — 2003. Том 4. С. 130—141.

80. Мошков М.Ю. О глубине деревьев решений // Доклады РАН. 1998. т. 358, №1. С. 26-32.

81. Назаров Д. Обзор современных пакетов КЭ анализа // САПР и Графика. 2000. №2. С. 16-27.

82. Нариньяни А.С. Модель или алгоритм: Новая парадигма информационной технологии (htpp: www.artint.ru/articles/narin/parad-rl .htm).

83. Новиков Ф.А. Дискретная математика для программистов. — СПб.: Питер, 2001. —304 с.

84. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями): Пер. с франц. — М.: Мир, 1999. — 720 с.

85. Ноженкова Л.Ф. Информационные технологии: интегрированный и гибридный подходы // Вычислительные технологии. 2004. Том 9. С. 84-94

86. Носов В.А. Основы теории алгоритмов и анализа их сложности (http: // intsys.msk.ru).

87. ОртегаДж. Введение в параллельные и векторные методы решения линейных систем : Пер. с англ. — М.: Мир 1991. — 224 с.

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

89. Оценка качества программных средств. Общие положения. ГОСТ 28195-89.

90. Пападимитриу X., СтайглицК. Комбинаторная оптимизация: Алгоритмы и сложность. — М.: Мир, 1985. — 512 с.

91. Подловченко Р.И., Хачатрян В.Е. Об одном подходе к разрешению проблемы эквивалентности // Программирование. 2004. № 4. С.3-20.

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

93. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980.

94. Роб П., КоронелК. Системы баз данных: проектирование, реализация и управление. 5-е изд., перераб. и доп.: Пер. с англ. — СПб.: БХВ-Петербург, 2004. — 1040 с.

95. Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике. — 3-е изд., перераб. и доп. — СПб.: Невский диалект, 2003. — 320 с.

96. Сборник действующих международных стандартов ИСО серии 9000. Т 1, 2, 3. — М.: ВНИИКИ. 1998.

97. Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984. -380 с.

98. Системы управления базами данных и знаний: Справ, изд. / Наумов А.Н., Вендров A.M., Иванов В.К. и др.; Под. ред. А.Н. Наумова. — М.: Финансы и статистика, 1991. —352 с.

99. Скворцов А.В. Триангуляция Делоне и ее применение. — Томск: Изд-во Томского уни-та, 2002. — 128 с.

100. Советов Б.Я., Яковлев С.А. Моделирование систем: Учеб. для вузов — 3-е изд., перераб. и доп. — М.: Высш. шк., 2001. — 343 с.

101. Степанченко И.В. Исследование влияния ограниченности параметров технических средств на выбор и реализацию алгоритмов управления динамическими процессами // Автореферат дисс. кандидата технических наук. — Волгоград, 2002. — 17 с.

102. Столлингс В. Структурная организация и архитектура компьютерных систем, 5-е изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2002.— 896 с.

103. Стренг Г., ФиксДж. Теория метода конечных элементов. — М.: Мир, 1977. —523 с.

104. СэломонД. Сжатие данных, изображений и звука. — М.: Техносфера, 2004. — 368 с.

105. Топоркова А.С. Исследование динамических характеристик программ на масштабируемых ресурсах // Автореферат дисс. кандидата технических наук. — М., 2001. — 19 с.

106. Трахтенброт Б.А. Алгоритмы и вычислительные машины. — М.: Сов. радио, 1974. —200 с.

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

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

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

110. Уваров Д.В., Перепелкин А.И., Корячко В.П. Построение дерева кратчайших путей в графе на основе данных о парных переходах // Системы управления и информационные технологии. 2004. № 4 (16). С. 93-96.

111. Усачев Ю.Е. Исследование характеристик вычислительных систем: Методическое пособие. — Пенза: Изд-во Пенз. технол. ин-та , 1998. — 36 с.

112. Успенский В.А. Машина Поста. — М.: Наука, 1979. — 96 с.

113. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные понятия и приложения. — М.: Наука, 1987.

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

115. ФеррариД. Оценка производительности вычислительных систем. Пер. с англ. —М.: Мир, 1981. —324 с.

116. ХачиянЛ.Г. Полиномиальные алгоритмы в линейном программировании // Журнал вычислительной математики и математической физики. 1980. № 1. С. 51-69.

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

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

119. ЦелищевВ.С. Алгоритмическое проектирование и оценивание систем на основе аналогового моделирования // Автореферат дисс. кандидата технических наук.—М., 2003. —20 с.

120. Чекинов С. Г. Возможные решения интервальных математических моделей И Информационные технологии. 2002. № 9. С. 12-17.

121. Чернов С.А. Исследование и реализация базовой вычислительной машины с внутренним языком высокого уровня И Автореферат дисс. . кандидата технических наук. —М., 2003. —20 с.

122. Черноножкин С.К. Методы и инструменты метрической поддержки разработки качественных программ // Автореферат дисс. . кандидата физико-математических наук— Новосибирск, 1998. — 19 с.

123. ЧмораА.Л. Современная прикладная криптография. — М.: Гелиос АРВ, 2001.—256 с.

124. Шевченко В.Н. Качественные вопросы целочисленного программирования, — М: Физматлит, 1995. — 192 с.

125. Шинкаренко В.И. Об оценке эффективности алгоритмов с учетом архитектуры ЭВМ. / Комп'ютерне моделювання. Тезисы докладов межгосударственной научно-практической конференции. — Днепродзержинск: ДГТУ, 2000. С. 268-269

126. Щекелин B.C. Моделирование информационных систем. — Ульяновск: УлГТУ. —46 с.

127. Юдин Д.Б., Горяшко А.П., Немировский А.С. Математические методы оптимизации устройств и алгоритмов АСУ / Под ред. Ю.В. Асафьева, В.А. Шабалина. — М.: Радио и связь. 1982. — 288 с.

128. Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики. 1958., Вып. 1.С. 75-127.

129. AhujaR. К., MehlhornK., OrlinJ. В., and TarjanR. E. Faster algorithms for the shortest path problem. Technical Report 193, MIT Operations Research Center, 1988.

130. Archer G. C. Object Oriented Finite Element Analysis // Ph.D. dissertation, University of California at Berkeley, 1996.

131. Baase S., Van Gelder Computer algorithms. Addison-Wesley Longman, Reading, MA (2000).

132. Bangerth W. and Kanschat G., Concepts for object-oriented finite element software / — the deal.II library Preprint 99-43 (SFB 359), IWR Heidelberg, October 1999.

133. Bangerth W., Using Modern Features of С++ for Adaptive Finite Element Methods: Dimension-Independent Programming / —in deal. II, Proceedings of the 16th IMACS World Congress, Lausanne, Switzerland, 2000.

134. Beizer B. Software testing techniques. — N. Y.: Van Nostrand Reinhold. 1990.

135. Ben-OrM. Lower bounds for algebraic computation trees // Proc. 15th ACM Annu. Symp. Theory Comput. Apr. 1983. pp. 80-86.

136. Bentley J. L. Writing Efficient Programs. Preitice-Hall, 1982.

137. Bentley J., Haken D., Saxe J. A general method for solving divide-and-conquer recurrences//SIGACT News. 1980. 12(3). pp. 36-44.

138. Brassard G., BratleyP. Algorithms: Theory and Practice. Prentice-Hall, Engle-wood Cliffs, NJ (1988).

139. Chaitin G. J. Algorithmic information theory. — Third Printing. — IBM, 1997, — 238 p.

140. Cobham A. The intrinsic computational difficulty of functions // Proc. Congress for Logic, Mathematics, and the Philosophy of Science-North Holland, Amsterdam, 1964. pp. 24-30.

141. Codd E. F., Codd S. В., Salley С. T. Providing OLAP (on-line analytical processing) to user-analysts: An IT-Mandate. / Technical report. E. F. Codd and Associates, San Jose 1993. —31 p.

142. CookS. C. The complexity of theorem-proving procedures // Third ACM Symposium on Theory of Computing., — ACM, New York, 1971. pp. 151-158.

143. Cook S., Dwork C., Reischuk R. Upper and lower time bounds for parallel random access machines without simultaneous writes // SIAM Journal on Computing, 1986, 15(1), pp. 87-97.

144. Deshpande P. M., RamasamyK., ShuklaA., NaughtonJ. F. Caching multidimensional queries using chunks. // In Proceedings of ACM SIGMOD, June 1998. pp. 259-270.

145. FredmanM. L., Saks M. E. The cell probe complexity of dynamic data structures. In Proc. of the Twenty First Annual ACM Symposium on Theory of Computing, 1989.

146. Goldberg A. V. Efficient Graph Algorithms for Sequential and Parallel Computers. PhD thesis, Department of Electrical Engineering and Computer Science, MIT, 1987.

147. GolumbicM. C. Algorithmic graph theory and perfect graphs. Academic Press, New York, 1980.

148. GrayR. M. Entropy and information theory. —New-York: Springer-Verlag, 1990. —306 p.

149. Hartmanis J. and Stearns R. E. On the computational complexity of algorithms //Transactions of the AMS. 1965. 117. P. 285-306.

150. Hochbaum D. Approximation algorithms for NP-Hard Problems. PWS Publishing, Boston, MA (1997).

151. HopcroftJ. E. and UllmanJ. D. Introduction to Automata Theory, Languages and Computation. — Addison-Wesley, Reading MA, 1979.

152. Inmon W. H. Building the data warehouse: Third edition. — New York: John Wiley and Sons, 2002. — 412 p.

153. KarmarkarN. A new polynomial-time algorithm for linear programming // Combinatorica, 1984, 4(4), pp.373-395.

154. Karp R. M. Reducibility among combinatorial problems // Complexity of Computer Computations / R. E. Miller, ed.-Plenum Press, New York, 1972. pp. 85-104.

155. KnuthD. Big Omicron and Big Omega and Big Theta. SIGACT News 8(2), (1976), pp. 18-24.

156. Lee D. Т., Wu Y. F. Efficient algorithms for Euclidean 1-line center and problems. Proc. ISOLDE III, Boston, MA, 1984.

157. Little J. D. C., Murty K. G., Sweeney D. W., and Karel C. An algorithm for the traveling salesman problem // Operations Research, vl 1 (1963), pp. 972-989.

158. LovaszL. Combinatorial problems and exercises, Academiqi Kiado, Budapest,1979.

159. Papadimitriou С. H. Computational Complexity. — Addison-Wesley, Reading MA, 1994.

160. PostE. L. Finite combinatory process — formulation 1 // J. Symbolic Logic (1936) l,pp. 103-105.

161. Roy P., VoraJ,, Ramamritham K., Seshadri S., Sudarshan S. Query Result Caching in Data Warehouses and Data Marts. University of Massachusetts Computer Science,1999. —13 pp.

162. Segewick R. Algorithms. 2d ed., Addison-Welsey, Reading, MA (1988).

163. SeidelR. A method for lower bounds for certain geometric problems. Dep. Comput. Sci., Cornell Univ., Uthaca, NY, Tech. Rep. 84-592, Feb. 1984.

164. Sommerville I. Software engineering. Addison-Wesley. Lancaster University.2000.

165. Steele L. M., Yao A. C. Lower bounds for algebraic decision trees // J. Algo-rith. 1982., 3. P. 1-8.

166. Sunday D. M. A very Fast Substring Search Algorithm // Comraun. ACM, Vol. 33 No. 8 (1990), pp. 132-142.

167. TarjanR. E. Amortized computational complexity // SIAM Journal on Algebraic and Discrete Methods. 1985. 6(2). pp. 306-318.

168. Tarjan R. E. Efficiency of a good but not linear graph algorithms // Siam journal on Computing, 1972, 1(2), pp. 215-225.

169. Toft В., Jensen T. R. Graph coloring problems. John Wiley & Sons, Inc., 1994.

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

171. Viglas A. On Hardness and Lower Bounds in Complexity Theory // A dissertation presented to the Faculty of Princeton University in Candidacy for the Degree of Doctor of Philosophy. — Princeton, 2002. — 109 p.

172. Vincent J., Waters A., Sinclair J. Software quality assurance // Vol. II. A program guide. — Englewood Cliffs, New Jersey: Prentice-Hall. 1988.

173. WilfH. S. Algoritms and complexity. — Internet Edition, 1994 (www/cis.uppen.edu/wilf) — 135 p.

174. Yao A. C., Rivest R. L. On the polyhedral decision problem // SIAM J. Comput. (1980) 9, pp. 343-347.

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

176. Ульянов М.В. Дополнение к книге Дж. Макконелла «Основы современных алгоритмов». — М.: Издательство «Техносфера», 2004. С. 303-366.

177. Ульянов М. В. Классификация алгоритмов в целях практического анализа // Информационные технологии. 2003. № 11. С. 29-36.

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

179. Александров А.Е., Ульянов М.В. Общие подходы к повышению ресурсной эффективности алгоритмического обеспечения систем конечно-элементного анализа // Автоматизация и современные технологии. 2004. № 9. С. 18-24.

180. Александров А.Е., Востриков А.А., Ульянов М.В. Эффективные алгоритмы формирования глобальной матрицы для комплекса конечно-элементного анализа // Автоматизация и современные технологии. 2004. № 10. С. 32-36.

181. Ульянов М.В. Учет специальных требований к алгоритмическому обеспечению в комплексной оценке качества алгоритмов // Вестник Рязанской радиотехнической академии. 2004. № 2. С. 29-36.

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

183. Ульянов М.В. Теоретико-множественный подход к определению функций трудоемкости алгоритма// Информация и безопасность. 2004. № 2. С. 53-58.

184. Михайлов Б.М., Ульянов М.В. Инструментальные средства для исследования эффективности алгоритмов: концепция и основные принципы построения // Информационные технологии. 2005. № 2. С. 54-57.

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

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

187. Ульянов М.В. Определение объектного и алгоритмического базисов // Программное и информационное обеспечение систем различного назначения на базе ПЭВМ: Межвузовский сборник научных трудов. — М.: МГАПИ, 2000. Вып. 3. С. 159-161.

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

189. Ульянов М.В. Классификация алгоритмов по их трудоемкости // Программное и информационное обеспечение систем различного назначения на базе ПЭВМ: Межвузовский сборник научных трудов. — М.: МГАПИ, 2000. Вып. 3. С. 157-159.

190. Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. — М.: МГАПИ, 2003. — 80 с.

191. Ульянов М.В., Родина Н.В. Разработка эффективных алгоритмов: Учебное пособие. — М.: МГАПИ, 2004. — 112 с.

192. Ульянов М.В., БесединА.В., Кондратьева Т.В. Система экспериментального анализа алгоритмов // Свидетельство об официальной регистрации программы для ЭВМ № 2004612709 от 20.12.2004.