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

• Автор: Евдокимов, Алексей Викторович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Ростов-на-Дону
• Количество страниц: 162 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1 АНАЛИЗ АЛГОРИТМИЧЕСКОГО ОПИСАНИЯ СИСТЕМ И СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1 Анализ специализированных языков имитационного I моделирования

1.2 Анализ методов дискретно-событийного моделирования

1 » * N1

1.3 Теоретическая база языков моделирования сетей массового обслуживания

1.3.1 Структура и параметры сети массового обслуживания

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

1.3.3 Вероятностный аппараттеории очередей

Выводы
2 ТЕОРЕТИЧЕСКИЙ АППАРАТ ЭФФЕКТИВНО ВЫЧИСЛИМЫХ АЛГОРИТМОВ
2.1 Классы сложности вычислимых функций
2.2 Реализуемость алгоритмов: абстрактный подход
2.3 Использование теории рекурсивных функций для построения эффективно вычислителимых алгоритмов

2.4 Разрешимость и реализуемость функций
Выводы
3 РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ОПТИМИЗАЦИИ ПРОЦЕССОВ ПРОГРАММНЫХ ВЫЧИСЛЕНИЙ
3.1 Формальное описание канала системы массового обслуживания и проектирование системы
3.2 Алгоритм работы системы имитационного моделирования
3.3 Описание объектов, входящих в имитационную модель
3.4 Синтаксис описания поведения узла системы массового обслуживания
3.5 Повышение эффективности программных операций с использованием техники частичные вычисления. Автоматическая генерация программ
3.6 Численные методы генерации потоков поступления и обработки заявок, реализованные в программном комплексе
3.7 Моделирование сети массового обслуживания в разработанном программном комплексе
Выводы I
4 МЕТАЯЗЫК ОПИСАНИЯ СИСТЕМ И СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ НА ОСНОВЕ АППАРАТА РЕКУРСИВНЫХ ФУНКЦИЙ

4.1 Неструктурированное описание систем массового обслуживания

4.2 Алгоритмы синтеза структурированного описания системы массового обслуживания на метаязыке
4.2.1 Алгоритм синтеза набора правил по заданной строке
4.2.2 Алгоритм синтеза набора правил по заданному набору строк
4.2.3 Алгоритм преобразования заданной структуры правил построенный по методу рекурсивного спуска
4.2.4 Алгоритм построения набора правил и модели на основе заданной входной строки
4.3 Язык описания систем массового обслуживания XML-QS
4.3.1 Структура языка описания систем массового обслуживания
4.3.2 Алгоритм построения формального распознавателя цепочек языка
4.4 Методика уточнения структуры и параметров моделируемой системы на основе разработанного метаязыка '
4.5 Алгоритм описания взаимосвязей систем массового обслуживания, входящих в сеть обслуживания
4.6 Асимптотические оценки разработанных алгоритмов
Выводы
5 РЕАЛИЗАЦИЯ И ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ СИСТЕМЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ДЛЯ ИССЛЕДОВАНИЯ ОТРАСЛЕВЫХ ИНФОРМАЦИОННЫХ СИСТЕМ
5.1 Описание программного комплекса
Интерфейс пользователя
5.2 Совершенствование методов организации и хранения данных на серверах систем автоматизированного управления железнодорожного транспорта
5.2.1 Описание системы
5.2.2 Оптимизация структуры базы данных протокольного сервера комплексной системы автоматизированного управления сортировочным процессом
5.3 Разработка систем информационного обеспечения объектов скорой медицинской помощи и методов структурирования и обработки данных в них
Выводы
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ 1 АКТЫ О ВНЕДРЕНИИ
ПРИЛОЖЕНИЕ 2 АЛГОРИТМ РАСПОЗНАВАНИЯ ЯЗЫКА XML-QS
ЛИТЕРАТУРА

ВВЕДЕНИЕ
Актуальность работы
Существует особая трактовка понятия «эффективность вычислений», смысл которой был заложен в работах Тьюринга, Поста, Черча, Клини, Гёделя, которые не могли предвидеть нынешнего прогресса в области компьютерных систем и сетей. Тем не менее, модели вычислений, заложенные в их работах, могут являться математическим фундаментом для построения эффективных программных комплексов с применением современных вычислительных систем и аппарата математического моделирования.
При решении многих практических задач выясняется, что реальные системы чрезвычайно сложны, и зачастую практически невозможно определить ряд их параметров, что исключает возможность аналитического решения. В этом случае применяется методика исследования системы с помощью имитационного моделирования (ИМ), поэтому в число этапов-ИМ входят вычислительные процедуры (эксперименты), требующие больших объемов вычислений.
Анализ существующих специализированных языков описания сложных систем и программных средств, построенных на их основе, показывает, что далеко не всегда в них используются эффективные численные методы и алгоритмы. С ростом вычислительных ресурсов компьютерных систем вопросы эффективных вычислений практически перестали рассматриваться специалистами в данной области, тем не менее, покажем, что проблемы эффективно вычислимых функций (алгоритмов) по-прежнему актуальны.
Стремительное развитие вычислительной техники привело к тому, что практически во всех отраслях народного хозяйства,были внедрены и продолжают развиваться и модернизироваться крупные корпоративные информационные системы, функционирующие на базе распределенных компьютерных сетей, обрабатывающие огромное количество разнородной информации, исходящей от множества различных источников. В связи с постоянно увеличивающимися возможностями вычислительной техники и ужесточением требований к точности математических моделей появляется необходимостью учитывать всё боль-

Функция /('(п,) при различных дисциплинах обслуживания определяется следующим образом:

ГСЯУ: (п,)
/(п,) = ц!ПП
. ч.(»)
Аг=1
н?’,

ЯХ(Я,)=ПП

А-1

", аМР(А)
1Сга-РЛ:/(п,) = П--и
у-1 (4
По существу, теорема ВСМР является следствием того факта, что баланс узла СеМО влечет локальный баланс и мультипликативную форму СеМО.
Выводы
1. Рассмотрена теоретическая база исследования сетей массового обслуживания.
2. Проанализированы преимущества и недостатки имитационного моделирования, описаны существующие подходы к имитационному моделированию.
3. Произведен анализ существующих программных средств и показаны их недостатки, приводящие к невозможности их применения для исследования предметной области данной работы. Среди недостатков выявлены:
о Эффективность алгоритмов и скорость вычислений в этих системах не анализируется и не оценивается, тогда как в системах реального времени, которые описываются и имитируются с помощью СеМО.
о Невозможность изменения целого ряда параметров системы в ходе работы модели, однако, такие изменения характерны для реальных систем, рассматриваемых в ходе исследования.