Содержание к диссертации
Введение
ГЛАВА 1 Оценки качества алгоритмов и алгоритмического обеспечения программных систем , 12
Введение 12
1.1 Обшие подходы к оценке качества алгоритмического обеспечения программных систем 13
1.2 Методы оценки алгоритмов в классической теории 30
1.3 Оценки алгоритмов в теории сложности вычислений 36
1.4 Специальные модели вычислений для оценки сложности алгоритмов 43
1.5 Заключение 48
ГЛАВА 2 Основы теории ресурсной эффективности вычислительных алгоритмов 50
Введение 50
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], В результате сегодня известно достаточно большое количество разнообразных по своим характеристикам вычислительных алгоритмов решения актуальных практических задач. При разработке алгоритмического обеспечения программных средств и систем возникает практическая необходимость исследования, оценки и сравнительного анализа ресурсной эффективности различных вычислительных алгоритмов, предназначенных для решения некоторой задачи в области множества входов, характеристики которых определяются спецификой области их применения. Результаты такого сравнительного анализа и исследования позволяют обосновать, в принятой системе количественных оценок, выбор рациональных ресурсно-эффективных алгоритмов и сформулировать рекомендации по их совершенствованию.
В связи с этим систематизация и развитие теоретической базы создания и выбора компонентов алгоритмического обеспечения программных систем, в том числе разработка такого раздела теории алгоритмов, как теория ресурсной эффективности, представляет собой актуальную проблему в области создания эффективного математического и программного обеспечения вычислительных машин, комплексов и компьютерных сетей.
Состояние проблемы
При разработке основ теории, методов оценки и сравнительного анализа ресурсной эффективности вычислительных алгоритмов охватывается широкий круг проблем теории алгоритмов, асимптотического анализа сложности алгоритмов, оценки качества программных средств и систем и их алгоритмического обеспечения, в исследование и развитие которых внесли значительных вклад российские и зарубежные ученые: А.Н. Колмогоров, А.А. Марков, В,М. Глушков, Г.Е. Цейтлин, E.JL Ющенко, Г.С. Цейтин, Ю.И. Янов, Л.А, Левин, В.Е. Котов, В.К. Сабельфельд, В.А. Горбатов, А.И. Мальцев, МКХ Мошков, Ф.А. Новиков, В.А. Носов, Б.Я. Фалевич, Э. Пост, А- Тьюринг, А, Черч, Д.Э. Кнут, А. Ахо, Дж, Хопкрофт, Дж. Ульман, М. Гэри, Д. Джонсон, Р, Грэхем, Д. Гасфилд, Р. Карп, Р. Тарьян, А Кобхем, М, Бен-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 г,, научных семинарах кафедр «Персональные компьютеры и сети» под рук, Б.М. Михайлова и «Управление и моделирование систем» под рук. С.Н. Музыкина Московской государственной академии приборостроения и информатики.
Специальные модели вычислений для оценки сложности алгоритмов
Полученная нагруженная сеть называется информационным графом над базовым множеством 9Ї = {Fy G).
На основе введенной модели вычислений в [35] получены теоретические результаты по оценкам сложности задач информационного поиска, в том числе мощностная нижняя оценка, т. е. строгое доказательство того, что время поиска по крайней мере не меньше, чем время, необходимое на перечисление ответа.
Далее на основе этой модели в [35] исследованы семь выделенных авторами модельных классов для задач информационного поиска, для которых предложены эффективные методы и алгоритмы их решения, и теоретически получены важные нижние и средние оценки сложности, введено понятие канонического эффекта и є — расширения запроса в информационном поиске. Интересный подход, связанный с исследованием задач сложностного класса NP, содержится в работах [23, 24, 178]. Этот подход основан на использовании аппарата полиэдральных графов задач и геометрической интерпретации алгоритмов.
В основе подхода лежит идея обнаружения признака, не обязательно напрямую характеризующего сложность задачи, но отличающего полиномиально-разрешимые задачи от NP -полных. Такой признак ищется в конструкциях, связанных с задачами, одной из которых является многогранник задачи.
Пусть М — некоторый многогранник, а X — множество его вершин. Две вершины называются смежными, если отрезок (то есть выпуклая оболочка пары вершин) не пересекается с выпуклой оболочкой остальных вершин. Проще, смежность вершин означает, что отрезок, их соединяющий, является ребром многогранника М. К изучению выпуклых многогранников приводят многие задачи, в числе которых особенно важными в прикладном отношении являются задачи линейного программирования.
Ответ на вопрос, сколько попарно смежных вершин может быть у выпуклого многогранника в т -мерном пространстве при т, равных 2 и 3, почти очевиден: не более трех при т = 2 и не более четырех для т = 3, что соответствует треугольнику и тетраэдру. Но уже для w-4 имеет место теорема о том, что для любого натурального п в RA существует выпуклый многогранник с п попарно смежными вершинами [53], Этот результат получен Гейлом в 1956 году [53] и приобрел широкую известность благодаря линейному программированию.
Переход к дискретным задачам связан с тем, что [23] «многие дискретные задачи естественным образом приводятся к геометрическому виду, и это дает возможность алгоритмические свойства задач интерпретировать в терминах понятий геометрии. Такая возможность в первую очередь характерна для дискретных задач оптимизации, их часто называют задачами комбинаторной оптимизации. Большинство задач комбинаторной оптимизации объединяет то, что их можно рассматривать как задачи отыскания минимума (или максимума) линейной функции на конечном множестве точек в пространстве Лт».
Многогранник задачи вводится в [24] следующим образом: пусть X — некоторая задача, X є Rm, рассмотрим две геометрические конструкции, связанные с X: обозначим через М(Х) выпуклую оболочку множества X и назовем ее многогранником задачи. Определим многогранный конус К(х) как множество, состоящее из тех точек, для которых решением соответствующих индивидуальных задач служит х. Сама же индивидуальная задача, задаваемая вектором с заключается в отыскании такого значения х є Xь для которого с є К(х). Для многогранника задачи М(Х) и множества конусов К(х),х Х легко устанавливается простая связь — конусы К(х) и К{у) имеют общую гипергрань, то есть грань размерности т — 1, в том и только том случае, если хну — смежные вершины многогранника Л/(Х).
Обозначая через X некоторую задачу, ХєЯт, рассмотрим граф G(X) многогранника М{Х): множеством вершин этого графа служит X, а ребрами являются геометрические ребра многогранника. Граф G (X) называется полиэдральным графом задачи X [24]. Обозначим через р(Х) характеристику графа G(X) — плотность, как максимальное количество попарно смежных вершин графа G(X).
Плотность полиэдрального графа задачи оказывается именно той величиной, поведение которой отражается на степени сложности задачи. В основе этой зависимости находится следующая интерпретация величины р{Х): значение р(Х) равно максимальному количеству таких точек из X, что для любых двух х и у из них соответствующие конусы К(х) и К(у) имеют общую гипергрань.
В большой серии работ, опубликованных в течение последних десяти лет, изучалось поведение плотности р{Хт) полиэдральных графов для различных задач комбинаторной оптимизации. В итоге обнаружилась следующая закономерность: для всех полиномиально разрешимых задач плотность р(Хт) ограничена сверху степенной функцией от /и, и для каждой JVP-полной задачи р(Хт) растет быстрее, чем любая степенная функция [23].
Таким образом, характер роста величины р{Хт) служит критерием, различающим задачи по сложности, и в соответствии с [23] можно говорить о геометрической интерпретации алгоритмов. Общее свойство всех алгоритмов комбинаторной оптимизации состоит в том, что выбор оптимального элемента х во множестве X происходит в результате выполнения конечной последовательности линейных сравнений для вектора, задающего индивидуальную задачу. Тем самым плотность полиэдрального графа задачи может интерпретироваться как нижняя оценка трудоемкости алгоритмов традиционного типа.
Операции в моделях вычислений и теоретико-множественный подход к определению функции трудоемкости
Определение трудоемкости алгоритма связано с базовыми операциями в модели вычислений (см, 1,2» 1.4), составляющими исходное множество операций данной модели. В связи с этим рассмотрим элементарные операции в различных моделях вычислений, базирующихся на априорном предположении о том, что механизм реализации умеет выполнять некоторые операции из заранее описанного множества. Алгоритмы, заданные в таких моделях вычислений, носят в теории алгоритмов название «условного алгоритма» или «относительного алгоритма» [78]. Мы не будем рассматривать специальные модели вычислений, ориентированные на решение задач верификации и исследования проблемы эквивалентности алгоритмов, например схемы алгоритмов Янова [132], схемы программ Котова [66], а также алгоритмическую модель Маркова [79, 80], базирующуюся на операциях преобразования слов в произвольных алфавитах. Машина Поста является моделью вычислений с наиболее примитивным базисом операций. Основные понятия модели вычислений (алгоритмического формализма) Поста [116, 117] —это пространство символов, в котором задаётся конкретная проблема и получается ответ, и набор инструкций, т. е. операций в пространстве символов, задающих как сами операции, так и порядок выполнения инструкций. Постовское пространство символов — это бесконечная лента ячеек, причем каждая ячейка может быть помечена или не помечена.
Конкретная проблема задается «внешней силой» (термин Поста), пометкой конечного количества ячеек, при этом очевидно, что любая конфигурация начинается и заканчивается помеченным ящиком. После применения к конкретной проблеме некоторого набора инструкций решение представляется также в виде набора помеченных и непомеченных ящиков, распознаваемое той же внешней силой Пост предложил следующий набор инструкций [164], который является, очевидно5 минимальным набором битовых операций: определить, помечен ящик или нет, и по результату перейти на одну из двух указанных инструкций; остановиться Отметим, что формулировка инструкций 1 и 2 включает неявно за щиту от неправильных ситуаций. Программа представляет собой нумеро ванную последовательность инструкций, причем переходы в инструкции 5 производятся на указанные в ней номера других инструкций, инструкции с 1-й по 4-ю содержат явное указание следующей команды. Среди операций машины Поста можно выделить содержательно следующие группы операций: — группу операций работы с памятью — чтение, запись и выбор ячеек; —- группу операций организации процесса вычислений. Отметим, что все операции, за исключением операции останова, являются «сложными» — они содержат как обращения к памяти по чтению, записи и выбору ячеек, так и элемент управления механизмом реализации — переход к следующей инструкции. Операции в машине Тьюринга Формализм машины Тьюринга является сегодня общепризнанным инструментом теоретического исследования в теории алгоритмов [121]-, что связано с близостью предложенной модели вычислений к конечным автоматам. Приведем характеристику работы А, Тьюринга, принадлежащую Хопкрофту [121]: «Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т, е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга».
Машина Тьюринга является расширением модели конечного автомата, включающим потенциально бесконечную память с возможностью перехода от обозреваемой в данный момент ячейки к ее левому или правому соседу [174],
Формально машина Тьюринга может быть описана следующим образом [59]. Пусть заданы: конечное множество состояний — Q, в которых может находиться машина, конечное множество символов ленты — Г, и функция 6 (функция переходов или программа), которая задается отображением пары из декартова произведения QxV (машина находится в состоянии q. и обозревает символ у,) в тройку декартова произведения.
При этом выделяется один пустой символ е из Г, подмножество ХєГ определяется как подмножество входных символов ленты, причем еє(Г Б), одно из состояний — q0 eQ является начальным состоянием машины. Решаемая проблема задается путем записи конечного количества символов s є 2 на ленту, после чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа — ( 70,Тсо)? после чего в соответствии с указанной функцией переходов 0?,, )— (#,,5,, или Д) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функцией переходов. Останов машины происходит в том случае, если для пары (qi9 ss) функция перехода не определена.
Методы получения ресурсных функций в рекурсивной реализации алгоритмов
Для алгоритмического базиса формального процедурного языка высокого уровня такими базовыми операциями, коррелированными с основными операциями языков процедурного программирования, будем считать следующие [179]: — простое присваивание: а г-Ь; — одномерная индексация: a[i\ : (адрес (а)+ і -длинаэлемента); — арифметические операции: { ,/,-,+ }; — операции сравнения: а { , ,-, } Ъ; — логические операции: ( /1) { or, and, not } (12); — операции взятия содержимого по адресу (штрих-операция) и адресации в сложных типах данных (патеХ.патеІ), По отношению к введенному набору базовых операций для алгоритмического базиса формального процедурного языка высокого уровня необходимо сделать несколько замечаний: — опираясь на идеи структурного программирования, из набора элементарных операций исключается команда перехода, поскольку ее можно считать связанной с операцией сравнения в конструкции ветвления или цикла по условию. Такое исключение оправдано запретом использования оператора перехода на метку в идеологии структурного программирования; — операции доступа к простым именованным ячейкам памяти считаются связанными с операциями, операнды которых они хранят; — операции индексации элементов массивов и сложной адресации в типах данных вынесены в отдельные элементарные операции с целью возможного согласования временных оценок программных реализаций; — конструкции циклов не рассматриваются, т. к, могут быть сведены к указанному набору элементарных операций (см. 3.1.1). С учетом этих замечаний можно говорить, что введенный алгоритмический базис является по трудоемкости 0(1)-эквивалентным машине с произвольным доступом к памяти, как выбранной модели вычислений. Таким образом, полученная в данном алгоритмическом базисе функция трудоемкости алгоритма будет отличаться от значения функции нумерации в машине с произвольным доступом к памяти не более чем на константный множитель. Дополнительная аргументация введения элементарных операций языка высокого уровня для получения функции трудоемкости основана на современных проектных разработках вычислительных машин с внутренним языком высокого уровня [125], в которой такие операции уже очевидно являются машинными.
Традиционная классификация теории алгоритмов опирается на результаты, полученные Кобхэмом (1964 г.), Куком (1971г.) и Левиным (1973 г.), работы которых положили начало теории сложности вычислений, в рамках которой получен целый ряд важных результатов, относящихся к классам задач, являющихся объектом исследований в этой теории [70, 121, 146]. В теории сложности рассматривается целый ряд специальных классов задач [121], при этом большинство практически решаемых задач относится к классу Р — классу задач, решающие алгоритмы которых имеют не более чем полиномиальную сложность. Большинство известных точных алгоритмов решения АТЧюлных задач имеют экспоненциальную (класс ЕХР) или надполиномиальную сложность [65].
К сожалению, использование в целях анализа ресурсной эффективности алгоритмов аппарата классической теории сложности не является вполне корректным. Это связано с тем, что теория сложности оперирует с классами задач, а не с классами алгоритмов, а большинство определений классов задач, за исключением классов Р и ЕХР9 не включает в себя явного указания сложностных оценок [14, 65, 121]- Таким образом, актуальной является задача разработки корректной классификации алгоритмов по сложности функции трудоемкости.
С другой стороны, в целях практического анализа представляет интерес и другая классификация, учитывающая влияние различных характеристик множества исходных данных на функцию трудоемкости. Отметим, что в классической теории сложности рассматривается только одна такая характеристика — длина входа [65].
В теоретическом аспекте анализа ресурсной эффективности представляет интерес и классификация задач, основой которой является сравнение доказанной нижней границы временной сложности задачи и оценки наиболее эффективного из существующих алгоритмов ее решения. На основе такой классификации можно говорить о теоретической возможности улучшения временной эффективности алгоритма,
В современной теории анализа алгоритмов известны доказательства нижних границ временной сложности для целого ряда задач [14, 35, 147]. Результаты, полученные в области практической разработки и анализа алгоритмов, позволяют указать наиболее асимптотически эффективные на данный момент алгоритмы решения широкого круга задач, В связи с этим представляет интерес взаимное сравнение этих результатов и построение на этой основе классификации вычислительных задач, отражающей, достигает или не достигает наиболее эффективный из известных в настоящее время алгоритмов доказанной нижней границы временной сложности задачи.
Заметим, что определения некоторых классов задач, рассматриваемых в теории алгоритмов, например классов Р и ЕХР [65, 121], также опираются на асимптотику временной сложности существующих алгоритмов решения задач в указанных классах. Теоретическая нижняя граница сложности — { иЛп)
Рассмотрим некоторую вычислительную задачу Z. Обозначим, пользуясь терминологией, введенной Э. Постом [116, 164], через Dz множество конкретных допустимых проблем данной задачи Z. Введем также следующие обозначения: Rz — множество правильных решений, Ver — верификационная функция задачи. Пусть DeDz — конкретная допустимая проблема данной задачи — вход алгоритма. Обозначим через Az полное множество всех алгоритмов (включающее как известные, так и будущие алгоритмы), решающих задачу Z в понимании алгоритма как финитного 1-процесса по Посту [164], т. е. любой алгоритм А из Az применим V DeDZt заканчивается и дает правильный ответ
Метод прогнозирования временной эффективности программных реализаций алгоритмов на основе функции трудоемкости
Практически значимым результатом анализа ресурсной эффективности некоторого алгоритма является получение таких сведений, которые могли бы дать возможность прогнозирования требуемых этим алгоритмом ресурсных затрат при решении задач из данной проблемной области. Одним из наиболее значимых ресурсов является ресурс процессора, и в аспекте этого ресурса результатом анализа является прогнозирование трудоемкости алгоритма, как для разных размерностей задачи, так и для различных входных данных при фиксированной размерности.
Идеальным результатом для решения задачи прогнозирования трудоемкости алгоритма можно считать получение точной функции трудоемкости fA{D), где D — конкретный вход алгоритма. Эта функция должна учитывать не только размерность входа, но и влияние значений элементов D и их порядка на количество задаваемых алгоритмом элементарных операций в формальной системе записи, К сожалению, такая функция может быть реально получена только для количественно-зависимых алгоритмов, образующих класс N 9 и? может быть, для отдельных алгоритмов других классов, ввиду сложности формального описания влияния параметрической составляющей на трудоемкость. Однако наиболее широким алгоритмическим классом является класс количественно-параметрических алгоритмов (класс NPR), для которого трудоемкости в лучшем и худшем случаях различаются между собой, порой значительно, например, для подкласса NPRH, Получение в этом классе точной функции трудоемкости затруднительно даже для относительно простых алгоритмов. Использование оценки в среднем позволяет прогнозировать трудоемкость алгоритма только при усреднении по большой выборке входов.
Более детальную информацию о поведении алгоритма можно получить, рассматривая функцию трудоемкости как дискретную случайную величину, характеризующуюся математическим ожиданием и дисперсией и ограниченную минимальным и максимальным значениями [200]. В ряде случаев значения математического ожидания и дисперсии могут быть получены теоретически, на основании совокупного анализа множества Dn — множества всех входов алгоритма размерности п, для некоторых алгоритмов такие оценки получены, например, Д, Кнутом [61].
Более детальное рассмотрение задачи прогнозирования связано с изучением влияния характеристик множества исходных данных на функцию трудоемкости алгоритма. Традиционно влияние изменений параметров входа на выходную характеристику изучаемого объекта называется чувствительностью по входному параметру [82], Таким образом, можно говорить о чувствительности алгоритма (в смысле его функции трудоемкости) к исходным данным. Так как трудоемкость определяет количество операций, задаваемых алгоритмом в принятой формальной системе записи, то такую чувствительность будем называть операционной. Поскольку трудоемкость алгоритма зависит как от количества элементов множества исходных данных, так и от параметров этого множества, то можно выделить различные аспекты операционной чувствительности алгоритмов, введенные в [200], Определение 2Л0 Под информационной чувствительностью алгоритма будем понимать влияние различных входов фиксированной размерности на изменение значений функции трудоемкости алгоритма. Определение 2.11 Под размерностной чувствительностью алгоритма будем понимать влияние изменения размерности на значения функции трудоемкости. Количественная мера информационной чувствительности алгоритмов Для иллюстрации понятия информационной чувствительности рассмотрим качественно вид функции трудоемкости для некоторого алгоритма, принадлежащего классу NPRy представленного на рисунке 2.6, Здесь по оси абсцисс отложены номера конкретных входов алгоритма с размерностью п, принадлежащих множеству Dn, всего таких входов Д, j. Мощность множества Dn значительна, однако конечна, в предположении о конкретной реализации алгоритма» в силу ограниченности представления чисел в компьютере. В случае если п — количество битов на входе, то максимально \Dn 1 = 2", если все битовые комбинации являются допустимыми для данного алгоритма. Реально мы имеем дело с целочисленной функцией целочисленного аргумента, поэтому график представляет собой набор точечных значений- Для наглядности на рисунке 2.6 показана огибающая линия этих точечных значений. Отметим, что качественно вид графика очень сильно зависит от принятого способа нумерации элементов множества О . Огибающая точечного графика трудоемкости количестєенно-параметрического алгоритма для различных входов размерности п. Для какого-то входа алгоритм выполняет максимальное количество операций, что соответствует худшему случаю для данной размерности — f2{n)y аналогично в лучшем случае количество операций будет минимально — /л(п) И трудоемкость для любого входа будет заключена между этими крайними значениями. Подсчитывая относительную по размерности множества Dn частотную встречаемость того или иного значения функции трудоемкости fA, мы можем получить гистограмму относительных частот значений функции трудоемкости Р{/А) как дискретной случайной величины. Возможный вид огибающей такой гистограммы показан на рисунке 2.7, Огибающая гистограммы относительных частот значений функции трудоемкости для количестве)mo-параметрического алгоритма. При этом очевидно выполнено следующее условие: тогда среднее значение трудоемкости может быть определено как где обе суммы берутся по всем целочисленным значениям функции трудоемкости /Л на множестве Dn:f% fA f. Вводя понятие информационной чувствительности, в дальнейшем обозначая ее через 5, (л) [200], мы хотим установить количественную меру разброса или рассеяния значений функции трудоемкости относительно среднего значения для различных входов фиксированной длины с учетом граничных значений. В общем случае этот разброс будет зависеть от размерности входа, поэтому бДгс) вводится как функция от аргумента п.
Стандартно мерой рассеяния случайной величины относительно математического ожидания является дисперсия D или среднеквадратическое отклонение CJ . В целях определения верхней границы для среднеквадрати-ческого отклонения ограниченной случайной величины, заданной функций fix) — af, докажем следующее утверждение [200].
