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

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

Евдокимов Алексей Викторович

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

Специальность 05 13 17 —Теоретические основы информатики

АВТОРЕФЕРАТ

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

Ростов-на-Дону - 2008 г

003170296

Работа выполнена на кафедре «Информатика» в государственном образовательном учреждении высшего профессионального образования «Ростовский государственный университет путей сообщения»

Научный руководитель

- доктор технических наук, доцент Бутакова Мария Александровна

Официальные оппоненты

- доктор технических наук, профессор Ковалев Сергей Михайлович

- кандидат технических наук, доцент Мартемьянов Сергей Васильевич

Ведущая организация Донской государственный технический

университет

Защита состоится и июня 2008 г в часов на заседании диссертационного совета Д 212 208 21 в Таганрогском технологическом институте Южного федерального университета по адресу 347928, г Таганрог, ГСГ1-17А, пер Некрасовский, 44, ауд Д-406

С диссертацией можно ознакомиться в научной библиотеке ЮФУ по адресу 344006, г Гостоп-на-Дону, ул Пушкинская 148, научная библиотека ЮФУ

Автореферат разослан « /§ » мая 2008 г

Ученый секретарь

диссертационного совета Д 212 208 21 доктор технических наук, профессор

Чернов Н И

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы

Существует особая трактовка понятия «эффективность вычислений», смысл которой был заложен в работах Тьюринга, Поста, Черта, Клини, Геделя, которые не могли предвидеть нынешнего прогресса в области компьютерных систем и сетей Тем не менее, модели вычислений, заложенные в их работах, могут являться математическим фундаментом для построения эффективных программных комплексов с применением современных вычислительных систем и аппарата математического моделирования

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

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

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

В работах Э Поста, а затем X Роджерса делается предположение и дается его обоснование о том, что «понятие общерекурсивной функции действительно является формальным эквивалентом эффективной вычислимости » Таким образом, если алгоритмы в системе ИМ построены на базе некоторых классов рекурсивных функций, то это будет означать, что они являются эффек-

тивно вычислимыми, то есть реализованными наилучшим способом из всех возможных

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

Теория алгоритмов сформировалась в 20 веке и впервые появилась в трудах Э Бореля (1912) и Г Вейля (1921) Началом систематической разработки теории алгоритмов можно считать 1936 год, когда А Черч опубликовал первое понятие вычислимой функции и привел первый пример функции, не являющейся вычислимой, а А Тьюринг и Э Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, машин Тьюринга) В дальнейшем теория алгоритмов получила развитие и трудах С Клини, Э Поста, А А. Маркова, А Н Колмогорова и других Оптимизации алгоритмов посвящена теория частичных вычислений, разработанная И Футамурой, В Ф Турчиным, А П Ершовым

Теории формальных грамматик и грамматическому разбору выражений посвящены труды таких ученых как Н Хомский, А Ахо, Д Ульман, Д Грис, Д Кнут

Теории и языкам РЕМ посвящены работы Дж Гордона, Е Сейджвика, А Лоу, В Кельтона, В В Емельянова Работы Г Буча, П Коуда, позволили создавать системы моделирования и программирования с использованием объектно-ориентированных принципов Отметим книги Л Клейнрока, Г Т Артамонова и О М Брехова по моделям функционирования ЭВМ

Современное состояние теории массового обслуживания обеспечили работы А К Эрланга и А А Маркова, А Я Хинчина, А А Боровкова, Б В Гне-денко, В А Каштанова, И Н Коваленко, Т Л Саати, Д Г Кендалла, Дж Литтла Из современных работ по СеМО следует выделить многочисленные труды В М. Вишневского, В А Ивницкого

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

Для достижения поставленной цели необходимо решение следующих задач.

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

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

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

4 Построение метаязыка описания и структурирования данных для СеМО с применением предложенной технологии оптимизации

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

6 Исследование информационных систем с использованием разработанной среды ИМ

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

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

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

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

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

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

3 Предложен метаязык структурированного описания СеМО ХМЬ-ОБ с эффективными методами вычислений, в том числе

3 1 для существующих языковых описаний СеМО разработаны алгоритмы

их преобразования к языку ХМЬ-ОБ, 3 2 разработан вычислительно-эффективный алгоритм распознавания входного языка,

3 3 показан класс СеМО, для описания которых применим данный язык

4 Разработана методика представления информационных систем на метаязыке XML-QS и алгоритмы ее применения

5 Разработаны алгоритмы линейной и полиномиальной сложности, на основе которых создано программное обеспечение для имитации СеМО

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

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

1 Разработан, внедрен и адаптирован комплекс программ для имитационного моделирования работы автоматизированных систем управления, описываемых в виде СеМО Внедрение этого комплекса позволило определить «узкие места» в системах управления и предложить обоснованные рекомендации по их устранению

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

3 На основе статистического анализа потоков данных в исследуемых СеМО выявлено наличие пиковых режимов работы, как случайных, возникающих в случае нештатных ситуаций, так и циклических, связанных с особенностями технологического процесса, приводящих к сбоям в работе систем, неудовлетворительному качеству обслуживания клиентов, несвоевременности предоставления информации, а также предложены методы по устранению этих недостатков В соответствии с выявленными особенностями потоков данных разработана методика анализа и контроля использования системы обслуживания СМП и комплексной системы автоматизированного управления сортировочным процессом (КСАУ СП)

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийском симпозиуме по прикладной и промышленной математике (2007 г Сочи), на Международной конференции «Математика Экономика Образование» (2006 г, Новороссийск), на Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (2006 г, Новочеркасск), Международной научно-практической конференции «Экономико-организационные проблемы проектирования и применения информационных систем» (2006 г, Кисловодск), на научно-теоретических и научно-практических конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (2003 - 2007 гг)

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

- эффективно вычислимые алгоритмы на основе рекурсивных функций,

- процедура оптимизации программных модулей на базе частичных вычислений,

- метаязык описания систем и сетей массового обслуживания ХМЬ-С^,

- принципы и методы представления СеМО,

- метод преобразования формальных описании СеМО к языку ХМЬ-<35,

- алгоритм распознавания разработанного метаязыка Публикации

По результатам проведенных теоретических и экспериментальных исследований опубликовано 16 печатных работ, из них 3 - в журналах, включенных в список рекомендованных ВАК

Структура н объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы и приложений Объем диссертационной работы - 162 страницы, из них основного текста 135 с

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим предлагаемую методику на примере СеМО, приведенной на

рис 1

Рис 1 Пример СеМО с отказами и повторными вызовами

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

Пусть также определена функция [1 если г- у,

0,

где 2 - индикатор сравнения

Таким образом, для каждого из узлов приведенно1 о примера справедливо.

/¡(*>У) = *,(*)»

/2(х,у) = (*2 (*) + / (5,2)) X у) + (?2 (*) + /4 (х,2)) X £(4, у), /З(х,у) = (,(х) + /2(х,3), /4(х,у) = (4(х) + /.,(Х,4), Л(х,У) = (5(Х) + /4(Х,5) Для случая, приведенного на рис 2, введем дополнительный узел п (узел 6) При этом следует отметить, что 1п = О

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

Суммарное время пребывания заявки в системе будет описываться функцией /„, вид которой зависит от конфигурации системы, п - узел в котором завершается обслуживание заявки Для примера рис 2

ШУ) = ШУ) = (М*) + Мх,3))х8(5уУ) + (ф) + /4(х,3)) х 8(4,у)

Приведенные формулы удовлетворяют следующему свойству ц-рекурсивных функций

Функция f называется определенной на отношении R с помощью JI-рекурсии, если

1 для (Vit )(Эу)/?(х,у),

2 f(5c) = \iyR(x,y), где \iyR{x,y) - наименьшее у, для которого выполняется отношение R(x,y)

Аналогично,f определено из guh с помощью ц-рекурсии, если

1 (Vx)(3y)g(x,y) = 0,

2 f(x) = w(g(x,y) = 0) □

Далее в главе на основе свойств рекурсивных функций выделен класс эффективно-вычислимых функций Приведены теоремы Черча, Клини, Гедсля, которые определяют минимальный класс рекурсивных функций, являющийся эффективно вычислимым На базе данного класса в следующих главах разрабатывается методика имитационного моделирования На основе теорем описаны способы преобразования функций системы ИМ с целью повышения их вычислительной эффективности

В третьей главе разработаны алгоритмы оптимизации процессов вычислений в системах ИМ СеМО Для этого приведено описание канала системы массового обслуживания в терминах предлагаемого далее метаязыка Рассмотрены элементы системы и их взаимосвязь Предложен метод проектирования системы ИМ в виде объектно-ориентированной модели Приведено описание полученных в ходе проектирования элементов системы Разработан синтаксис описания поведения узла системы массового обслуживания и примеры его применения

Общий алгоритм работы системы ИМ

1 Начальная инициализация

а чтение и анализ информации о СеМО, б построение конфигурации модели, в установка текущего времени системы t =0, г инициализация входного канала К*, д начальная инициализация каналов модели

2 Определение следующего момента возникновения: события

а определение времени ближайшего события tn <„=mm(r(/\o),nim(T(Kl)), Г(А',)>0, где ЦК,) - функция, определяющая время завершения обработки ближайшей заявки в канале К, Если канал К, свободен, то Т\К,)=со

3 Сбор статистических сведений о ходе моделирования

4 Переход к следующему этапу моделирования

а Направление обработанной заявки в следующий канал, принятие решения о завершении обслуживания заявки, принятие решения об отказе обслуживания (данное решение принимается диспетчером модели на основе информации о конфигурации СеМО), б Установка модельного времени t=t„ в Если t>tm-dX, то переход к п 5, иначе п 2 5. Останов

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

^cmam

Icmam - статические данные, известные до начала вычислений, 1йш - динамические (исходные) данные программы,

0 - выходные данные

Процесс частичных вычислений преобразует (prog,Iclnam) в (prog*) вычислением всех статических данных на стадии компиляции Таким образом, полученная после преобразования с использованием метода частичных вычислений программа, является более эффективной, чем исходная Метод частичных вычислений всегда порождает корректную программу

out = [[ source\]s input = [[int]] [source, input] = [[[[muc]] [int, source] ]] input = [[target]] input

int — интерпретатор,

mix - процедура частичных вычислений

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

1 Интерпретация исходного кода программы, напитанной на языке S

2 Преобразование исходной программы с использованием методики частичных вычислений

3 Генерация результирующей преобразованной программы на языке L Выражение [target] = [mix] int, source часто называется первой проекцией Футамуры

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

При вычислении с использованием простейшего генератора псевдослучайных величин, как правило, используется следующая формула генерации х1+1 = {х* a + b) mod с, где а,Ь,с - постоянные величины Случайная величина в диапазоне [0,1) получается вычислением r = xHi/c Далее, равномерное распределение генерируется по формуле f(c],c2) = r*ci+c2

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

,, . (xt*a + b) mod с Л

/(с, ,с2) = ^-1-* с, + с2

с

£

к виду f(cvc2) = ((xl*a + b) modc)*c'+c2, где с' = —, позволяя обойтись без

с

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

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

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

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

E=F{+F|-F}

F=U{*U|/U}

U=T|-T

Т=«(»Е«)»|1|<число>

1=<идентификатор>|<идентификатор>"("{Е{,Е}}")"

Аналогично алгоритмам, приведенным в главе 3, примем следующие обозначения Пусть исходные данные -ST- входная строка

Для построения алгоритма определим некоторый объект, представляющий собой лексический анализатор Определим следующие методы объекта Lex InitStr(ST) - выполняет начальную инициализацию анализатора, Lex JiestartQ - выполняет возврат анализатора на первую лексему, Lex GetToken(TOK, TKL) - возвращает следующую лексему по заданной входной строке и переходит на следующую лексему,

Lex NextToken(TOK, TKL) - возвращает следующую лексему по заданной входной строке и не переходит на следующую лексему, ТОК - следующая лексема

Отличием от алгоритма лексического анализатора, приводимого в главе 3, будет другой набор классов лексем TKL

1 арифметическая операция (+,-,*,/),

2 идентификатор,

3 число,

4 скобка «(» или «)»,

5 символ«,»

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

В алгоритме применена процедура транслировать_ выражение(), относящаяся к непосредственной реализации процедуры трансляции и в данном разделе не описываемая Также используется функция семантиче-ское_действие(тип действия,параметр!, параметр2) Эта функция выполняет семантические действия над аргументами, не выполняя трансляции, а генерируя результат непосредственно в выходной поток

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

Процедура E(static)

Определить переменную StaticAll

вызов F(Static)

StaticAll = Static

Lex NextToken(TOK,TKL)

Пока (TKL=1) и ((TOK='+') или (ТОК='-'))

Lex GetToken(TOK,TKL)

вызов F(Static)

Если (Staticonull) и (StaticAllonull)

тогда StaticAll =Семантическое_действие(ТОК,Static,StaticAll) иначе транслировать Bbipa3KeHHe(),StaticAlI=mill конец если

Lex NextToken(TOK,TKL) Конец Пока Static =StaticAll

Конец процедуры Е

Процедура F(static)

Определить переменную StaticAll

вызов U(Static)

StaticAll = Static

Lex NextToken(TOK,TKL)

Пока (TKL=1) и ((TOK='*') или (ТОК=7'))

Lex GetToken(TOK,TKL)

вызов U(Static)

Если (Staticonull) и (StaticAllonull)

тогда StaticAlI ^СемгчпическоелействиеСГОК,Static,StaticAlI) иначе транслировать Bbipaxeai!e(),StaticA]l=null конец если

Lex NextToken(TOK,TKL) Конец Пока Static =StaticAU Конец процедуры F

Процедура U(static)

Lex NextToken(TOK,TKL) Если (TKL=1) и ((ТОК='-') Lex GetToken(TOK,TKL) Вьвов T(Static)

Если (Staticonull) тогда StaticAlI = Семантичсское_действие(ТОК,Static,null) иначе транслировать выраление() конец если (StaticOnuü) иначе

Вызов T(Static) Конец если (TKL=1) Конец процедуры U

Процедура T(static)

Lex NextToken(TOK,TKL) Если (TKL=4) и ((ТОК='С) тогда

Lex GetToken(TOK,TKL) Вызов E(static) Lex GetToken(TOK,TKL) Если (TKL04) или ((ТОКо')') конец если

иначе если TKL=3 тогда Static иначе I(static) Конец если Конец процедуры

Процедура I(static)

Определить переменную StaticAlI Определить переменную Id Lex GetToken(TOK,TKL)

Если (TKLo2) тогда синтаксическая_ошибка(«ожидается идентификатор ») конец если

Lex NextToken(TOK,TKL) Если (TKL=4) тогда

Lex GetToken(TOK,TKL) Lex NextToken(TOKJKL) Пока (TKLo4) и (ТОКо")") Lex GetToken(TOK,TKL) Вызов E(Static)

Если Static=null тогда StaticAlI =null, конец если Lex NextToken(TOK,TKL)

Если (TKL<>4 или ТОКо")") и TKL05 тогда синтаксическая_ошибка

(«Ожидается ) или,»)

Конец пока

Lex GetToken(TOK,TKL)

тогда синтаксическая_ошибка(«ожидается)») =семантические_действия(пи11,ТОК,null)

Если StaticAllonull тогда Static =Семантические_Действня( id,StaticAll,Null) Конец если иначе

Static =Семантические_Действия(пи11,Т0К)пи11) Если Static=null тогда Транслировагь_выражение(), Конец если (Static=null) Конец если (TKL=4) Конец процедуры I

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

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

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

Четвертая глава посвящена разработке метаязыка структурированного описания СеМО XML-QS В главе рассмотрены различные способы описания структуры и свойств СеМО и выявлен класс систем, которые невозможно формально описать с помощью данных методов Приведены алгоритмы преобразования различных форм описания систем массового обслуживания Разработан алгоритм анализа (синтаксический анализатор) языка XML-QS

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

Выделены следующие элементы языка

Тег Смысловое значение

<СМО> Заголовок описания СМО

<УЗЛЫ> Заголовок блока описания узлов СМО

<УЗЕЛ> Заголовок блока описания узла СМО

<Идентификатор> Элемент описания уникального идентификатора узла

<Закон обслуживания> Элемент описания закона обслуживания

<Формула> Элемент описания формулы закона распределения времени обслуживания заявок

<Параметры_закона> Заголовок описания параметров закона обслуживания

< Параметр> Заголовок описания параметра закона обслуживания

<Имя_параметра> Элемент, описывающий наименование параметра

<3начение параметра> Элемент, описывающий значение параметра

<Входная очередь> Заголовок описания

<Длина_очереди> Элемент, описывающий значение параметра «длина входной очереди»

<Входной_поток> Элемент описания закона распределения времени поступления заявок

<Таблица_связей> Заголовок описания таблицы связей между элементами

Идентификатор источника> Элемент описания источника заявок

<Приемник> Заголовок описания приемника

<Идентификатор приемника> Элемент описания приемника заявок

<Вес связи> Элемент описания параметра связи

<Правило> Элемент описания правила использования данной связи

Приведена общая структура и вложенность элементов языка описания СеМО, показанная на рис 3

Рис 3 Общая структура и вложенность элементов языка

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

В нотации Бэкуса-Наура структура языка описания СеМО будет выглядеть так

СеМО = "<СеМО>" СМО {СМО} СеМОЬш!« "</СеМО>"

СМО ="<СМО>" CMOID NODES SOURCE CMOLmks "</CMO>" NODE = NODE{NODE}

NODE = "<УЗЕЛ>" NODEID DISTR QUEUE "</УЗЕЛ>"

NODEID = "<ИДЕНТИФИКАТОР>' NUMBER"</H4EHTH'J)HKATOP>" CMOID = "<ИДЕНТИФИКАТОР>"ШМВЕК"</ИДЕШИФИКАТОР>" DISTR = "<Закон_распределения>" STMT|IDENTITIER "</Вакон_распределеиия>" QUEUE = "<Bx0flHaH_04epe®>"QUEUELEN "</Входная_очередь>" SOURCE = "<<Входной_поток>>" DISTR PARAMS QUEUE

"<У<Входной_поток>>" STMT ="<OOPMyjIA>"STMTPROGRAM"</ ФОРМУЛА>"

PARAMS = "<Параметры_закона>" PARAM{PARAM} "</Параметры_закона>" PARAM = "<Параметр>" PARAMNAME "=" PARAMVALUE "< Параметр>" PARAMNAME = "<Имя_параметра>" IDENTITIER "<Имя_парачетра>" PARAMVALUE = "<3начение_параметра> " SIGNEDFLOATNUMBER "</Значение_параметра>" CeMOLink = " <Таблица связей>" CeMOLinkELEM " </Таблица_связей>" CeMOLmkELEM =" <Идентификатор_источника>" <CMOID>

"</Идентификатор_источника>" CeMOLinkDi sts CeMOLinkDests = "<Приемник>" CeMOLinkDest{ CeMOLinkDest} "<Я1риемпик>" CeMOLinkDest = CeMOLmkDestID CeMOLinkDestWeigth CeMOLinkDestRule CMOLinkDestRule = "<Правило>" IDENTIFIER "</Прагшло>" CeMOLinkDestID = "<Идентификатор_приемника>" IDENTIFIER

"</Иде1пификатор_приемника>" CeMOLinkDestWeigth = "<Вес_связи>" PARAMS|SIGNEDFLOATNUMBER "<Вес_связи>"

CMOLink = " <Таблица_связей>"<СМОЕткЕЕЕМ> " </Таблица_овязей>" CMOLinkELEM =" <Идентификатор_источника>" <NODEID>

"<УИдентификатор_источника>" CMOLinkDests CMOLinkDests = "<Приемник>" CMOLinkDest{ CMOLinkDest} "</Приемник>" CMOLinkDest = CMOLmkDestlD CMOLinkDestWeigth CMOL nkDestRule CMOLinkDestRule ="<Правило>" IDENTIFIER "</Правило>" CMOLmkDestlD = "<Идентификатор_приемника>" IDENTIFII R

'Ч/Идентификатор_приемника>" CMOLinkDestWeigth = "<Вес__евязи>" PARAMS|SIGNEDFLOATNUMBER "<Вес_связи>"

QUEUELEN = "<Длина_очереди>" NUMBER "<Длина_очереди>" NUMBER =DIGIT {DIGIT}

UNSIGNEDFLOATNUMBER =DIGID {DIGIT}" "{DIGIT}

SIGNEDFLOATNUMBER ="+"|"-"|" " UNSIGNEDFLOATNUMBER ["E+'T'E-" NUMBER] IDENTIFIER =LETTER{LETTER|DIGIT} DIGIT ={"0"|"Г'|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"} LETTER ={"A" "Z"|"a" "z'T'A" "Я"|"а" "я"}

Приведенный язык описания СеМО позволяет в качестве закона распределения выбрать либо один из заранее заданных законов (правило DISTR ="<Закон_распределения>" ЮЕЫТ1Т1Е11"</Заксн_распределения>"), либо описать его с помощью языка программирования, аналогичного я ¡ыку Паскаль (правило DISTR ="<Закон_распределения>"8ТМТ "</Закон_ распределения^')

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

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

— инвариантность описания объектов,

— компактность представления схемы СеМО,

— однозначность идентификации узлов СеМО,

- обеспечение корректности связей между элементами СеМО (ссылочной целостности),

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

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

Оценка сложности полученных алгоритмов

Название алгоритма Параметры Оценки сложности

0 О о

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

Процедура обработки сообщений в объектной модели СеМО С\ап

Процедура генерации объектной модели СеМО п - дайна входной строки С\п+ (Уо&и С,и

Основной алгоритм синтаксического разбора языка ХМЫЗв С\п

Алгоритм анализа ограничений объектной модели языка хмызв СУ+ С2П^2П

Подпрограмма формирования связей в объектной модели п - число объектов

Процедура анализа и оптимизации синтаксического дерева ХМЬ-ОБ п - длина входной строки СггАо&П

Алгоритм оптимизации процесса генерации входных потоков и потоков обслуживания, задаваемых пользователем п - длина входной строки л10{*2» Сщ'

Примечание С, - постоянные, характеризующие время работы алгоритма

В пятой главе приведено описание разработанного программного комплекса и его применения для исследования СеМО Разработанные

теоретические основы создания программных систем на базе вычислитетьно-эффективных алгоритмов использованы автором при сопровождении подсистем поддержки принятия решений в системах СМП и КСАУ СП Показаны результаты ИМ с их использованием

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

В приложениях приведены алгоритмы моделирования, тексты npoi рамм и акты о внедрении результатов работы

Основные результаты диссертации опубликованы в работах:

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

1 Евдокимов А В Построение языковых моделей для описания сложных объектов при проведении имитационного моделирования систем массового обслуживания Известия вузов Северо-Кавказский регион 1ехн науки №6(142),

2007 г С 5 - 9

2 Евдокимов А В Использование техники частичных вычислений для оптимизации процессов обработки информации в программных комплексах // Журнал научных публикаций аспирантов и докторантов - Курск, № 2, февраль

2008 г С 184-188

3 Евдокимов А В Построение языка описания сложных объектов при проведении имитационного моделирования с использованием теории массового обслуживания // Обозрение прикладной и промышленной математики -М ОПиПМ, 2007, т 14, вып 6 С 1102

Другие работы, в которых опубликованы резулыпа/ь ы диссертации

4 Бутакова MA, Евдокимов А В Разработка эффективных алгоритмов для имитационного моделирования сетей массового обслуживания на базе математического аппарата теории рекурсивных функций // Труды РГУПС, № 1, 2008 г С 35-41

5 Бутакова MA , Евдокимов А В Разработка техно югии моделирования систем и сетей массового обслуживания с использованием теории рекурсивных функций // Компьютерные технологии в науке, производстве, социальных и экономических процессах Материалы VIII Междунар науч -практ конф, г Новочеркасск, 16 нояб 2007 г / Юж-Рос гос техн ун т (НПИ) - Новочеркасск ЮРГТУ, 2007 С 15-18

6 Евдокимов А В Язык описания систем массового обслуживания на железнодорожном транспорте Статья Сборник Труды всероссийской научно-практической конференции «Транспорт-2007» Часть 1 - Ростов-на-Дону, РГУПС, 2007 С 45

7 Бутакова MA, Евдокимов АВ, Лябах H H Комплект программ для имитационного моделирования систем массового обслуживания Свидетельство об отраслевой регистрации разработки № 6038 от 20 04 2006

8 Евдокимов А В Имитационное моделирование систем массового обслуживания на железнодорожном транспорте // Труды XIV Международной

конференции «Математика Экономика Образование», июнь 2006, г Новороссийск - Ростов н/Д, изд-во «ЦВВР», 2006 С 130-133

9 Евдокимов А В Моделирование объектов транспорта на основе теории массового обслуживания // Труды VII Международной научно-практической конференции «Экономико-организационные проблемы проектирования и применения информационных систем» - Кисловодск, 2006 С 47 -50

10 Евдокимов А В, Курбесов А В Программный комплекс поддержки национальных проектов в области здравоохранения Журнал «Главный врач юга России», - Ростов н/Д, № 2, 2006 С 14

11 Евдокимов А В Программный комплекс имитационного моделирования систем массового обслуживания В сб Труды всероссийской научно-практической конференции «Транспорт-2006» Часть 2 -Ростов-на-Дону, РГУПС, 2006 С. 45-46

12 Евдокимов А В Методика описания систем массовою обслуживания при моделировании объектов железнодорожного транспорта // Извес гия вузов Северо-Кавказский регион Приложение к № 4 Новочеркасск, 2006 г стр 17 -20

13 Евдокимов А В Моделирование объектов железнодорожного транспорта на основе использования теории массового обслуживания Сборник Труды всероссийской научно-практической конференции «Транспорт-2005» Часть 1 - Ростов-на-Дону, РГУПС, 2005 С 96-97

14 Евдокимов А В, Шелехов К К Автоматизация работы станции скорой медицинской помощи Журнал «Главный врач юга России», №3,2005 С 28

15 Майоров В Д, Евдокимов А В Схемотехнический редактор Сб тр Всероссийской научно-практической конференции «Транспорт-2004» Часть 1 -Ростов-на-Дону, РГУПС, 2004 С 45-46

16 Генцелъман ТВ, Евдокимов А В, Курбесов А В Автоматизация контроля счетов в страховой медицинской организации / Сб тр «Десятилетие обязательного медицинскою страхования опыт, проблемы, перспективы», -Ростов-на-Дону, 2003 С 152-154

Личный вклад автора в работах, выполненных в соавторстве

/2/ - разработка алгоритмов преобразований вычислимых функций на основе проекций Футамуры, /4,5/ - усовершенствование и применение математического аппарата теории рекурсивных функций, /7/ ~ разработка эффективных вычислительных процедур, /10, 14 - 16/ - разработка программного обеспечения объектов автоматизации

Евдокимов Алексей Викторович

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

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

Формат 60x84/16 Бумага офсетная Печать офсетная Уел печ л

Тираж 100 Заказ №5910.

Ростовский государственный университет путей сообщения Ризография РГУПСа

Адрес университета 344038, Ростов н/Д, пл Ростовского Стрелкового полка народного ополчения, 2

ВВЕДЕНИЕ

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

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

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

1 < • \ «

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

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

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

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

Выводы

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

2.1 Классы сложности вычислимых функций

2.2 Реализуемость алгоритмов: абстрактный подход

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

2.4 Разрешимость и реализуемость функций 62 Выводы

3 РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ОПТИМИЗАЦИИ ПРОЦЕССОВ ПРОГРАММНЫХ ВЫЧИСЛЕНИЙ

3.1 Формальное описание канала системы массового обслуживания и проектирование системы

3.2 Алгоритм работы системы имитационного моделирования

3.3 Описание объектов, входящих в имитационную модель

3.4 Синтаксис описания поведения узла системы массового обслуживания

3.5 Повышение эффективности программных операций с использованием техники частичные вычисления. Автоматическая генерация программ

3.6 Численные методы генерации потоков поступления и обработки заявок, реализованные в программном' комплексе

3.7 Моделирование сети массового обслуживания в разработанном программном комплексе 86 Выводы »

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 Асимптотические оценки разработанных алгоритмов 115 Выводы

5 РЕАЛИЗАЦИЯ И ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ СИСТЕМЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ДЛЯ ИССЛЕДОВАНИЯ ОТРАСЛЕВЫХ ИНФОРМАЦИОННЫХ

СИСТЕМ

5.1 Описание программного комплекса 119 Интерфейс пользователя

5.2 Совершенствование методов организации и хранения данных на серверах систем автоматизированного управления железнодорожного транспорта

5.2.1 Описание системы

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

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

Выводы

Актуальность работы

Существует особая трактовка понятия «эффективность вычислений», смысл которой был заложен в работах Тьюринга, Поста, Черча, Клини, Гёделя, которые не могли предвидеть нынешнего прогресса в области компьютерных систем и сетей. Тем не менее, модели вычислений, заложенные в их работах, могут являться математическим фундаментом для построения эффективных программных комплексов с применением современных вычислительных систем и аппарата математического моделирования.

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

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

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

В работах Э. Поста, а затем X. Роджерса делается предположение и дается его обоснование о том, что «понятие общерекурсивной функции действительно является формальным эквивалентом эффективной вычислимости.». Таким образом, если алгоритмы в системе ИМ построены на базе некоторых классов рекурсивных функций, то это будет означать, что они являются эффективно вычислимыми, то есть реализованными наилучшим способом из всех возможных.

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

Теория алгоритмов сформировалась в 20 веке и впервые появилась в трудах Э. Бореля (1912) и Г. Вейля (1921). Началом систематической разработки теории алгоритмов можно считать 1936 год, когда А.Черч опубликовал первое понятие вычислимой функции и привел первый пример функции, не являющейся вычислимой, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, машин Тьюринга). В дальнейшем теория алгоритмов получила развитие в трудах С. Клини, Э. Поста, A.A. Маркова, А.Н. Колмогорова и других. Оптимизации алгоритмов посвящена теория частичных вычислений разработанная И. Футамурой, В.Ф. Турчиным, А.П. Ершовым.

Теории формальных грамматик и грамматическому разбору выражений посвящены труды таких ученых как Н. Хомский, А. Ахо, Д. Ульман, Д. Грис, Д. Кнут.

Теории и языкам ИМ посвящены работы Дж. Гордона, Е. Сейджвика, А. Jloy, В. Кельтона, В.В. Емельянова. Работы Г. Буча, П. Коуда, позволили создавать системы моделирования и программирования с использованием объектно-ориентированных принципов. Отметим книги JI. Клейнрока, Г.Т. Артамонова и О.М. Брехова по моделям функционирования ЭВМ.

Современное состояние теории массового обслуживания обеспечили работы. А.К. Эрланга и A.A. Маркова, А.Я. Хинчина, A.A. Боровкова, Б.В. Гне-денко, В.А. Каштанова, И.Н. Коваленко, Т.Л. Саати, Д.Г. Кендалла, Дж. Литтла. Из современных работ по СеМО следует выделить многочисленные труды В.М. Вишневского, В.А. Ивницкого.

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

Для достижения поставленной цели необходимо решение следующих задач.

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

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

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

4. Построение метаязыка описания и структурирования данных для СеМО с применением предложенной технологии оптимизации.

5. Разработка методики представления и моделирования СеМО, описывающей реальные информационные системы с помощью разработанного метаязыка.

6. Исследование информационных систем с использованием разработанной среды ИМ.

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

В диссертационном исследовании используются принципы системного, структурно-функционального и сравнительного анализа.

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

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

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

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

3. Предложен метаязык структурированного описания СеМО ХМЬ-(38 с эффективными методами вычислений, в том числе:

3.1.для существующих языковых описаний СеМО разработаны алгоритмы их преобразования к языку ХМЬ-С^Б;

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

3.3.показан класс СеМО, для описания которых применим данный язык.

4. Разработана методика представления информационных систем на метаязыке ХМЬ-С^Б и алгоритмы ее применения.

5. Разработаны алгоритмы линейной и полиномиальной сложности, на основе которых создано программное обеспечение для имитации СеМО.

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

Практическую ценность представляют следующие результаты.

1. Разработан, внедрен и адаптирован комплекс программ для имитационного моделирования работы автоматизированных систем управления, описываемых в виде СеМО. Внедрение этого комплекса позволило определить «узкие места» в системах управления и предложить обоснованные рекомендации по их устранению.

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

3. На основе статистического анализа потоков данных в исследуемых СеМО выявлено наличие пиковых режимов работы, как случайных, возникающих в случае нештатных ситуаций, так и циклических, связанных с особенностями технологического процесса, приводящих к сбоям в работе систем, неудовлетворительному качеству обслуживания клиентов, несвоевременности предоставления информации, а также предложены методы по устранению этих недостатков. В соответствии с выявленными особенностями потоков данных разработана методика анализа и контроля использования системы обслуживания СМП и комплексной системы автоматизированного управления сортировочным процессом (КСАУ СП).

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийском симпозиуме по прикладной и промышленной математике (2007 г. Сочи), на Международной конференции «Математика. Экономика. Образование» (2006 г., Новороссийск); на Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (2007 г.,

Новочеркасск); Международной научно-практической конференции «Экономико-организационные проблемы проектирования и применения информационных систем» (2006 г., Кисловодск), на научно-теоретических и научно-практических конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (2003 - 2007 гг.).

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

- эффективно вычислимые алгоритмы на основе рекурсивных функций;

- процедура оптимизации программных модулей на базе частичных вычислений;

- метаязык описания систем и сетей массового обслуживания ХМЬ-С)8;

- принципы и методы представления СеМО;

- метод преобразования формальных описаний СеМО к языку ХМЬ-С)8;

- алгоритм распознавания разработанного метаязыка.

Публикации

По результатам проведенных теоретических и экспериментальных исследований опубликовано 16 печатных работ, из них 3 — в журналах, включенных в список рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы и приложений. Объем диссертационной работы - 162 страницы, из,них основного текста 135 с.

Основные результаты диссертационного исследования состоят в следующем.

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

2. Разработаны методы структуризации данных в системах ИМ, на основе которых предложен метаязык описания данных ХМЬ-С>8.

3. Метаязык ХМЬ-РЭ построен на основе вычислительно эффективных процедур, использующих аппарат теории рекурсивных функций.

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

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

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

ЗАКЛЮЧЕНИЕ

1. Алехин М.Ю. Применение теории массового обслуживания для решения производственных задач. — JL: ЛКИ, 1989.

2. Афанасьев А. Н. Формальные языки и грамматики: Учебное пособие. -Ульяновск: УлГТУ, 1997. 84 с.

3. Ахо A.B., Сети Р., Ульман Д.Д. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ. М.: Мир, 1978 -792 с. '

4. Ахо A.B., Ульман Д.Д. Теория синтаксического анализа, перевода и компиляции. Т.2. Компиляция. -М.: Мир, 1978, -812 с.

5. Ахо A.B., Ульман Д.Д. Теория синтаксического анализа, перевода и компиляции. Т.З. Компиляция. -М.: Мир, 1978, -778 с.

6. Берштейн Л.С., Боженюк A.B. Нечеткие модели принятия решений: дедукция, индукция, аналогия: Монография. Таганрог: Изд-во ТРТУ, 2001.-110 с.

7. Бочаров П.П. Сеть массового обслуживания с сигналами со случайной задержкой // Автоматика и телемеханика. № 9. - 2002. - С. 85-96.

8. Бочаров П. П., Печинкин А. В. Теория массового обслуживания. М.: Изд-во РУДН, 1995.

9. Бржезовский А. В., Корсакова Н. В., Фильчаков В. В. Лексический и синтаксический анализ. Формальные языки и грамматики. — JL: ЛИАП, 1990, — 31с.

10. Бу такова М.А., Евдокимов A.B., Лябах H.H. Комплект программ для имитационного моделирования систем массового обслуживания. Свидетельство об отраслевой регистрации разработки № 6038 от 20.04.2006.

11. Бутакова М.А., Евдокимов A.B. Разработка эффективных алгоритмов для имитационного моделирования сетей массового обслуживания на базе математического аппарата теории рекурсивных функций // Труды РГУПС, № 1, 2008 г. С. 34 40.

12. Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989. — 360 с.

13. Волкова И. А., Руденко Т. В. Формальные языки и грамматики. Элементы теории трансляции. — М.: Диалог-МГУ, 1999. — 62 с.

14. Генцелъман Т.В, Евдокимов A.B., Курбесов A.B. Автоматизация контроля счетов в страховой медицинской организации / Сб. тр. «Десятилетие обязательного медицинского страхования: опыт, проблемы, перспективы», — Ростов-на-Дону, 2003: С. 152 154.

15. Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. — М.: Наука, 1965. -210с.

16. Гнеденко Б.В., Коваленко H.H. Введение в.теорию массового обслужива-. ния. М.: КомКнига, 2005,-400с.

17. Гордеев А. В., Никитин А. В., Филъчаков В. В. Организация пакетов прикладных программ: Учебное пособие. — Л.: ЛИАП, 1988, — 78 с.

18. Гордеев В.А., Молчанов А.Ю. Системное программное обеспечение. Учебник. Санкт-Петербург. Изд. «Питер», 2001. -736 с.

19. Д. Ван Тассел. Стиль, разработка, эффективность, отладка и испытание программ. М.: Мир, 1985. - 332 с.

20. Дворянкин А. И. Основы трансляции: Учебное пособие. — Волгоград: ВолгГТУ, 1999. 80 с.

21. Дынкин Е. Б. Марковские процессы. — М.: Физматгиз, 1963.

22. Дудин А.Н., Клименюк В.И., Царенков Г.В. Расчет характеристик однолинейной системы обслуживания с групповым Марковским потоком, полумарковским обслуживанием и конечным буфером // Автоматика и телемеханика. №8. - 2002. - С. 87-101.

23. Евдокимов A.B. Построение языковых моделей для описания сложных объектов при проведении имитационного моделирования систем массового обслуживания. Известия вузов. Северо-Кавказский регион. Техн. науки. № 6(142), 2007 г. С. 5 9.

24. Евдокимов A.B. Шелехов К.К. Автоматизация работы станции скорой медицинской помощи. Журнал «Главный врач юга России», №3, 2005. С. 28.

25. Евдокимов A.B. Моделирование объектов железнодорожного транспорта на основе использования теории массового обслуживания. Сборник Труды всероссийской научно-практической конференции «Транспорт-2005». Часть 1. Ростов-на-Дону, РГУПС, 2005. С. 96 - 97.

26. Евдокимов A.B. Методика описания систем массового обслуживания при моделировании объектов железнодорожного транспорта // Известия вузов. Северо-Кавказский регион. Приложение к № 4. Новочеркасск, 2006 г. стр. 17-20.

27. Евдокимов A.B. Программный комплекс имитационного моделирования систем массового обслуживания. В сб.: Труды всероссийской научно-практической конференции «Транспорт-2006». Часть 2. -Ростов-на-Дону, РГУПС, 2006. С. 45 46.

28. Евдокимов A.B. Имитационное моделирование систем массового обслуживания на железнодорожном транспорте // Труды XIV Международной конференции «Математика. Экономика. Образование», июнь 2006, г. Новороссийск-Ростов н/Д, изд-во «ЦВВР», 2006. С. 130 133.

29. Ъ5.Евдокимов A.B. Курбесов A.B. Программный комплекс поддержки национальных проектов в области здравоохранения. Журнал «Главный врач юга России», № 2, 2006. С. 14.

30. ЪЬ.Евдокимов A.B. Язык описания систем массового обслуживания на железнодорожном транспорте. Статья Сборник Труды всероссийской научно-практической конференции- «Транспорт-2007» Часть Г. Ростов-на-Дону, РГУПС, 2007. С. 45.

31. Евдокимов A.B. Построение языка описания сложных объектов при проведении имитационного моделирования с использованием теории массового обслуживания // Обозрение прикладной и промышленной математики. ОПиПМ, 2007, т.14, вып. 6, с.1102.

32. Жаков В. И., Коровинский В: В., Филъчаков В. В. Синтаксический анализ и генерация кода. — СПб:: ГААП, 1993. — 26 с.

33. Заде Л. Основы нового подхода к анализу сложных систем и процессов принятия»решений // Математика сегодня М:: Знание, 1973. -58 с.40.3аде JJ.A. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976. - 165 с.

34. Ивахненко А.Г., Мюллер И.А. Самоорганизация прогнозирующих моделей. Киев: Техника, 1985; Берлин ФЕБ Ферлаг Теник, 1984. - 219 с.

35. АЪ.Ивницкий В.А. Теория сетей массового обслуживания. М.: Изд-во физ.-мат. лит-ры, 2004.

36. Ивченко Г. И., Каштанов В. А., Коваленко И. Н. Теория массового обслуживания. — М.: Высшая школа, 1982, -324 с.

37. Киндлер Е. Языки моделирования / Пер. с чешского. — М.: Энергоатом-издат, 1985. -456 с.4Ь.Клейнрок Л. Вычислительные системы с очередями. — М.: Мир, 1979, -276 с.

38. Клименюк В.И. Многолинейная система массового обслуживания с групповым Марковским входным потоком и повторными вызовами // Автоматика и телемеханика. -№8. -2001, с. 97-108. .

39. Клини С.К. Введение в метаматематику. М.: Издательство иностранной литературы. 1952 г., 524 с

40. Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. -М., 1976 г. -879 с.

41. Кнут Д. Искусство программирования для ЭВМ. т.2. Получисленные алгоритмы. -М., 1977 г. -723 с.

42. Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск. -М., 1978 г. -827 с.

43. Компаниец Р. И., Манъков Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов/Учебное пособие для высших и средних учебных заведений. СПб.: КОРОНА-принт, 2000. - 256 с.

44. Концептуальное моделирование информационных систем./Под ред. В. В. Фильчакова. СПб.: СПВУРЭ ПВО, 1998. - 356 с.

45. Кэнту М. Delphi 5 для профессионалов. — СПб.: Питер, 2001.

46. JIoy A.M., Келътон В Д. , Имитационное моделирование. Классика CS; Изд. «Питер», 2004, -847 с.

47. Льюис Ф. и др. Теоретические основы построения компиляторов. — М.: Мир, 1979. 483 с.

48. Лябах H.H., Бутакова М.А. Системы массового обслуживания: развитие теории, методология моделирования и синтеза: Монография. Южн. науч. центр РАН, Рост. гос. ун-т путей сообщения. — Ростов н/Д, 2004.

49. Лябах H.H., Шабелъников А.Н. Техническая кибернетика на железнодо-. рожном транспорте: Учебник. — Ростов н/Д: Изд-во СКНЦ, 2002. -283 с.

50. Майоров В.Д. Евдокимов A.B. Схемотехнический редактор. Сб. тр. Всероссийской научно-практической конференции «Транспорт-2004». Часть 1. Ростов-на-Дону, РГУПС, 2004. С. 45 -46.

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

52. Мельников Б. Ф. Подклассы класса контекстно-свободных языков. — М.: Изд-во МГУ, 1995.- 174 с.

53. Модель оптимизации технологии эксплуатационной работы СевероКавказской железной дороги и Южного региона / МПС РФ. Ростов н/Д, 2001.-С. 127.

54. Назаров A.A., Уразбаева СУ. Исследование СМО в дискретном времени и их применение к анализу оптоволоконных сетей связи. Автоматика и телемеханика. -№ 12. 2002. - С. 59-70.

55. Петер Л. Рекурсивные функции. М.: 1954, 264 с.

56. Пратт Т., Зелковиц М. Языки программирования: реализация и разработка. — СПб.: Питер, 2001. -686с.

57. Ю.Саати Т.П. Элементы теории массового обслуживания и ее приложения.- М.: Советское радио, 1971.-520 с.

58. Савенков Т.Ю. Предельные теоремы для характеристик СМО с пакетной обработкой требований / Московский университет // Вестник. Сер. 15. Вычислительная математика и кибернетика. № 3. - 2003. - С. 15-22.

59. Семенюта А.Н. Планирование развития первичных сетей связи на основе генетических алгоритмов // Автоматика и телемеханика. № I. -2002.-С. 67-75.

60. Таташев А.Г. Системы обслуживания МАР/Оп/1/1 с двумя специальными дисциплинами // Автоматика и телемеханика. №12. - 2001. - С. 33-39;1 ^.Тихонов А.Н., Арсенин В.Н. Методы решения некорректных задач. М.:

61. Наука, 1979.-286 с. 15.Труб И.И. Об оптимальной стратегии генерирования результатов запросов к ¡гиегпе^серверу баз данных // Автоматика и телемеханика. № 6. -2003. С. 95-102.

62. Чернов В.П., Ивановский В.Б. Теория массового обслуживания. -М.: ИНФРА-М, 2000. 158 с.

63. Эббинхаус Г.Д., Якобе К., Ман Ф.К. , Хермес Г. Машины Тьюринга и рекурсивные функции. М. 1972., 264 с.84.http://www.w3 .org/TR/1998/REC-xml-1998021085.http://lecture.narod:ru/TEMP/norenkov.html

64. Adiri L and B. Avi-Itzhak: A Time-Sharing Queue with a Finite Number of Customers, J. Assoc. Comput.Mach, 16: 315-323 (1969).

65. Ahrens, J.H., and U. Dieter. Computer Methods for Sampling from Gamma, Beta, Poisson, and Binomial Distributions, Computing, 12: 223-246 (1974).

66. Alexopoulos, C, and A.F. Seila: Output Data Analysis, in Handbook of Simulation, J.Banks, ed., John Wiley, New York (1998). p.120-128.

67. Alrefaei, M.H., and S. Andradottir: Discrete Stochastic Optimization via a Modification of the Stochastic Ruler Method, Proc. 1996 Winter Simulation Conference, San Diego, p. 406-411 (1996).

68. Alrefaei, M.H., and S. Andradottir, A Simulated Annealing Algorithm with Constant Temperature lot Discrete Stochastic Optimization, Management Set., 45:748-764(1999).

69. Anderson, T.W.: The Statistical Analysis of Time Series, John Wiley, New York (1994).

70. Andreasson, I J.; Antithetic Methods in queueing Simulations, Technical Report NA 72.58, Department of Computer Science, Royal Institute of Technology, Stockholm (1972).

71. Atkinson, A.C.: Tests of Pseudo-random Numbers, Appl. Statist, 29:164-171 (1980).

72. Avramidis, A.N., and J.R. Wilson: A Splitting Scheme for Control- Variates, Operations Res. Letters, 14:187-198 (1993).

73. Avramidis, A.N., and J.R. Wilson: Integrated Variance Reduction Strategies for Simulation, Operations Res., 44:327-346 (1996).

74. Back, T.: Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, and Genetic Algorithms, Oxford University Press, New York (1996).

75. Bagrodia, R.L.: Perils and Pitfalls of Parallel Discrete-Event Simulation, Proc. 1996 Winter Simulation Conference, San Diego, p. 136-143 (1996).

76. Balci, O., and R.G. Sargent: A Methodology for Cost-Risk Analysis in the Statistical Validation of Simulation Models, Commun. Assoc. Comput. Mack., 24:190-197 (1981).

77. Balci, O.: Verification, Validation and Testing, in Handbook of Simulation, J. Banks, ed., John Wiley, New York (1998).

78. Baskett F., Chandy K.M., Muntz R.R., Palacios F. Open, closed and mixed networks of queues with different classes of customers // J. ACM, 1975, № 22. P. 248 260.

79. Barton, R.R.: Design of Experiments for Pitting Subsystem Metamodels, Proc. 1997 Winter Simulation Conference, Atlanta, p. 303-310 (1997).

80. Barton, R.R.: Metamodels for Simulation Input-Output Relations, Proc. 1992 Winter Simulation Conference, Washington, D.C., p. 289-299 (1992).

81. Bays, C, and S.D. Durham: Improving a Poor Random Number Generator, Assoc. Comput. Mach. frans. Math. Software., 2:59-64 (1976).

82. Bechhofer, R.E., T.J. Santner, and D. Goldsman: Design and Analysis for Statistical Selection, Screening and Multiple Comparisons, John Wiley, New York (1995).

83. Bertsekas, D.P., and R. Gallager: Data Networks, 2d ed., Prentice-Hall, Englewood Cliffs, New Jersey (1992).

84. Bettonvil, В., and J.P.C. Kleijnen: Searching for Important Factors in Simulation Models with Many Factors: Sequential Bifurcation, Eur. J. Operational Res., 96:180-194 (1997).

85. Bichel, P. J., and K.A. Doksum: Mathematical Statistics: Basic Ideas and Selected Topics, Prentice-Hall, Upper Saddle River, New Jersey (1977).

86. Biles, W.E., and J J. Swain: Mathematical Programming and the Optimization of Computer Simulations, Math. Program. Studies, 11:189-207 (1979).

87. Biles, W.E., and J.J. Swain: Optimization and Industrial Experimentation, John Wiley, New York (1980).

88. Biles, W.E.: Experimental Design in Computer Simulation, Proc. 1979 Winter Simulation Conference, San Diego, p. 3-9 (1979).

89. Billingsley, P., D.J. Croft, D. V. Huntsberger, and C.J. Watson: Statistical Inference for Management and Economics, 3d ed., Allyn & Bacon, Boston (1986).

90. Bowden, R.O., and J.D. Hall: Simulation Optimization Research and Development, Proc. 1998 Winter Simulation Conference, Washington; D.C., p. 1693-1698 (1998).

91. Bowden, R.O.: The Spectrum of Simulation Software, HE Solutions, 30:44-46 (May 1998).

92. Box, G.E.P., and M.E. Mullen A Note on the Generation of Random Normal Deviates, Ann. Math. Statist, 29:610-611 (1958).

93. Box, G.E.P., гпб. N.R. Draper: Empirical Model-Building and Response Surfaces, John Wiley, New York (1987).

94. Bratley, P., B.L. Fox, and L.E. Schräge: A Guide to Simulation, 2d ed., Springer-Verlag, New York (1987).

95. Bright, H.S., and R.L. Enison: Quasi-random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography, Сотр. Surveys, 11:357-370 (1979).

96. Brown, M., and H. Solomon: On Combining Pseudorandom Number Generators, Ann. Statist., 7: 691-695 (1979).

97. Brown, R.: Calendar Queues: A Fast 0(1) Priority Queue Implementation for the Simulation Event Set Problem, Commun. Assoc. Comput. Mack, 31:1220-1227(1988).

98. Buss, A.H.: Modeling with Event Graphs, Proc. 1996 Winter Simulation Conference, San Diego, p. 153-160 (1996).

99. Carothers, CD., B. Topol, R.M. Fujimoto, and V. Sunder am\ Visualizing Parallel Simulations in Network Computing Environments: A Case Study, Proc. 1997 Winter Simulation Conference, Atlanta, p. 110-117 (1997).

100. Carson, J.S.: Variance Reduction Techniques for Simulated Queueing Processes, Technical Report 78-8, Department of Industrial Engineering, University of Wisconsin, Madison (1978).

101. Carson, Y., and A. Maria: Simulation Optimization: Methods and Applications, Proc. 1997 Winter Simulation Conference, Atlanta, p. 118-126 (1997).

102. Carter, G., and EJ. Ignall: Virtual Measures: A Variance Reduction Technique for Simulation, Management Sci., 21: 607-616 (1975).

103. Cheng, R.C.H., and J.D. Lamb: Interactive Implementation of Optimal Simulation Experiment Designs, Proc. 1998 Winter Simulation Conference, Washington, D.C., p. 707-712 (1998).

104. Cheng, R.C.H., and J.P.C. Kleijnen: Improved Design of Queueing Simulation Experiments with Highly Heteroscedastic Responses, Operations Res., 47 (1999).

105. Cizek P., Hardle W., Weron R. Statistical Tools in Finance and Insurance. Springer Verlag, Heidelberg, 2005.

106. Debicki K., Mandjes M. Traffic with an fBm Limit: Convergence of the Stationary Workload Process // Queueing Systems, 2004, v. 46, № 1 2. P. 113-127.

107. Evans, G.W., B. Stockman, and M. Mollaghasemi: Multicriteria Optimization of Simulation Models, Proc. 1991 Winter Simulation Conference, Phoenix, p. 894-900(1991).

108. Evans, M., N.AJ. Hastings, and J.B. Peacock: Statistical Distributions, 2d ed., John Wiley, New York (1993).

109. Farrington, P.A. and J.J. Swain: Design of Simulation Experiments with Manufacturing Applications, Proc. 1993 Winter Simulation Conference, Los Angeles, p. 69-75 (1993).

110. Fishman G. S.\ Statistical Analysis for Queueing Simulations, Management Sei., 20:363-369 (1973).

111. Fishman, G.S.: Estimating Sample Size in Computer Simulation Experiments, Management Sei., 18: 21-38 (1971).

112. Fishman, G.S.: Monte Carlo: Concepts, Algorithms, and Applications, Springer-Verlag, New York (1996), 168.

113. Fishman, G.S.: Principles of Discrete Event Simulation, John Wiley, New York (1978), 231.

114. Foss S., Korshunov D. Heavy Tails in Multi-Server Queue // Queueing Systems, 2006, v. 52, № 1. P. 31 48.

115. Fu, M.C.: Optimization via Simulation: A Review, Ann. of Operations Res, 55:199-247(1994).

116. Futamura.Y. Partial evaluation of computation process an approach to a compilercompiler / Systems, Computers, Controls, 2(5): 45 - 50, 1971.

117. Fujimoto, R.M.: Parallel and Distributed Simulation, in Handbook of Simulation, J. Banks, ed., John Wiley, New York (1998), 218.

118. Gal, S„ R.Y. Rubinstein, and A. Ziv: On the Optimality and Efficiency of Common Random Numbers, Math. Comput. Simul, 26:502-512 (1984).

119. Gross, Di, and.CM. Harris: Fundamentals of Queueing Theory, 3d ed., John Wiley, New York (1998), 324.

120. Gupta, S.S., and J.C. Hsu: A Computer Package for Ranking; Selection; and Multiple Comparisons with the Best, Proc. 1984 Winter Simulation Conference, Dallas, p. 251^257(1984).

121. Healy, K.J., and L. W. Schruben: Retrospective Simulation Response Optimization, Proc. 1991 Simulation Conference, Phoenix, p. 901-906 (1991).

122. Heidelberger, P.: Fast Simulation of Rare Events in Queueing and Reliability Models, Assoc. Comput. Mach. Trans. Modeling and Comput. Simul., j • •5:43-85 (1995).

123. Heikes, R.G., D.C. Montgomery, and R.L. Rardin: Using Common Random Numbers in Simulation Experiments—An Approach to Statistical Analysis, Simulation, 25:81-85 (1976).

124. Hogg, R. V. and A.F. Craig: Introduction to Mathematical Statistics^ 5th ed., Prentice-Hall,,Upper Saddle River, New Jersey (1995), 328,

125. Hunter, J:S:, and T.H. Nay lor. Experimental Designs for Computer S i-mulation Experiments, Management'Sei!, 16:422-434 (1970).

126. Joines, J:A., and S.D.-Roberts: Object-Oriented Simulation; in Handbook of Simulation, J. Banks, ed., John Wiley, New York (1998), 345.

127. Jones, D.W.: An Empirical Comparison of Priority-Queue and Event-Set Implementations, Commun. Assoc. Comput. Mach., 29: 300-311 (1986):

128. Kelton, W.D., and A.M. Law: A New Approach for Dealing with the Startup Problem in Discrete Event Simulation, Naval Res. Legist. Quart., 30:641-658 (1983).

129. Kelton, W.D.: Designing Simulation Experiments, Proc. 1999 Winter Simulation Conference, Phoenix ,16-22,(1999).

130. Kelton, W.D.\ Random Initialization Methods in Simulation, IIE Trans., 21:355-367(1989).

131. Levasseur, J.A.: The Case for Object-Oriented Simulation, OR/MS Today, 23:65-67 (August 1996).

132. Little J. A proof for the Queueing Formula L XW II Operation Research, 9, 1961.

133. Marse, K., and S.D. Roberts: Implementing a Portable FORTRAN Uniform (0,1) Generator, Simulation, 41:135-139 (1983).

134. Naylor, Т.Н., and J.M. Finger: Verification of Computer Simulation Models, Management Sci., 14: 92-101 (1967).

135. Odifreddi P. Classical recursion theory. Studies in logic and Foundation mathematics. Elsevier Science B.V. 1999. -V. 125. 465 p.

136. Pugh, W.\ Skip Lists: A Probabilistic Alternative to Balanced Trees, Commun. Assoc. Comput. Mack, 33: 668-676 (1990).

137. Raatikainen, K.E.E.: Sequential Procedure for Simultaneous Estimation of Several Percentiles, Trans., of the Society for Сотр. Simulation, 7:21-24 (1990).

138. Rubinstein, R.Y.: Monte Carlo, Optimization, Simulation and Sensitivity of Queuing Networks, Krieger Publishing Co., Malabar, Florida (1992), 324.

139. Rubinstein, R.Y.: Simulation and the Monte Carlo Method, John Wiley, New York (1981), 284.

140. Tukey, J.W.: Exploratory Data Analysis, Addison-Wesley, Reading, Massachusetts (1970), 269.

141. Wilson, J.R., A.AB. Pritsken Experimental Evaluation of Variance Reduction Techniques for Queueing Simulation Using Generalized Concomitant Variables, Management ScL, 30:1459-1472 (1984b).