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

РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт проблем управления им. В.А. Трапезникова

На правах рукописи УДК 658.512.011.56:004.42

СМИРНОВ СЕРГЕЙ ВЛАДИМИРОВИЧ

МОДЕЛИ И МЕТОДЫ АВТОМАТИЗИРОВАННОГО

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

Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Москва 2005

Работа выполнена в Институте проблем управления им. В.А. Трапезникова РАН

Научный руководитель: доктор технических наук, профессор

Артамонов Евгений Иванович

Официальные оппоненты: доктор технических наук, профессор

Хачумов Вячеслав Михайлович

доктор физико-математических наук, профессор Смолянинов Владимир Владимирович

Ведущее предприятие: Институт системного анализа РАН.

Защита состоится ¿о 2005 г. вд^час. ¿%?мин.

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

Института проблем управления им. академика В.А.Трапезникова РАН

по адресу: 117806, г. Москва, ул. Профсоюзная, 65.

Телефон совета: 334-93-29

С диссертацией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разослан 2005 г.

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

Большой вклад по разработке методов синтеза структур данных внесли работы Е.И. Артамонова, В.Ш. Рубашкина, О.П. Кузнецова и др. По проектированию специализированных информационных систем использующих сложно структурированные графические данные И.А Башмакова, Л.Ф. Ноженковой, МЛ. Сидоренко, B.C. Тикунова, А.И. Мартыненко, Д.В. Тюкавкина и др., в органах управления государственной власти В.Я. Цветкова, С.В. Шайтуры, Е.Г. Капралова, Н.В. Коноваловой. По проектированию информационных систем, использующих методы картографического исследования Л.М. Бугаевского, О.Ю. Жуковой, Н.И. Мельниченко, Т.П. Нырцовой, и др..

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

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

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

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

1. Определить возможности построения СИС, алгоритмы функционирования, структуру алгоритмов, используемые структуры данных.

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

3. Разработать математические модели информационного обеспечения СИС.

4. Разработать языковые и интерактивные средства взаимодействия пользователей с СИС. Определить их эргономические и психофизиологические характеристики.

5. Создать программное обеспечение подсистем СИС.

6. Исследовать эффективность внедрения разработанных

систем.

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

Научная новизна работы заключается в следующем:

- разработке алгоритмов функционирования и архитектуры СИС для управления социально-образовательной сферой;

- разработке структуры информационно-аналитической модели СИС для управления социально-образовательной сферой;

- разработке структуры и состава баз данных СИС для управления социально-образовательной сферой;

- разработке метода синтеза архитектуры подсистемы определения кратчайшего пути на модели графического слоя СИС;

- разработке универсального алгоритма определения кратчайшего пути на моделях графического слоя СИС с использованием многокритериальных оценок;

- предложены аналитические оценки сложности автоматизированного извлечения информации в СИС при решении задач в социально-образовательной сфере;

- предложен способ тестирования цветового зрения пользователя СИС для управления социально-образовательной сферой и

настройки пользовательского интерфейса по результатам тестирования.

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

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

Реализация результатов работы. Полученные в диссертации результаты и программное обеспечение внедрены в Юго-Западном и Северном окружных управлениях образованием г. Москвы. Акты внедрения и использования научных результатов приведены в приложении диссертационной работы.

Апробация работы. Материалы диссертационной работы докладывались на Ш-й и ГУ-й международных конференциях «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта. САБ/САМ/РБМ» (Москва: ИЛУ РАН, 2003, 2004), У-й молодёжной научно-технической конференции «Наукоёмкие технологии и интеллектуальные системы» (Москва: МГТУ, 2003), Ш-й международной научно-практической конференции «Математическое моделирование в образовании, науке и производстве» (Приднестровье, Тирасполь: ПГУ, 2003), международной конференции «Информацион-

ные средства и технологии» (Москва: МЭИ (ТУ), 2003), региональной дистанционной научно-практической конференции «Методы и устройства психофизиологических исследований человека» (Йошкар-Ола: МарГТУ,2003).

Публикации. По материалам диссертации опубликовано 12 печатных работ.

Структура и объём работы. Диссертационная работа состоит из введения, 4-х глав, заключения, списка литературы и приложений. Общий объём основного текста диссертации - 130 стр., включая 28 рис., 6 таб., списка литературы из 120 наименований, 9-и приложений.

Содержание диссертации

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

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

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

ф - множество форм внешнего представления объектов информации;

Д - множество точностей представления объектов информации.

Основными отличиями разработанного метода от известных являются:

1. Данные в СИС и их структура определяются способами кодирования, передачи и точностью представления.

2. Введено понятие «локальный алгоритм» (ЛА), которое более точно определяет минимальную единицу программного обеспечения, аналогичную понятиям «модуль» или «черный ящик» в известных методах. Под локальным алгоритмом понимается сильно связанная часть общего алгоритма функционирования СИС с последовательным выполнением операций над данными, представленными с одинаковой точностью и одним способом кодирования.

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

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

Практически, на текущий момент времени не каждой дуге можно найти соответствующую реализацию.

5. В заключительной стадии проектирования для всех наборов вариантов структуры строятся их обобщенные модели структур в виде набора взаимосвязанных моделей ЛС, реализующих общий алгоритм функционирования системы. На обобщённых моделях каждой дуге присваивается вес, соответствующий показателю качества реализации. Задача выбора лучшей системы для одного варианта структуры сводится к определению кратчайшего пути на графе обобщённой модели. Лучшая структурная организация системы выбирается по значениям показателей качества для всех вариантов структур.

Разработанный метод синтеза структур использовался при проектировании подсистем обработки сложно структурированной графической информации (ПОГИ) и решении оптимизационных задач (ПРОЗ) в СИС.

Исследован алгоритм функционирования подсистемы обработки графической информации (ПОГИ), проведены операции с алгоритмом, определены возможные варианты построения структур подсистемы.

Способы представления ({5,ТЬ}), кодирования (а) и точность представления (5) информации на входах и выходах системы определяются внешними устройствами или системами. Представление, кодирование и точность промежуточной информации задается разработчиком и в последующем уточняются на последней стадии синтеза структуры системы.

Генерация первого набора вариантов построения подсистемы заключается в следующем. Алгоритм функционирования ПОГИ включает (см. рис. 1.2) интерпретацию входного графического языка (ИВЯ), интерактивных действий пользователя (ИИД); процессорные операции с графической информацией (ГП) такие, как геометрические построения, преобразования, создания 2D и 3D-моделей, операции с растровыми данными; постпроцессорные (ПП) операции по выводу информации на внешние устройства. Первоначально алгоритм функционирования может быть разделен на три основные части (ЛА), различающиеся точностью представления информации.

Первая часть, включающая ИВЯ и ИИД, обрабатывает символьную информацию, на выходе формируется символьная

12

таблица входных описаний (ТО). Характеристики структуры данных ТО представлены следующим образом:

где Ор1 - 5 - оператор в таблице описаний из общего числа п операторов, М1 - идентификатор i - го оператора,

Вторая (ГП) - на входе информация (таблица входных описаний -ТВО) кодируется аналогично ТО, а геометрические характеристики объектов представляются с большей точностью в виде действительных чисел: ^ ^

на выходе ГП формируется предтерминальный файл (ПТФ) с результатами геометрических построений в виде действительных чисел:

где х; ,у\ - координаты г -ой точки ломаной линии, порождённой ) -

ым оператором, - служебная информация

Третья (ПП) - преобразует ПТФ в терминальный файл (ТФ), в котором информация представляется в виде, понятном конкретному внешнему устройству:

М",Ра:,Ра"2...Рапт-

Естественно, что для последовательной передачи информации от входа к выходу ПОГИ необходим преобразователь (П1) ТО в ТВО.

Рис.1.2

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

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

Проведён анализ алгоритмов решения оптимизационных задач в СИС таких, как автоматизированное размещение объектов социально-образовательной сферы и определение оптимальных путей их обслуживания. Последняя задача сводится к автоматической трассировке соединений между объектами с использованием алгоритма определения кратчайшего пути. Такие алгоритмы находят широкое применение при прокладывании трасс шоссейных дорог, трасс трубопроводов, при разработке принципиальных схем, и т.п. Разработан универсальный алгоритм и программное обеспечение ПРОЗ многокритериального определения кратчайшего пути на растровой модели, определены возможные варианты построения совмещенных структур подсистем обработки графической информации (ПОГИ) и решения оптимизационных задач (ПРОЗ) в СИС.

Алгоритм функционирования ПРОЗ включает операции по подготовке исходных данных, размещению типовых графических обозначений объектов, прокладыванию трасс между объектами, визуализации и выпуску чертежной документации в электронном виде или на твёрдых носителях. После каждой из этих операций допускается возможность редактирования полученных результатов. Подготовка исходных данных включает описание типовых графических изображений объектов, их характеристик и создание библиотек типовых объектов. Показано, что за счёт совмещения алгоритмов ПОГИ и ПРОЗ, выполнения операций с алгоритмами, систематизации реализаций по структурам данных и их взаимным преобразованиям появляются принципиально новые решения по структурной организации ПРОЗ.

В четвёртой главе представлена общая структура разработанного программного обеспечения СИС для решения задач в социально-образовательной сфере. Структура системы выбрана на основе созданного метода синтеза. Система содержит (см.рис.1.3) подсистему обработки графической информации (ПОГИ), подсистему решения оптимизационных задач (ПРОЗ), набор прикладных подсистем, использующих графическую информацию (геометрические модели, карты, базы данных объектов и т.п). Все подсистемы взаимодействуют через информационную подсистему по обмену геометрическими моделями и базами данных._

Рис.1.3. 15

Заштрихованные блоки на рис. 1.3 являются авторской разработкой. В СИС предусмотрена связь с внешними инструментальными системами через стандартные графические структуры данных.

Приведены примеры создания типовых графических объектов и геометрических моделей электронных карт на их основе. Показана возможность решения оптимизационных задач в социально-образовательной сфере с использованием геометрических моделей.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

5. Созданы языковые и интерактивные средства взаимодействия пользователя с СИС. Языковые средства взаимодействия содержат пять классов операторов: задания единиц измерения и масштабирования; формирования геометрических моделей; задания типов объектов и их настройки на цветовое восприятие пользователя; описания сопутствующих вычислений, геометрических построений и преобразований; описания растровых структур.

6. Проведён анализ методов синтеза структур систем. Для автоматизации процесса проектирования структур СИС со сложно структурированными графическими данными вводятся элементы формализации, основанные на использовании типовых структур данных внешних устройств и геометрических процессоров,

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

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

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

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

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

11. Разработанные в диссертационной работе модели, методы, алгоритмы, программное и информационное обеспечения СИС для

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

Основные публикации по теме диссертации

1. Смирнов С.В., Тюкавкин Д.В. Использование ГИС-проектов для средних школ //Автоматика и телемеханика. - М., 2002. - №4. - С. 179183.

2. Смирнов С.В., Тюкавкин Д.В. Разработка советующей географической информационной системы для целей управления социально-образовательной сферы региона // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта. CAD/CAM/PDM-2003: Тез. докл. III междунар. конф. и выст-ки. - Москва: ИПУ, 2003 г. - С 23-25.

3. Смирнов С.В., Тюкавкин Д.В. Разработка ГИС-продуктов для целей управления социально-образовательной сферой региона // Сб. науч. тр. V-й молодёж. науч.-техн. конф. «Наукоёмкие технологии и интеллектуальные системы 2003». В 2 частях. Часть 1. - Москва: МГТУ им. Н.Э.Баумана, 2003. - С. 164-166.

4. Смирнов С.В., Тюкавкин Д.В. Разработка тематического слоя геоинформационной системы при помощи графо-аналитической модели // Объединённый научный журнал. - М., 2003. - №22. - С. 7980.

5. Смирнов С.В. Моделирование специализированной справочной географической информационной системы (ССС) ГИС для обеспечения информацией по образованию округа // Математическое моделирование в образовании, науке и производстве: Материалы III междунар. науч.- практ. конф. Тирасполь: РИО ПГУ, 2003. - С. 66-67.

6. Смирнов С.В. Разработка (ССС) ГИС для целей компьютеризации процесса принятия решений // Междунар. форум информатизации-2002: Докл. междунар. конф. «Информационные средства и технологии». 14-16 октября 2003 г., в 3-х т.т. Т.1. - М.: Янус-К, 2003.-С. 194-197.

7. Смирнов СВ., Тюкавкин Д.В. Разработка специализирован-ной справочно-советующей системы // Приборы и системы. Управление, контроль, диагностика. - М., 2003. - №11. - С. 13-17.

8. Смирнов С.В., Тюкавкин Д.В. Геоинформационная система для поддержки принятия решений в органах управления социально-образовательной сферой // Проблемы управления. - М., 2003. - №3. -С. 54-60.

9. Смирнов С.В. Психофизиологическое исследование гигиены труда при выборе системы геоинформационных знаков // Сб. науч. ст. Всеросс. дистанц. науч. - практ. конф. «Методы и устройства в психофизиологических исследованиях человека». - Йошкар-Ола: МарГТУ,2003.-С.5-9.

10. Смирнов С.В., Тюкавкин Д.В. Процесс построения справочной геоинформационной системы для оказания помощи окружной администрации управления социально-образовательной сферой // Приборы и системы. Управление, контроль, диагностика. - М., 2004. -№2.-С. 4-10.

11. Артамонов Е.И., Смирнов С.В. Разработка программного обеспечения нахождения кратчайшего пути в задачах социально-образовательной сферы // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта. CAD/CAM/PDM-2004: Тез. докл. IV междунар. конф. и выст-ки. - Москва: ИПУ, 2004 г. - С. 27.

12. Артамонов Е.И., Смирнов С.В. Синтез структуры системы автоматической трассировки соединений между элементами на плоскости // Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта. CAD/CAM/PDM-2004: Тез. докл. IV междунар. конф. и выст-ки. - Москва: ИПУ, 2004 г. - С. 28.

Зак. 36. Тир. 100. ИПУ.

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

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

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

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

Геометрический процессор реализует алгоритмы геометрических построений, преобразования, создания 2D и 3D-моделей, алгоритмы штриховок и т.п.

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

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

Разработана структура информационно-аналитической модели СИС применительно к объектам социально-образовательной сферы территориально-административных округов г. Москвы. Модель

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

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

Разработана унифицированная структура данных графических слоев информационно-аналитической модели СИС. Одним из основных принципов построения структуры данных является использование для описания объектов не графических примитивов, а объектов, имеющих логический смысл. Все используемые в СИС объекты принадлежат к одному из трёх классов: трёхмерные геометрические объекты, к которым относятся линии, дуги, плоскости и т.д.; поясняющие объекты; структурные объекты, разделяющиеся на несколько подтипов; ассоциирующие объекты, позволяющие объединять в группы произвольное число объектов для последующей обработки; объекты, определяющие проекцию, позволяют определять условия проецирования объектов; объекты-фрагменты, с помощью которых можно определять часто используемые изображения.

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

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

где А - цветовое зрение изготовителя карты СИС;

X), У], - факторы цветового зрения изготовителя СИС;

В - цветовое зрение потребителя карты СИС;

Х^ Y2 Z2 - факторы цветового зрения; причём Хи Х2 - физический, Yt, Y2 - физиологический, Zi, Zi психологический факторы.

Для приближённо одинакового восприятия цвета изготовителем и потребителем карты необходимо перед цветовым наполнением СИС провести тестирование потребителя на восприятие цвета, чтобы узнать индивидуальные особенности его цветового зрения. Разработана методика предварительной настройки цвета и конструкций объектов под индивидуальные особенности конечных пользователей.

Созданы средства взаимодействия пользователя с СИС. Языковые средства взаимодействия содержат пять классов операторов.

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

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

В третьей главе проведён анализ методов структурной организации систем, разработан метод синтеза структур СИС, рассмотрены варианты построения подсистем обработки сложно структурированной графической информации (ПОГИ) и решения оптимизационных задач (ПРОЗ) в СИС.

К настоящему времени разработаны CASE (Computer-Aided Software/System Engineering) технологии, методология структурного анализа SADT (Structured Analysis and Design Technique) и ее подмножество IDEF0. Методы структурной организации существенным образом определяют эксплуатационные характеристики создаваемых систем такие, как быстродействие, объёмы занимаемой

памяти, сложность разработки и тестирования, надёжность. Большая часть известных методов позволяет дисциплинировать и документировать процесс описания алгоритмов функционирования, провести «визуальный» анализ алгоритмов и неформальный синтез структуры системы. Эти методы синтеза структурной организации преимущественно основаны на опыте и интуиции конкретных разработчиков.

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

Разработан метод синтеза структур СИС, в котором учитываются перечисленные факторы и особенности сложно структурированных графических данных. Основными исходными данными при проектировании структур являются алгоритм функционирования системы и его характеристики. Алгоритм функционирования СИС характеризуется следующей четвёркой параметров:

где Е - алгоритм функционирования системы;

Р - множество объектов информации (данных), поступающих в процессе функционирования систем по входам, выходам и связям между блоками;

О - множество операций над объектами информации; Г - множество связей между операциями; Т - времена выполнения операций.

Множество объектов информации в свою очередь характеризуется

где А - множество способов кодирования объектов информации;

Е = {Р,0,Г,т},

(1.2)

тройкой:

(1.3)

\ х-"-

V ¿SCCiíft«.*

' V

V « «и

39 ИЮН 2005

Введение.

Глава 1. Информационные системы в социально-образовательной сфере.

1.1. Анализ информационных систем в социально-образовательной сфере и инструментальных программных средств для их разработки.

1.2. Особенности задач предоставления услуг в социально-образовательной сфере.

1.3. Анализ информационных моделей при решении задач в социальнообразовательной сфере и требования к проектируемой СИС.

Выводы главы 1.

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

2.1. Структура информационно-аналитической модели СИС и разработка средств для её создания.

2.2. Разработка модели графического слоя СИС.'.

2.3. Графоаналитическая модель тематического слоя СИС.

2.4. Выводы главы 2.

Глава 3. Анализ и разработка алгоритмов решении в СИС оптимизационных задач социально-образовательной сферы.

3.1. Структурная организация специализированной информационной системы.

3.2. Синтез структур программного обеспечения и анализ сложности их построения для решения оптимизационных задач в СИС.

3.3. Анализ и исследование возможностей использования алгоритмов определения кратчайшего пути в СИС.

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

3.5. Выводы главы 3.

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

4.1. Архитектура СИС.

4.2. Программная реализация задачи поиска кратчайшего пути.

4.3. Оценка сложности автоматизации извлечения графической информации при решении задач в социально-образовательной сфере.

4.4. Структура данных и их преобразование.

4.5. Выводы главы 4.

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

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

К настоящему времени сложился класс программно реализованных систем, в которых за счёт развитых средств взаимодействия пользователей с системой, особенно графических, при постоянно увеличивающейся сложности решаемых задач общение пользователей с системой происходит в реальном масштабе времени. Примерами такого рода систем являются системы автоматизированного проектирования (САПР), информационно-аналитические системы, геоинформационные системы (ГИС) и т.п. Для устранения информационной недостаточности известно использование этих систем, но самые распространённые - ГИС используют ' ;■•>•. также сложно структурированную графическую информацию. Достоинствами таких систем являются: оптимальное управление географически привязанных объектов управления социально-образовательной сферы, анализ данных мониторинга для задач пространственного анализа статистических данных по показателям образовательной системы, планирование развития и административного управления образовательными учреждениями, возможность быстрого рассмотрения многих вариантов и выбора наиболее приемлемого решения [6-8].

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

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

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

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

1. Разработать алгоритмы функционирования СИС, структуру алгоритмов, структуры данных.

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

3. Разработать математические модели информационного обеспечения СИС.

4. Разработать языковые и интерактивные средства взаимодействия пользователей с СИС. Определить их эргономические и психофизиологические характеристики.

5. Создать программное обеспечение подсистем СИС.

6. Исследовать эффективность внедрения разработанных систем.

Для решения этих задач и разработки системы был произведён анализ трудов российских и зарубежных учёных в следующих областях:

- информационное обеспечение органов управления среднего образования -O.A. Башкиров, A.M. Бершадский, A.C. Бождай, Ю.Г. Васин, В.Н. Васильев, Э.Д. Днепров, A.B. Духанов, А.Ю. Скопин, JI.B. Жилина и др.

- создания баз данных - К.Д. Дейт, Т. Кроув, В.Ш. Рубашкин, Ж. Шомье, Д. Эйвисон и др.;

-картографии - Н.М. Биктимирова, О.В. Бирюкова, JI.M. Бугаевский, A.C. Васмут, JI.A. Вахрамеева, О.Ю. Жукова, H.H. Лосяков, Н.И. Мельниченко, Т.П. Нырцова, К.А. Салищев, И.И. Стрижкин и др.;

- принципов построения ГИС и САПР - Е.И. Артамонов, A.M. Берлянт, J1. М. Бугаевский, М. Зейлер, О.К.Кадетов, Е.Г. Капралов, Н.В. Коновалова, A.B. Кошкарёв, А.И. Мартыненко, Л.Ф. Ноженкова, М.П. Сидоренко, B.C. Тикунов, A.M. Трофимов, В.Ё. Хаксхольд, В.Я. Цветков, C.B. Шайтура, Е.Е. Ширяев, D.F. Marble, D.J. Peuquet, H. Samet, S. Tanimoto и др;

- дискретной математики - O.E. Акимов, М.О. Асанов, В.А. Баранский, И.А. Башмаков, К. Берж, A.A. Грешилов, В.А. Евстигнеев, A.A. Зыков, Н. Кристофидес, О.П. Кузнецов, О. Ope, Д.В. Тюкавкин, Р. Уилсон, JT.P. Форд, Д.Р. Фалкерсон и др.).

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

Научная новизна работы заключается в разработке и создании:

- алгоритмов функционирования и архитектуры СИС для управления социально-образовательной сферой;

- структуры информационно-аналитической модели СИС для управления социально-образовательной сферой;

- структуры и состава баз данных СИС для управления социально-образовательной сферой;

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

- метода синтеза архитектуры подсистемы определения кратчайшего пути на модели графического слоя СИС;

- аналитических оценок сложности автоматизированного извлечения информации в СИС при решении задач в социально-образовательной сфере;

- способа тестирования цветового зрения пользователя СИС для управления социально-образовательной сферой и настройки пользовательского интерфейса по результатам тестирования.

Основные научные результаты:

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

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

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

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

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

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

Реализация результатов работы. Полученные в диссертации результаты и программное обеспечение внедрены в Юго-Западном и Северном окружных управлениях образованием г. Москвы. Акты внедрения и использования научных результатов приведены в приложении диссертационной работы.

На защиту выносятся:

- алгоритмы функционирования и архитектура СИС для решения оптимизационных задач в социально-образовательной сфере;

- структура информационно-аналитической модели СИС для управления социально-образовательной сферой;

- структура и состав баз данных СИС для решения оптимизационных задач в социально-образовательной сфере;

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

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

- аналитические оценки сложности автоматизированного извлечения графической информации в СИС при решении оптимизационных задач в социально-образовательной сфере;

- способ тестирования цветового зрения пользователя СИС для управления социально-образовательной сферой и настройки пользовательского интерфейса по результатам тестирования.

Апробация работы. Материалы диссертационной работы доложены на Ш-й и 1У-й международных конференциях «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта. С АО/САМ/РОМ» (Москва: ИПУ РАН, 2003, 2004 гг.), У-й молодёжной научно-технической конференции «Наукоёмкие технологии и интеллектуальные системы» (Москва: МГТУ, 2003), Ш-й международной научно-практической конференции «Математическое моделирование в образовании, науке и производстве» (Приднестровье, Тирасполь: ПГУ, 2003), международной конференции «Информационные средства и технологии» (Москва: МЭИ (ТУ), 2003), Региональной дистанционной научно-практической конференции «Методы и устройства психофизиологических исследований человека» (Йошкар-Ола: МарГТУ, 2003).

Публикации. По теме диссертации опубликовано 12 печатных трудов (5 статей и 7 тезисов докладов).

Структура и объём работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы и приложений. Общий объём диссертации составляет - 171 стр., основного текста - 139 стр., включая - 23 рис., - таб., списка литературы из - 105 наименований. Имеются 8 приложений на 32 стр.

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

Заключение

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

1. Определен класс специализированных информационных систем со сложно структурированными графическими данными (СИС), в которых за счет развитых средств взаимодействия пользователей с системой, особенно графических, при постоянно увеличивающейся сложности решаемых задач общение пользователей с системой происходит в реальном масштабе времени. На примерах систем, используемых в социально-образовательной сфере, рассмотрены особенности алгоритмов функционирования, их структурной организации, совмещенных графических и текстовых структур данных. Проведён анализ методов проектирования таких систем. Показано, что современные методы проектирования не учитывают особенности структур данных и способов их представления, отсутствуют методы автоматизации процесса синтеза их структур и разработки средств графического взаимодействия пользователей с системами.

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

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

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

5. Созданы языковые и интерактивные средства взаимодействия пользователя с СИС. Языковые средства взаимодействия содержат пять классов операторов: задания единиц измерения и масштабирования; формирования геометрических моделей; задания типов объектов и их настройки на цветовое восприятие пользователя; описания сопутствующих вычислений, геометрических построений и преобразований; описания растровой структур.

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

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

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

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

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

11. Разработанные в диссертационной работе модели, методы, алгоритмы, программное и информационное обеспечения СИС для управления социально-образовательной сферой внедрены в окружных управлениях образованием Северного и Юго-Западного административных округов г. Москвы. Получены акты о внедрении.

130