авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

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

Pages:   || 2 | 3 |

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

-- [ Страница 1 ] --

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

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

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

Специальность 05.13.17 – Теоретические основы информатики

Автореферат

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

кандидата технических наук

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

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

Научный руководитель – доктор технических наук, доцент Бутакова Мария Александровна
Официальные оппоненты – доктор технических наук, профессор Ковалев Сергей Михайлович
– кандидат технических наук, доцент Мартемьянов Сергей Васильевич
Ведущая организация Донской государственный технический университет

Защита состоится _19 июня 2008 г. в 14 часов 20 мин. на заседании диссертационного совета Д 212.208.21 в Таганрогском технологическом институте Южного федерального университета по адресу: 347928, г. Таганрог, ГСП-17А, пер. Некрасовский, 44, ауд. Д-406.

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

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

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

диссертационного совета Д 212.208.21

доктор технических наук, профессор Чернов Н.И.

Общая характеристика работы

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

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

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

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





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

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

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

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

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

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

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

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

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

  1. Выделение класса систем, обладающих высокой степенью распределенности и значительным числом разнородных объектов обслуживания и требующих значительных объемов вычислений, возникающих в связи с внедрением новых принципов передачи и обработки информации, а также требованием оперативной поддержки принятия решений за ограниченное время.
  2. Разработка методов оптимизации процессов программных вычислений и способов преобразования алгоритмов к эффективному, теоретически обоснованному базису.
  3. Разработка рекурсивных форм эффективно вычислимых алгоритмов описания и моделирования систем.
  4. Построение метаязыка описания и структурирования данных для
    СеМО с применением предложенной технологии оптимизации.
  5. Разработка методики представления и моделирования СеМО, описывающей реальные информационные системы с помощью разработанного метаязыка.
  6. Исследование информационных систем с использованием разработанной среды ИМ.

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

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

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

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

  1. Исследована теоретическая база представления алгоритмов распознавания языков представления СеМО и предложены методы реализации программных процедур эффективными способами.
  2. Разработана технология оптимизации вычислений в программных модулях с использованием методов частичных вычислений и алгоритмов рекурсивных преобразований.
  3. Предложен метаязык структурированного описания СеМО XML-QS с эффективными методами вычислений, в том числе:
    1. для существующих языковых описаний СеМО разработаны алгоритмы их преобразования к языку XML-QS;
    2. разработан вычислительно-эффективный алгоритм распознавания входного языка;
    3. показан класс СеМО, для описания которых применим данный язык.
  4. Разработана методика представления информационных систем на метаязыке XML-QS и алгоритмы ее применения.
  5. Разработаны алгоритмы линейной и полиномиальной сложности, на основе которых создано программное обеспечение для имитации СеМО.

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

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

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

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

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

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

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

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

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

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

– метаязык описания систем и сетей массового обслуживания XML-QS;

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

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

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

Публикации

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

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

Основное содержание работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть также определена функция:

где – индикатор сравнения.

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

 Для случая, приведенного на рис. 2, введем-8

Для случая, приведенного на рис. 2, введем дополнительный узел n (узел 6). При этом следует отметить, что .

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

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

. Пример преобразования СеМО для-11.

 Пример преобразования СеМО для-12

Рис. 2. Пример преобразования СеМО для рекурсивного описания

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

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

  1. для ;
  2. , где - наименьшее y, для которого выполняется отношение .

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

1. ;

2. .



Pages:   || 2 | 3 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.