Ресурсная эффективность вычислительных алгоритмов : Теория и применение

• Автор: Ульянов, Михаил Васильевич
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 309 с. : ил.

ГЛАВА 1 ОЦЕНКИ КАЧЕСТВА АЛГОРИТМОВ И АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ ПРОГРАММНЫХ СИСТЕМ Л 2 Введение
1.1 Общие подходы к оценке качества алгоритмического обеспечения программных систем

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

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

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

1.5 Заключение

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

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

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

2.4 Заключение

ГЛАВА 3 РЕСУРСНЫЕ ФУНКЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ: МЕТОДЫ ПОЛУЧЕНИЯ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ
3.1 Методы получения ресурсных функций для процедурной реализации алгоритмов
3.2 Методы получения ресурсных функций в рекурсивной реализации алгоритмов

3.3 Сравнительный анализ алгоритмов по ресурсным функциям
3.4 Заключение
ГЛАВА 4 ВРЕМЕННАЯ ЭФФЕКТИВНОСТЬ ПРОГРАММНЫХ

РЕАЛИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ
4.1 Временные оценки для программных реализаций вычислительных алгоритмов
4.2 Метод прогнозирования временной эффективности программных реализаций алгоритмов на основе функции трудоемкости
4.3 Заключение
ГЛАВА 5 ПРИМЕНЕНИЕ ЭЛЕМЕНТОВ ТЕОРИИ РЕСУРСНОЙ ЭФФЕКТИВНОСТИ ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ ВЫБОРА РАЦИОНАЛЬНЫХ АЛГОРИТМОВ
5.1 Рациональные ресурсно-адаптивные алгоритмические решения по
компоненту формирования глобальной матрицы для программной системы «Термоупругость 3D»
5.2 Решение задачи упаковки с динамической внутренней границей объема для рациональной организации данных аналитического компонента индивидуальных информационных систем
5.3 Сравнительный анализ ресурсной эффективности алгоритмов решения классической задачи одномерной упаковки
5.4 Основные принципы построения инструментальных средств для исследования ресурсной эффективности алгоритмов
5.5 Заключение
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
# ПРИЛОЖЕНИЕ

Актуальность темы
Актуальность исследований в области ресурсной эффективности вычислительных алгоритмов определяется, прежде всего, рядом существующих сегодня тенденций развития наукоемких технологий в области программных средств и систем и особенностями решаемых проблемных задач. Практически значимыми и актуальными в наукоемких технологиях становятся сегодня сложные задачи большой размерности и вычислительной сложности, программные системы обработки потоков задач и обслуживания потоков запросов со значительными объемами обрабатываемых данных, эффективные программные средства для вычислительных систем, работающих в режиме реального времени в условиях ограниченных вычислительных ресурсов. Примерами могут служить программные системы, использующие методы конечно-элементного анализа для задач расчета деформаций и тепловых полей в сложных объектах [3], программы моделирования сложных систем [33, 104, 130], программное обеспечение информационно-телекоммуникационных систем и компьютерных сетей [26], в том числе информационно-поисковые системы Интернета и др. Актуальность этой тематики отражена и в приоритетных направлениях развития науки России — в перечне критических технологий РФ.
К современным программным средствам и системам, предназначенным для решения указанного круга задач, предъявляется ряд достаточно жестких требований по ресурсной эффективности, при этом такие характеристики их качества, как временная эффективность и ресурсоемкость являются одними из определяющих. Решение этих приоритетных, и ряда других практически актуальных задач не может опираться только на возрастающие мощности современных компьютеров.
Поскольку эффективность алгоритмических решений во многом влияет на характеристики реализующих их программных систем [119, 140], то, как один подходов в современных наукоемких компьютерных
ГЛАВА
ОСНОВЫ ТЕОРИИ РЕСУРСНОЙ ЭФФЕКТИВНОСТИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ
Разработка основ теории ресурсной эффективности вычислительных алгоритмов имеет своей целью создание, на основе систематизации и развития теоретических исследований в области разработки и выбора компонентов алгоритмического обеспечения программных средств и систем, научно-методической базы для решения вопросов сравнительного анализа и рационального выбора вычислительных алгоритмов в реальном диапазоне длин входов.
Достижение этой цели предполагает решение следующих основных задач, связанных с созданием основ теории ресурсной эффективности вычислительных алгоритмов и состоящих в разработке: системы определений и обозначений, ориентированной на задачи анализа ресурсной эффективности; функций ресурсной эффективности вычислительных алгоритмов и их программных реализаций, теоретико-множественного подхода к определению функции трудоемкости на основе анализа операций в моделях вычислений; теоретического обоснования перехода к базовым операциям процедурного языка высокого уровня; теоретических основ классификаций алгоритмов; классификаций вычислительных алгоритмов, отражающих различные аспекты их ресурсной эффективности.
Решению поставленных задач на основе обобщения существующего опыта теоретического анализа алгоритмов и посвящена настоящая глава.