Введение к работе
Актуальность работы
Существует особая трактовка понятия «эффективность вычислений», смысл которой был заложен в работах Тьюринга, Поста, Черча, Клини, Гёделя, которые не могли предвидеть нынешнего прогресса в области компьютерных систем и сетей. Тем не менее, модели вычислений, заложенные в их работах, могут являться математическим фундаментом для построения эффективных программных комплексов с применением современных вычислительных систем и аппарата математического моделирования.
При решении многих практических задач выясняется, что реальные системы чрезвычайно сложны, и зачастую практически невозможно определить ряд их параметров, что исключает возможность аналитического решения. В этом случае применяется методика исследования системы с помощью имитационного моделирования (ИМ), поэтому в число этапов ИМ входят вычислительные процедуры (эксперименты), требующие больших объемов вычислений.
Анализ существующих специализированных языков описания сложных систем и программных средств, построенных на их основе, показывает, что далеко не всегда в них используются эффективные численные методы и алгоритмы. С ростом вычислительных ресурсов компьютерных систем вопросы эффективных вычислений практически перестали рассматриваться специалистами в данной области, тем не менее, покажем, что проблемы эффективно вычислимых функций (алгоритмов) по-прежнему актуальны.
Стремительное развитие вычислительной техники привело к тому, что практически во всех отраслях народного хозяйства были внедрены и продолжают развиваться и модернизироваться крупные корпоративные информационные системы, функционирующие на базе распределенных компьютерных сетей, обрабатывающие огромное количество разнородной информации, исходящей от множества различных источников. В связи с постоянно увеличивающимися возможностями вычислительной техники и ужесточением требований к точности математических моделей появляется необходимость учитывать всё большее число факторов, характерных для реальных систем, увеличивается и сложность используемых моделей, необходимых при изучении данных систем. Кроме того, в функции многих таких систем встроены подсистемы поддержки принятия решений, которые в режиме реального времени должны оперативно осуществлять анализ, обработку, передачу информации и формирование управляющих и/или советующих решений. Указанные факторы – увеличения объема вычислительных задач и выполнения их за приемлемое для системы время – свидетельствуют о необходимости дальнейшего развития методов эффективных вычислений и их внедрения в системы обработки информации.
В работах Э. Поста, а затем Х. Роджерса делается предположение и дается его обоснование о том, что «понятие общерекурсивной функции действительно является формальным эквивалентом эффективной вычислимости…». Таким образом, если алгоритмы в системе ИМ построены на базе некоторых классов рекурсивных функций, то это будет означать, что они являются эффективно вычислимыми, то есть реализованными наилучшим способом из всех возможных.
Разработанные автором метаязык описания и структуризации данных и построенные на его базе комплексы программ, реализующие алгоритмы, оптимизированные по критерию вычислительной эффективности, использующие аппарат рекурсивных функций и частичных вычислений, предназначены для исследования и использования в системах реального времени, в которых проблема скорости вычислений очевидна.
Теория алгоритмов сформировалась в 20 веке и впервые появилась в трудах Э. Бореля (1912) и Г. Вейля (1921). Началом систематической разработки теории алгоритмов можно считать 1936 год, когда А.Черч опубликовал первое понятие вычислимой функции и привел первый пример функции, не являющейся вычислимой, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, машин Тьюринга). В дальнейшем теория алгоритмов получила развитие в трудах С. Клини, Э. Поста, А.А. Маркова, А.Н. Колмогорова и других. Оптимизации алгоритмов посвящена теория частичных вычислений, разработанная Й. Футамурой,
В.Ф. Турчиным, А.П. Ершовым.
Теории формальных грамматик и грамматическому разбору выражений посвящены труды таких ученых как Н. Хомский, А. Ахо, Д. Ульман, Д. Грис, Д. Кнут.
Теории и языкам ИМ посвящены работы Дж. Гордона, Е. Сейджвика, А. Лоу, В. Кельтона, В.В. Емельянова. Работы Г. Буча, П. Коуда, позволили создавать системы моделирования и программирования с использованием объектно-ориентированных принципов. Отметим книги Л. Клейнрока, Г.Т. Артамонова и О.М. Брехова по моделям функционирования ЭВМ.
Современное состояние теории массового обслуживания обеспечили работы А.К. Эрланга и А.А. Маркова, А.Я. Хинчина, А.А. Боровкова, Б.В. Гнеденко, В.А. Каштанова, И.Н. Коваленко, Т.Л. Саати, Д.Г. Кендалла, Дж. Литтла. Из современных работ по СеМО следует выделить многочисленные труды В.М. Вишневского, В.А. Ивницкого.
Цели и задачи исследования. Основной целью исследования является разработка методов преобразования вычислительных процессов к оптимизированным рекурсивным видам эффективно вычислимых алгоритмов на основе математического аппарата теории программирования, теории рекурсивных функций и методов частичных вычислений.
Для достижения поставленной цели необходимо решение следующих задач.
-
Выделение класса систем, обладающих высокой степенью распределенности и значительным числом разнородных объектов обслуживания и требующих значительных объемов вычислений, возникающих в связи с внедрением новых принципов передачи и обработки информации, а также требованием оперативной поддержки принятия решений за ограниченное время.
-
Разработка методов оптимизации процессов программных вычислений и способов преобразования алгоритмов к эффективному, теоретически обоснованному базису.
-
Разработка рекурсивных форм эффективно вычислимых алгоритмов описания и моделирования систем.
-
Построение метаязыка описания и структурирования данных для
СеМО с применением предложенной технологии оптимизации. -
Разработка методики представления и моделирования СеМО, описывающей реальные информационные системы с помощью разработанного метаязыка.
-
Исследование информационных систем с использованием разработанной среды ИМ.
Теоретико-методологическая основа исследования. В работе используются теоретические и практические разработки, связанные с построением и анализом формальных грамматик. В качестве теоретической базы при построении наиболее эффективных алгоритмов применяется математический аппарат теории рекурсивных функций. Для оптимизации программ использовался аппарат частичных вычислений. При разработке методик анализа и преобразования данных использовались современные методы и средства представления информации. Основой прикладных аспектов теоретических исследований явились труды отечественных и зарубежных авторов, посвященные проблемам, связанным с теорией массового обслуживания.
В диссертационном исследовании используются принципы системного, структурно-функционального и сравнительного анализа.
Информационно-эмпирической базой исследования послужили экспериментально-статистические и экспертные данные о конфигурации и функционировании сложных систем массового обслуживания, являющихся предметом исследования.
Научная новизна работы заключается в разработке методов реструктуризации и оптимизации вычислений в ИМ на основе эффективных алгоритмов. К наиболее существенным научным результатам работы относятся следующие.
-
Исследована теоретическая база представления алгоритмов распознавания языков представления СеМО и предложены методы реализации программных процедур эффективными способами.
-
Разработана технология оптимизации вычислений в программных модулях с использованием методов частичных вычислений и алгоритмов рекурсивных преобразований.
-
Предложен метаязык структурированного описания СеМО XML-QS с эффективными методами вычислений, в том числе:
-
для существующих языковых описаний СеМО разработаны алгоритмы их преобразования к языку XML-QS;
-
разработан вычислительно-эффективный алгоритм распознавания входного языка;
-
показан класс СеМО, для описания которых применим данный язык.
Разработана методика представления информационных систем на метаязыке XML-QS и алгоритмы ее применения.
Разработаны алгоритмы линейной и полиномиальной сложности, на основе которых создано программное обеспечение для имитации СеМО.
Практическая ценность. Предложенные теоретические подходы к представлению СеМО и их формальному описанию используются в интегрированных информационно-управляющих системах в подсистемах поддержки принятия решений.
Практическую ценность представляют следующие результаты.
1. Разработан, внедрен и адаптирован комплекс программ для имитационного моделирования работы автоматизированных систем управления, описываемых в виде СеМО. Внедрение этого комплекса позволило определить «узкие места» в системах управления и предложить обоснованные рекомендации по их устранению.
2. Разработан и внедрен программный комплекс управления процессом работы станции скорой медицинской помощи (СМП) г. Таганрога, в котором практически реализованы методы эффективных вычислений, предложенные в диссертации, позволяющие оптимизировать работу станции СМП, и, как следствие, повысить эффективность и устойчивость функционирования этой системы.
3. На основе статистического анализа потоков данных в исследуемых СеМО выявлено наличие пиковых режимов работы, как случайных, возникающих в случае нештатных ситуаций, так и циклических, связанных с особенностями технологического процесса, приводящих к сбоям в работе систем, неудовлетворительному качеству обслуживания клиентов, несвоевременности предоставления информации, а также предложены методы по устранению этих недостатков. В соответствии с выявленными особенностями потоков данных разработана методика анализа и контроля использования системы обслуживания СМП и комплексной системы автоматизированного управления сортировочным процессом (КСАУ СП).
Достоверность научных и практических результатов работы подтверждается проведенными вычислительными экспериментами на практических задачах, а также публикациями и актами о внедрении.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийском симпозиуме по прикладной и промышленной математике (2007 г. Сочи), на Международной конференции «Математика. Экономика. Образование» (2006 г., Новороссийск); на Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (2006 г., Новочеркасск); Международной научно-практической конференции «Экономико-организационные проблемы проектирования и применения информационных систем» (2006 г., Кисловодск), на научно-теоретических и научно-практических конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (2003 – 2007 гг.).
Основные положения и результаты, выносимые на защиту:
– эффективно вычислимые алгоритмы на основе рекурсивных функций;
– процедура оптимизации программных модулей на базе частичных вычислений;
– метаязык описания систем и сетей массового обслуживания XML-QS;
– принципы и методы представления СеМО;
– метод преобразования формальных описаний СеМО к языку XML-QS;
– алгоритм распознавания разработанного метаязыка.
Публикации
По результатам проведенных теоретических и экспериментальных исследований опубликовано 16 печатных работ, из них 3 – в журналах, включенных в список рекомендованных ВАК.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы и приложений. Объем диссертационной работы – 162 страницы, из них основного текста 135 с.
Похожие диссертации на Методы оптимизации процессов программных вычислений и эффективно вычислимые алгоритмы для метаязыка описания сетей массового обслуживания
-
