«ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И ПРОГРАММНЫЕ СРЕДСТВА: ПРОЕКТИРОВАНИЕ, РАЗРАБОТКА И ПРИМЕНЕНИЕ Сборник научных статей Гродно 2011 УДК 004 005.951(082) ББК 32.81я43 И38 Редакционнаяколлегия: кандидат физико-математических ...»

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

где H = { u i }, i>1 – хосты, подключенные к центральному серверу (где установлены программные средства для компьютерного проектирования технологии ИМС); D = {dj}, j>1 – тип данных, передаваемых на центральный сервер; O = {ok}, k>1 – тип сетевых операций (просмотр результатов, моделирование); Q = {q}, l>2 – возможные стеки протоколов, образующих сетевую среду (в зависимости от инструментов, используемых при реализации комплекса удаленного проектирования).

Учитывая требования к использованию различных альтернативных показателей работы сервера, необходимо применять вектор показателей эффективности :

где 1 = избыточность – показатель эффективности использования пропускной способности сетевого интерфейса центрального сервера; 2 = производительность – показатель эффективности работы сетевого интерфейса центрального сервера при различных нагрузках; 3 = нагрузка на оборудование – показатель эффективности использования разных инструментов при нагрузке центрального сервера и оперативной памяти; 4 = стоимость решения – показатель эффективности финансовых вложений; 5 = перспективность – показатель масштабности и развития данного решения; 6 = безопасность – показатель безопасности решения.

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

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

где аh – весовой коэффициент h-го частного показателя.

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

Архитектура комплекса удаленного проектирования В настоящее время известно несколько видов архитектуры комплекса удаленного проектирования, действующего посредством сети Интернет. Достаточно полный обзор существующих архитектур комплексов можно найти в работе [2].

Наиболее известные варианты комплекса удаленного проектирования в сети Интернет основаны на технологиях ssh, vnc, x11, vnp, а также web-сервере.

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

Некоторые результаты Центральное место в создании комплекса удаленного проектирования принадлежит Webсерверу, на котором размещено используемое для проектирования и проведения расчетов программное обеспечение. Web-сервер обеспечивает доступ пользователя к сайту, а также осуществляет обработку всех запросов, вводимых пользователем через браузер. Другая функция Webсервера – это осуществление обмена информацией о текущем состоянии проекта, полученной и обработанной при запросе пользователя. Таким образом, Web-сервер является связующим звеном между аппаратными средствами сети Интернет и пользовательским браузером. Наиболее удобным и эффективным в отношении указанных требований является Web-сервер Apache. Apache предоставляет богатые возможности, позволяющие настроить Web-сервер в соответствии с потребностями индивидуальных и корпоративных пользователей. Настройка сервера Apache производится с помощью директив, содержащихся в конфигурационных файлах. Apache позволяет создавать виртуальные Web-узлы, а также выполняет функции proxy-сервера.

Для обработки форм, которые содержат запросы проектирования (моделирования), а также в результатах расчетов, проведенных на сервере, можно использовать языки PHP/PERL, скриптовые языки, наиболее приспособленные к среде UNIX. Для сохранения в графическом формате (например, PNG) результатов моделирования предпочтительно использовать стандартную, бесплатную программу gnuplot, т.к. она обладает гибкими настройками и совместима с системами UNIX.

Screen-shot с результатами моделирования технологии формирования биполярного транзистора с использованием программного комплекса SUPREMIII представлен на рис.

Рис. Окончательное распределение концентраций примесей в активных элементах структуры биполярного транзистора, полученное с использование программного комплекса SUPREM III – Результат моделирования через глобальную сеть Интернет 1. Najbuk, M. Internet-based learning and design in microelectronics /M. Najbuk, V. Nelayev // Proc. Int Conf.

«e-learning jako metoda wspomagajca proces ksztacenia». – Gdask, Poland, 2006. P. 72–76.

Найбук, М.Н. e-обучающие комплексы в микроэлектронике /М.Н. Найбук // Материалы VIII международной научно-методической конференции «Наука и образование в условиях социальноэкономической трансформации общества». – Витебск, 2005. – С. 229–231.

Бречко Теодор, профессор, Университет в Белостоке, Республика Польша, [email protected].

Найбук Мирослав Николаевич, ассистент, Университет в Белостоке, Республика Польша, [email protected].

УДК 004.

СИСТЕМА МАШИННОГО СРАВНЕНИЯ ИСХОДНЫХ КОДОВ ПРОГРАММ

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

Введение В программировании одним из способов проверки правильности работы программы или алгоритма является проверка выдаваемых ими результатов на заранее подготовленном наборе исходных данных и правильных ответов – системе тестов. Кроме этого способа можно использовать аналитический – человеко-машинный анализ исходного кода и доказательство правильности работы алгоритма.

Для качественной проверки правильности решения задачи иногда необходимо несколько десятков тестов для того, чтобы убедиться, что автором учтены все возможные ситуации в исходных данных. Например, в задаче нахождения коэффициентов уравнения прямой в виде Ax+By+C=0 необходимо вычислить выражение k ( x2 x1 ) /( y2 y1 ), в знаменателе которого может оказаться значение 0, что приведет к аварийному завершению работы программы при отсутствии проверки соответствующей ситуации.

По дисциплине «Основы алгоритмизации и программирования» разработано 8 лабораторных работ. Каждая из них включает в себя от 8 до 12 задач. По каждой задаче используется от 4 до 20 тестов. Таким образом, преподавателю для однократной проверки решений всех задач одного студента необходимо выполнить около 12 * 10 * 8 = 960 запусков.

Для автоматизации процесса тестирования правильности решений задач используется система «eContest», изначально предназначенная для проведения соревнований по спортивному программированию. Для студентов 1-го курса созданы соревнования – лабораторные работы. Сейчас для них в системе доступно М задач и Н тестов.

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

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

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

Метрики программного обеспечения принято разделять на три основные группы:

метрики размера программ;

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

метрики сложности потока данных программ.

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

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

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

Метрики программного обеспечения используются в различных программных продуктах, в большинстве своем относящихся к разряду систем управления версиями (CVS, Subversion, Ration ClearCase, Jira, ClearQuest и т.д.). Они ориентированы на отслеживание изменений, вносимых в файлы при их многократной модификации.

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

В работе системы используются два типа метрик: концептуальные графы и количественноразмерные характеристики (описанные выше метрики). Для построения концептуальных графов используется аналог алгоритма, описанного в [3]. В узлах концептуального графа содержатся ключевые слова и конструкции языка программирования.

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

CALC CYCLE OUTPUT

CALC CONDITION

Листинг 1. Fragment of Course and Module classes begin writeln(m[p]);

end;

Используются следующие узлы: INPUT (ввод данных), OUTPUT (вывод данных), CALC (вычисления), CYCLE (цикл), CONDITION (условие), OUTPUT (вывод) – элементарные блоки структурного программирования.

Разработка системы Система состоит из трех частей: база данных, веб-приложение и модули расчета и анализа.

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

В базе данных, работающей на СУБД MySQL 5, для хранения значений каждой метрики используется отдельная таблица. Структура всех таких таблиц имеет вид (id по таблице, id решения по базе eContest, значение метрики). Это позволило упростить разработку приложений обработки данных, используя единый программный интерфейс доступа к данным. Кроме таблиц значений метрик в базе еще имеются таблицы для хранения результатов анализа (две таблицы для групп вариантов решений задач (группы и члены групп) и две таблицы для стилей написания и оформления исходных кодов) и очереди заданий.

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

Для реализации данного подхода использована технология Struts. В состав Struts входят три основных компонента: сервлет-контроллер, jsp-страницы и бизнес-логика приложения. Модель инкапсулирует бизнес-логику приложения. Управление передается обратно подходящему представлению посредством контроллера. Этот вызов соответствует запросу нужной jsp-страницы и перенаправлению. Перенаправление осуществляется путем обращения к набору соответствий между моделью и представлением.

Для организации совместной работы СУБД с web-приложением использована технология Hibernate. Hibernate не только решает задачу связи классов с таблицами базы данных, но также предоставляет средства для автоматической генерации и обновления набора таблиц, построения запросов и обработки полученных данных. Обеспечивается поддержка сохранности данных стандартных Java-объектов.

Примеры использования описанных выше веб-технологий можно найти в книге [4]. Для анализа используются 6 консольные приложения:

построения концептуального графа по исходному коду;

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

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

сравнения двух множеств характеристик (для характеристик, входящих в оба множества, иначе характеристика игнорируется);

обработчик очереди заданий (осуществляет запуск других приложений, контролирует корректность их работы).

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

Разработанная система сейчас находится в стадии отладки и тестирования разработчиками.

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

В перспективе ожидается внедрение разработанного приложения в опытную эксплуатацию.

Метрика программного обеспечения. Энциклопедия Википедия [Эл. Ресурс]. – Режим доступа:

http://ru.wikipedia.org/wiki/Метрика_программного_обеспечения.

Новичков, А. Метрики кода и их практическая реализация в Subversion и ClearCase. Часть 1 – метрики. / http://cmcons.com/articles/CC_CQ/dev_metrics/mertics_part_1/.

Богатырев, М.Ю. Решение некоторых задач Text Mining при поможи концептуальных графов. / М.Ю. Богатырев, В.В. Тюхтин. – ТГУ.

Блинов, И.Н. Java. Промышленное программирование: практ. пособие / И.Н. Блинов, В.С. Романчик. – Минск: УниверсалПресс, 2007. – 704 с.

Петрукович Иван Анатольевич, студент кафедры программного обеспечения интеллектуальных и компьютерных систем факультета математики и информатики Гродненского государственного университета имени Я. Купалы, [email protected].

Анищенко Иван Сергеевич, студент кафедры программного обеспечения интеллектуальных и компьютерных систем факультета математики и информатики Гродненского государственного университета имени Я. Купалы, [email protected].

Ващило Владимир Витольдович, преподаватель кафедры программного обеспечения интеллектуальных и компьютерных систем факультета математики и информатики Гродненского государственного университета имени Я. Купалы, [email protected].

УДК 004.

ПОИСК ИНФОРМАЦИИ В РАЗРОЗНЕННЫХ ДОКУМЕНТАХ

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

Задача Решение задачи поиска информации состоит в составлении поисковой системой набора ссылок на документы, удовлетворяющие некоторым критериям поиска. Наличие слов из поискового запроса в найденных документах является классическим вариантом критерия поиска. Такие поисковые системы как Google, Yandex, Rambler и многие другие успешно справляются с решением этой задачи. Помимо набора слов в поисковом запросе многие из них позволяют использовать специальный язык для расширенного поиска. Google, в частности, позволяет использовать специальные модификаторы для выделения слов, которые должны отсутствовать в документах, для которых можно использовать синонимы, усиления значимости слова, запрета изменения словоформы, возможности замены и т.п. Считается, что все слова, записанные в поисковом запросе через пробел без специальных модификаторов, должны присутствовать в теле документа. В результате пользователь получает ссылки на документы, которые содержат требуемые слова. Чем больше слов в поисковом запросе, тем более строгим является запрос (при отсутствии модификатора «ИЛИ»), тем меньше результатов выдает поисковая система: документы уточняются по мере добавления известных пользователю слов.

Рассмотрим пример 1. На запрос «грамматики» будет выдан набор ссылок на документы, содержащие такие фразы в различных словоформах: «грамматика русского языка», «контектносвободные грамматики» и пр. На запрос «графовая грамматики» будет выдан набор ссылок на документы, содержащиеся в результате предыдущего запроса, но уже обязательно содержащие и слово «графовые» в различных словоформах. На языке теории множества это означает найти подмножество множества. При поиске несколько ответов содержали ссылки на книгу грамматика и «Графовая» как фамилия.

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

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

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

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

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

Из слов словаря строится набор обобщенных понятий конкретной предметной области – тезаурус. Тезаурус состоит из понятий – существительных и глаголов.

В качестве модели предметной области предлагается использовать семантическую сеть.

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

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

Фреймы описываются с помощь графовых продукций.

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

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

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

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

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

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

Рис. 3. Решетка результатов запроса «средства порождения UML-диаграмм»

Степин, Ю.Г. Генерация структурной модели предметной области на основе атрибутивных графовых исчислений. /Ю.Г. Степин. // Информационные системы и технологии (IST2009): материалы V Международной научной конференции-форума (Минск, 16-17нояб. 2009 г.). В 2 ч. Ч. 2. – Минск:

А.Р. Вараксин, 2009. – с. 183 – 185.

Богатырев, М.Ю. Решение некоторых задач Text Mining при помощи концептуальных графов.

/М.Ю. Богатырев, В.В. Тюхтин. – ТГУ.

Степин Юрий Генрихович, старший преподаватель кафедры МИОЭС факультета экономики и управления Гродненского государственного университета имени Янки Купалы, [email protected].

Ващило Владимир Витольдович, преподаватель кафедры программного обеспечения интеллектуальных и компьютерных систем факультета математики и информатики Гродненского государственного университета имени Янки Купалы, [email protected].

УДК 004.

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

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

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

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

Проблемы обеспечения качества интерфейсов Нет единодушного согласия о трактовке определения практичности, но есть единодушное понимание важности обеспечения практичности приложений, так как именно от этого зависит успех и принятие пользователями (в широком смысле – рынком) программного продукта.

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

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

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

ISO/TR 16982:2002 предоставляет информацию о методах практичности для проектирования и оценки. Стандарт ISO 9241 состоит из 17-ти частей и покрывает большое количество аспектов, касающихся работающих за компьютером людей [1]. ISO/IEC 9126 «Оценка программного продукта – Характеристики качества и руководства по их использованию» был отдельно разработан в качестве стандарта для инженерии программного обеспечения [2]. Он состоит из 4-х частей: модель качества, внешние и внутренние метрики, а также метрики качества в использовании. По этому стандарту практичности отводится место одной из характеристик качества программного продукта. Практичность имеет собственные подхарактеристики: понятность, обучаемость, простота использования, привлекательность, соответствие практичности.

Модель качества В соответствии со стандартом ISO 9126 модель качества представляет собой иерархию из характеристик качества, которые объединяют в себе подхарактеристики качества и метрик этих подхарактеристик [3].

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

Для оценки практичности в рамках данного проекта использовалась модель, которая предлагается стандартом ISO 9126.

Оценка интерфейсов Проектирование пользовательского интерфейса должно происходить итеративно в цикле «проектирование – оценка практичности» до тех пор, пока не будут достигнуты удовлетворительные показатели практичности. Основные методы оценки практичности:

метод, основанный на метриках, моделях: используется модель, инструментальное средство или пользователи для получения эмпирических данных;

тестирование: проводится наблюдение за тем, как пользователи используют программный продукт;

экспертная (эвристическая) оценка: оценка пользовательского интерфейса с целью обнаружения проблем;

опрос (интервьюирование пользователей): общение с пользователем с целью проникновения в суть проблем, связанных с практичностью.

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

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

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

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

определялся контекст использования на основании требований к продукту;

акцентировалось внимание на подхарактеристиках практичности, исходя из контекста использования и знания стандартов качества;

формировался набор метрик;

проводились измерения.

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

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

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

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

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

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

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

Таблица. Набор метрик для оценки практичности 1 Понятность 2 Обучаемость 3 Простота использования 4 Привлекательность 5 Соответствие практичности Анализ полученных результатов позволил сделать следующие выводы.

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

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

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

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

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

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

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

ISO 9241 – 11: Руководство по практичности (1998).

ISO/IEC FDIS 9126 – 1: Программная инженерия – Качество продукта – Часть 1: Модель качества (2000).

Бахтизин, В. В. Стандартизация и сертификация программного обеспечения / В.В. Бахтизин, Л.А. Глухова. – Мн.: БГУИР, 2006. – С. 159 – 160.

Ворвуль Александр Александрович, ассистент кафедры программного обеспечения информационных технологий факультета компьютерных систем и сетей Белорусского государственного университета информатики и радиоэлектроники, магистр технических наук, [email protected].

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

УДК 004.891. И.Т. ДАВЫДЕНКО, Д.А. ЛАЗУРКИН, С.А. САМОДУМКИН

БАЗА ЗНАНИЙ ИНТЕЛЛЕКТУАЛЬНОЙ СПРАВОЧНОЙ СИСТЕМЫ

ПО ГЕОМЕТРИИ

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

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

Основным принципом при создании базы знания является унификация представления знаний в системе [1]. Для построения баз знаний используется множество подходов, одним из подходов является технология проектирования баз знаний, основанная на технологии OSTIS [2].

Баз знаний интеллектуальной справочной системы по геометрии Применим методику проектирования баз знаний, основанную на технологии OSTIS, при проектировании базы знаний интеллектуальной справочной системы по геометрии [3].

Данная методика включает в себя следующие этапы:

1. Разработка первой версии сборника тестовых вопросов.

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

Фрагмент 1-й версии тестового сборника вопросов системы по геометрии:

Запросы основных свойств заданного объекта o Какие высказывания описывают свойства прямоугольных треугольников?

Запросы минимального высказывания (минимального фрагмента базы знаний), описывающего семантически значимую связь между всеми объектами заданного множества объектов o Как связаны между собой понятия конгруэнтности и равновеликости?

Запросы пар высказываний, описывающих отличающиеся свойства заданных двух объектов o Чем отличается Понятия конгруэнтности геометрических фигур от Понятия конгруэнции между двумя геометрическими фигурами?

2. Запись в SСg-коде ответов на все тестовые вопросы.

Пример записи ответа на вопрос «По каким признакам классифицируются треугольники»

представлен на рис.1.

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

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

теорией, составляющей основу проектируемой базы знаний, является геометрия Евклида;

основными классами объектов исследования являются геометрические фигуры;

в качестве примеров конкретных объектов исследования (типичных представителей наиболее важных классов объектов исследования) в геометрии были выделены: линейные фигуры (отрезок, линия, луч и др.), планарные фигуры (многоугольники, окружность, круг и др.);

выделены основные отношения, составляющие предмет исследования: параллельность, перпендикулярность, пересечение, конгруэнтность, сторона, внутренний угол, лежать между, лежать против, вписанность и др.;

выделен набор основных утверждений (аксиом и теорем), описывающих различные свойства выделенных классов объектов исследования и выделенных отношений [4].

5. Разработка исходного текста базы знаний на псевдоестественном языке.

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

Рис. 2. Описание понятия «тройка точек» на псевдоестественном языке Рис. 3. Описание понятия «линия» на псевдоестественном языке 6. Перевод исходного текста базы знаний с псевдоестественного языка в SCg-код.

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

7. Анализ и уточнение распределения всех вводимых понятий по их логическим уровням.

Распределение понятий по логическим уровням основывается на определении понятий, т.е.

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

8. Анализ и уточнение распределения всех вводимых утверждений по их логическим уровням.

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

9. Логико-дидактическая структуризация базы знаний: декомпозиция и упорядочение выделенных разделов.

База знаний по геометрии декомпозируется на разделы: Ядро геометрии, Планиметрия, Стереометрия, Аналитическая геометрия.

На заключительной стадии разработки прототип системы по геометрии был успешно протестирован.

В заключении отметим, что данная работа выполнена в рамках открытого международного проекта OSTIS (Open Semantic Technology for Intelligent Systems) [2].

Гаврилова, Т.А. Базы знаний интеллектуальных систем / Т.А. Гаврилова, В.Ф. Хорошевский. – СПб.:

Питер, 2000. – 384 с.

OSTIS // Open Semantic Technology for Intelligent Systems [Электронный ресурс] – 2010. – Режим доступа: http://ostis.net/ – Дата доступа: 01.03.2010.

Голенков, В.В. Представление и обработка знаний в графодинамических ассоциативных машинах / В.В. Голенков [и др.]; под ред. В.В. Голенкова. – Минск, 2001. – 412 с.

Голенков, Интеллектуальные обучающие системы и виртуальные учебные организации / В.В. Голенков [и др.]; под ред. В.В. Голенкова. – Минск, 2001. – 488 с.

Т.А. Гаврилова Формальное представление сложноструктурированных знаний / Т.А. Гаврилова, Н.А. Гулякина, В.В. Голенков // Нечеткие системы и мягкие вычисления: сб. ст. Третьей Всероссийской научн. конф. в 2 т. – Волгоград, 2009. – Т. 1. – С. 40–45.

Давыденко Ирина Тимофеевна, студентка 5 курса факультета информационных технологий и управления Белорусского государственного университета информатики и радиоэлектроники, [email protected].

Лазуркин Дмитрий Александрович, студент 5 курса факультета информационных технологий и управления Белорусского государственного университета информатики и радиоэлектроники, [email protected].

Самодумкин Сергей Александрович, старший преподаватель кафедры интеллектуальных информационных технологий факультета информационных технологий и управления Белорусского государственного университета информатики и радиоэлектроники, [email protected].

УДК 004.5:004.

МОДЕЛЬ ЕСТЕСТВЕННО-ЯЗЫКОВОГО ПОЛЬЗОВАТЕЛЬСКОГО ИНТЕРФЕЙСА ИНТЕЛЛЕКТУАЛЬНЫХ СПРАВОЧНЫХ СИСТЕМ

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

Введение В основе предлагаемого подхода лежит модель пользовательских интерфейсов, основу которой составляет унифицированное кодирование информации при помощи абстрактного кодирования семантических сетей (Semantic Code) [2]. Естественно-языковой интерфейс рассматривается как специализированная интеллектуальная система, основанная на SC-коде (такие системы называются sc-системами).

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

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

Анализ предметной области Естественно-языковой интерфейс рассматривается как интеллектуальная система (scсистема). Как и любая sc-система, естественно-языковой интерфейс включает в себя базу знаний и машину обработки знаний.

База знаний естественно-языкового интерфейса включает в себя полное, либо частичное описание используемого естественного языка, что может включать в себя: фонетические, графические, семантические, лексические, грамматические (морфологические и синтаксические) правила, а так же различные лингвистические словари.

Лингвистические правила, а также словари, записываются на едином специализированном sc-языке, разработанным для описания различных лингвистических структур. Использование семантических сетей для «хранения» словарей естественных языков позволяет:

1. Избавиться от избыточности данных.

2. Объединять словари в одну базу знаний.

Такая база знания представляет собой отдельный ip-компонент, который будет востребован в различных интеллектуальных справочных sc-системах.

Машина обработки знаний естественно-языкового интерфейса включает в себя:

1. Операции морфологического, синтаксического и семантического разбора естественноязыковых текстов.

2. Операции по генерации естественно-языкового текста из sc-конструкций.

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

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

Анализируемое предложение представляет собой sc-конструкцию в которой строго фиксируется порядок слов и знаков в предложении.

На этапе морфологического анализа для каждой словоформы в sc-конструкции предложения строятся отношения в соответствии значений ее грамматических категорий, т.е. совокупности грамматических значений (род, падеж, склонение и т.д.). Грамматические категории могут присутствовать в базе знаний естественно-языкового интерфейса явно (словоформа присутствует в словаре с описанием ее грамматических категорий) либо грамматическая категория может выявляться на основании морфологических правил используемого естественного языка. Такой подход позволяет разработчику при проектировании естественно-языкового интерфейса выбирать между быстродействием и объемом проектируемой базы знаний.

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

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

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

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

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

Семантический этап анализа естественно-языкового текста можно разбить на два уровня:

поверхностно-семантический и глубинно-семантический [5].

На уровне поверхностно-семантического анализа выделяются отношения синонимии и омонимии между предложениями естественного языка [5]. Для этого каждое понятие в базе знаний идентифицируется (связывается связкой отношения идентификация*) множеством синонимов внешнего представления данного понятия.

На глубинно-семантическом уровне анализа строится однозначное отображение естественно-языкового текста в sc-память системы.

Результатом семантического анализа является конструкция запроса к системе. Сложность в получении такого результата заключается в семантической неполноте исходного естественноязыкового вопроса. Например, вопрос «В какой класс многоугольников входит понятие квадрата?» в развернутом виде будет выглядеть следующим образом: «Какое понятие является подмножеством понятия многоугольника и надмножеством понятия квадрат?». Из примера видно, что, в процессе развертки, произошли следующие подстановки: высказывание «входит» было развернуто в «является подмножеством», «квадрата» – «понятие квадрата», «класс многоугольников» – «понятие, являющееся подмножеством понятия многоугольника», «многоугольник» – «понятие многоугольника».

Такие преобразования протекают на этапе семантического анализа и кодируются в SC-коде (рис. 2).

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

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

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

Заключение Данная модель естественно-языковых интерфейсов предоставляет единую основу для анализа естественно-языковых текстов: начиная с ввода текста, морфологический, лексический, семантический анализ и генерация текста. Семантическая модель естественно-языковых интерфейсов интеллектуальных вопросно-ответных систем позволяет устанавливать отношения между семантически эквивалентными лингвистическими конструкциями и структурой внутренней памяти системы. Работа выполняется в рамках открытого проекта OSTIS [2].

Голенков, В.В. Представление и обработка знаний в графодинамических ассоциативных машинах / В.В. Голенков [и др.]. – Минск, БГУИР, 2001.

OSTIS // Open Semantic Technology for Intelligent Systems [Электронный ресурс] – 2010. – Режим доступа: http://ostis.net/ – Дата доступа: 01.03. Елисеева, О.Е. Естественно-языковой интерфейс интеллектуальных систем: учебное пособие / О.Е. Елисеева [и др.]. – Минск, БГУИР, 2009.

Лобанов, Б.М. Речевой интерфейс интеллектуальных систем: учебное пособие / Б.М. Лобанов [и др.]. – Минск, БГУИР, 2006.

Апресян, Ю.Д. Избранные труды, том II. Интегральное описание языка и системная лексикография / Ю.Д. Апресян. – Москва: Школа «Языки русской культуры», 1995.

Житко Владимир Александрович, студент 5 курса факультета информационных технологий и управления Белорусского государственного университета информатики и радиоэлектроники, [email protected].

Корончик Денис Николаевич, магистрант кафедры интеллектуальных информационных технологий факультета информационных технологий и управления Белорусского государственного университета информатики и радиоэлектроники, [email protected].

Мошенко Сергей Генадьевич, студент 5 курса факультета компьютерного проектирования Белорусского государственного университета информатики и радиоэлектроники, [email protected].

УДК 004.4'

СРЕДСТВА ОТЛАДКИ ПРОГРАММ, ОРИЕНТИРОВАННЫХ

НА ОБРАБОТКУ БАЗ ЗНАНИЙ

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

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

В данной статье описывается подход к созданию средств отладки, которые являются частью среды программирования для базового языка процедурного программирования, ориентированного на обработку семантических сетей, SCP (Semantic Code Programming) [1, 2, 3, 4]. В дальнейшем такой отладчик будем называть scp-отладчиком.

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

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

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

ассоциативный доступ к памяти и явное выделение связей между частями scp-программы позволяет отладчику проявлять «интеллектуальность» без анализа низкоуровневой структуры отлаживаемой программы;

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

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

Механизм отладки scp-программ Для добавления в scp-интерпретатор возможности отладки scp-программ необходимо расширить модель scp-процесса [1, 3]. Процесс, интерпретирующий scp-программу, должен сообщать отладчику о ходе своей работы. Для этого введем понятие трассировщика scp-процесса. Трассировщик scp-процесса – это микропрограмма, которая сопоставлена данному scp-процессу и получает сведения о ходе его выполнения. Каждому scp-процессу может быть поставлен в соответствие один трассировщик. Таким образом, в связку, обозначающую scp-процесс, будет добавлен дополнительный компонент с атрибутом ptrace_, который является знаком трассировщика.

Управление трассировщику передается в следующих случаях:

осуществилось выполнение одного scp-оператора (только в случае пошаговой трассировки);

в результате интерпретации scp-оператора произошла ошибка;

scp-процесс создал процесс-потомок;

scp-процесс завершился.

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

Эта же микропрограмма получает следующие сообщения управления от пользовательского интерфейса:

продолжить выполнение текущего отлаживаемого scp-процесса, который приостановлен;

включить режим пошаговой трассировки и перейти к следующему scp-оператору текущей scp-программы;

перейти к начальному scp-оператору scp-программы, которую вызывает текущий scpоператор.

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

Точка останова в scp-программе Традиционно для реализации функциональности точки останова используется специальная инструкция, при интерпретации которой управление передается отладчику для данного процесса, если он для этого процесса установлен.

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

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

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

Для всех найденных дуг их конечным элементов устанавливается знак созданной точки останова, а от самой точки останова к scp-оператору, на который она установлена, создается безусловный переход.

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

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

Рис. 1. Способ установки точки останова на scp-оператор opj На рис. 2 показан способ задания для scp-переменной vari в качестве значения узла vali. В таком способе задания можно выделить следующие структурные элементы:

заголовок scp-переменной для отображения на экране – это элементы с идентификаторами vari и valpair;

собственно само значение vali.

На экран пользователю достаточно выводить только эту информацию.

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

С учетом специфики отладки scp-программ при отображении значений scp-переменных возникают следующие проблемы:

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

неизвестен размер семантической окрестности, доступной по ассоциативным связям, значения scp-переменной, которую необходимо вывести на экран;

неизвестны элементы, которые необходимо удалить с экрана, при выключении отображения значения scp-переменной (кроме тривиальных случаев);

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

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

OSTIS // Open Semantic Technology for Intelligent Systems [Электронный ресурс] – 2010. – Режим доступа: http://ostis.net/ – Дата доступа: 01.03.2010.

Представление и обработка знаний в графодинамических ассоциативных машинах / В.В. Голенков [и др.]. – Минск, БГУИР, 2001. – 412 с.

Программирование в ассоциативных машинах / В.В. Голенков [и др.]. – Минск, БГУИР, 2001 – 276 с.

Голенков, В.В. Язык параллельного программирования, ориентированный на переработку сложноструктурированных знаний в структурно перестраиваемой ассоциативной памяти : учеб.-метод. пособие / В.В. Голенков, Н.А. Гулякина; каф. ИИТ, БГУИР. – Минск, 1998. – 82 с.

7. Rosenberg, Jonathan B. How Debuggers Works: Algorithms, Data Structures, and Architecture / Jonathan B. Rosenberg. – Wiley, 1996. – 272 p.

Житко Владимир Александрович, студент 5 курса факультета информационных технологий и управления Белорусского государственного университета информатики и радиоэлектроники, [email protected].

Лазуркин Дмитрий Александрович, студент 5 курса факультета информационных технологий и управления Белорусского государственного университета информатики и радиоэлектроники, dilaz03 @gmail.com.

Пивоварчик Ольга Васильевна, начальник отдела информационных технологий Барановичского государственного университета, [email protected].

УДК 519.

СИСТЕМА ДОЛГОВРЕМЕННОГО ПРОГРАММИРОВАНИЯ

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

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

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

Общие сведения Обычно время жизни данных, с которыми работают программы, не превышает времени работы самой программы, если они явно не были записаны во внешнюю память. Эта ограниченная длительность жизни временных данных заложена в семантику алгоритмических языков программирования – вся память, отданная программе, освобождается после ее завершения. С другой стороны, существуют другие системы разработки программ, называемые «системами программирования баз данных» (database programming) и «системы долговременного программирования» (persistence programming), в которых программа может работать с сохраненными во внешней памяти данными. Такие сохраненные данные называются долговременными или стабильными. Долговременные данные могут храниться в любых известных моделях данных: реляционных, объектных или смешанных. Основными отличиями долговременного программирования от обычного или от программирования баз данных являются направленность процесса разработки программы и наличие интегрированного хранилища во внешней памяти.

Главной задачей долговременного программирования является создание программных средств, которые оперируют долговечными, конкурентно доступными и потенциально большими объемами информации. В дальнейшем, такие программные средства будем называть долговременными или долговечными (ДПС) 2. Системой долговременного или стабильного программирования принято называть систему программирования, которая позволяет разрабатываемой программе оперировать долговременными объектами. Любые, вновь созданные объекты, являющиеся временными, могут становиться долговременными и, таким образом, у объектов появляется возможность пережить время выполнения программы. Типичными представителями таких долговечных программных средств являются CAD/CAM системы, системы автоматизации офисов, CASE средства, среды разработки программных средств, интегрированные системы управления, большие информационные системы различного назначения.

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

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

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

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

Ортогональные системы долговременного программирования Ортогональные системы долговременного программирования (ОСДП), как средства создания ДПС, отличаются от СУБД и языков программирования СУБД тем, что дают разработчику возможность пользоваться долговременными данными независимо от их назначения. Эта независимость становится возможной при следовании следующим трем принципам [2]:

Принцип независимости. Внешний вид программы должен быть независим от времени жизни используемых данных.

Принцип ортогональности типа. Любые объекты должны быть способны обладать любым временем жизни независимо от своего типа.

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

Объектные ОСДП (ООСДП) ставят перед своими разработчиками множество различных вопросов. Задачи, в которых используются ООСДП, настолько различны по своим требованиям, что практически невозможно разработать универсальную систему, которая предоставляет эффективные решения для всех возможных задач. Очевидно, необходимость решения различных задач будет приводить к различным архитектурам и различным подходам построения объектноориентированных систем долговременного программирования.

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

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

Выполнение программы или запроса в месте хранения долговременных объектов имеет ряд существенных достоинств:

высокая производительность;

минимизация трафика по сети;

невысокие требования к ресурсам рабочих станций клиентов;

использование централизованного сервера.

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

Современные персональные компьютеры обладают достаточной вычислительной мощностью и имеют достаточный для выполнения сложных задач объем ресурсов (память и диски). Часто оказывается, что общий объем оперативной памяти и суммарная производительность персональных компьютеров, подключенных к мощному серверу, в несколько раз больше, чем ресурсы сервера.

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

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

выполнение кода методов клиентом;

пересылку объектов и сообщений.

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

Альтернативой пересылки объектов к месту выполнения методов является модель удаленного вызова процедур типа RPC или ее адаптация к объектно-ориентированной модели RMI (удаленный вызов методов). Однако, при таком подходе плохо выразимы транзакционные операции над множеством объектов.

Предложенная в работе ООСДП, использующая «умного клиента» – частного случая концепции активных клиентов, являясь эффективной реализацией ортогональной персистентности объектов, является так же и средой разработки и выполнения для информационных Интернетсистем, где вся разработка может вестись на основе клиентского языка сценариев, не требуя изменений на других уровнях многозвенной архитектуры.

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

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

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

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

1. Atkinson, M.P. An Approach to Persistent Programming / M.P. Atkinson, P.J. Bailey, K.J. Chisholm, W.P. Cockshott, R. Morrison // Computer Journal. – 1983. – Vol. 26, № 4. – P. 360–365.

2. Atkinson, M.P. & Morrison, R. Orthogonally Persistent Object Systems / M.P. Atkinson, R. Morrison // VLDB Journal. – 1995. – Vol. 4, № 3. – P. 319-401.

Зудин Андрей Борисович, соискатель кафедры вычислительных систем и сетей факультета автоматики и телемеханики Московского государственного института электроники и математики, [email protected].

УДК 621.

ИСПОЛЬЗОВАНИЕ МОДЕЛИ ПРОЦЕССА СЪЕМКИ ДЛЯ ОЦЕНКИ ВЕЛИЧИНЫ

«СМАЗА» В ОПТИКО-ЭЛЕКТРОННОЙ АППАРАТУРЕ ДИСТАНЦИОННОГО

ЗОНДИРОВАНИЯ ЗЕМЛИ ИЗ КОСМОСА

На этапе проектирования оптико-электронной аппаратуры (ОЭА) дистанционного зондирования Земли (ДЗЗ) высокого разрешения из космоса требуется определить и по возможности компенсировать искажения («смазы»), связанные с пилотированием космического аппарата (КА) и особенностями функционирования ОЭА. Для оценки величин «смазов» разработана математическая модель процесса съемки.

Введение При создании ОЭА ДЗЗ из космоса высокого разрешения используется специальный режим работы фотоприемного устройства (ФПУ) – режим временной задержки и накопления (ВЗН).

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

Съемка подстилающей поверхности осуществляется за счет собственного движения КА. В фокальной плоскости объектива ОЭА формируется изображение, скорость и направление перемещения которого (еще говорят «бега») по ФПУ зависит от параметров орбиты КА, режима его работы и параметров ОЭА.

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

Ошибки в определении пространственной ориентации осей КА, ошибки стабилизации осей КА, форма геоида Земли, изменение высоты подстилающей поверхности по маршруту съемки, дисторсия объектива, погрешности изготовления и установки ФПУ влияют на величину и направление вектора скорости бега изображения по всей плоскости установки ФПУ, вызывают сдвиг изображения относительно столбцов матрицы ФПЗС (называемый «смазом» изображения), что, как следствие, снижает качество формируемых изображений [1-2].

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

Описание модели В модели использованы две декартовы системы координат: абсолютная геоцентрическая система координат (АГСК) и система координат фокальной плоскости съемочной системы (см. рис. 1).

Модель реализована с использованием программного пакета Matlab R2008a. Пользовательский интерфейс программы представлен на рис. 2.

Модель позволяет задать следующие параметры:

1) геометрия ФПУ (способ геометрического расположения матриц ФПЗС при использовании более одной матрицы);

2) параметры орбиты КА;

3) углы крена, рысканья и тангажа КА;

4) ошибки (СКО ошибок ориентации и стабилизиции), вибрации КА;

5) параметры объектива (фокусное расстояние, дисторсия);

6) параметры моделирования (количество моделируемых точек на каждом приемнике, временной шаг моделирования движения по орбите).

Результатом работы программы являются траектории движения проекций элементов подстилающей поверхности по матрицам ФПЗС (см. рис. 3).

Рис. 3. Пример траекторий бега изображения по фокальной плоскости Расчет продольного и поперечного «смаза» изображения Основываясь на результатах моделирования, программа рассчитывает скорости бега изображения по фокальной плоскости (см. рис. 4).

Рис. 4. Пример распределения скорости бега изображения по фокальной плоскости Пример рассчитанного продольного «смаза» системы с дисторсией представлен на рис. 5.

Рис. 5. Пример продольного «смаза» для ОЭА с дисторсией объектива Пример рассчитанного поперечного «смаза» для ОЭА, ФПУ которого состоит из 12 матриц ФПЗС, представлен на рис. 6.

Рис. 6. Пример поперечного «смаза», ФПУ которого состоит из 12 матриц ФПЗС Заключение Представленная модель позволяет определять величины «смазов» при проектировании ОЭА ДЗЗ из космоса высокого разрешения. Модельные данные могут быть использованы с целью минимизации постоянных составляющих продольных и поперечных «смазов», а также определения величин неустранимых «смазов».

Миллер, Б.М. Компенсация сдвига изображения при съемке с использованием ПЗС в режиме задержки и интегрирования / Б.М. Миллер, Е.Я. Рубинович // Информационные процессы. – Том 7, №1. – 2007. – Лаврова, Н.П. Космическая фотосъемка / Н.П. Лаврова. – М.: Недра, 1983.

Иванов Александр Петрович, аспирант кафедры системного анализа факультета радиофизики и электроники Белорусского государственного университета, инженер-конструктор 2-й категории ОАО «Пеленг», [email protected].

Сикорский Дмитрий Анатольевич, начальник отдела ОАО «Пеленг», кандидат технических наук, [email protected].

УДК 004.

МЕТОДОЛОГИЯ ПОСТРОЕНИЯ МОДЕЛИ ДИНАМИЧЕСКОЙ

РАСПРЕДЕЛЕННОЙ ПРЕДМЕТНОЙ ОБЛАСТИ

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

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

Введение В условиях динамично меняющейся внешней среды и в результате глобализации общества появляются задачи с новыми свойствами. Для их решения требуются «внешние» знания, непосредственными носителями которых являются эксперты. Как правило, знания фрагментарны, имеют произвольную структуру, различный формат и распределены в глобальной среде [1].

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

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

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

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

Пусть имеется некоторая сложно структурированная задача S и n ее атомарных подзадач S1, …, Sn. В рамках подзадач известны текст постановки (Text), спецификация требований к решению (Req) и ограничения на время (Time):

Предположим, что для решения задачи S требуются информационные ресурсы Z (знания), которые носят фрагментарный характер, распределены в k источниках и в сумме составляют предметную область Y. Носителями знаний являются эксперты Expert1,…,Expertk.

Требуется разработать методы интеграции знаний Zi, полученных из k удаленных экспертных источников, в единую предметную область Y, при условии, что Timei0, n, k – переменная величина.

Одним из основных этапов решения поставленной задачи является построение адекватной модели предметной области и разработка соответствующих алгоритмов.

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

[2], позволяют рассматривать возможность его использования для построения модели ПрО ССЗ.

Онтологическую модель, отражающую суть подхода П. Чена, можно представить следующим образом:

где Entity = (entity1, …, entityn) – конечное множество значимых сущностей предметной области;

Relation = f(entityi, entityj) – множество типов связей между сущностями; ERD – диаграммы, представляющие иерархию связей между сущностями.

Значимыми сущностями (Entity) в контексте расмматриваемого класса ССЗ являются подзадачи S1, …, Sn, исполнители Expert1, Expert2, …, Expertn и знания Z. Анализируя описанные компоненты и алгоритм построения модели, можно сделать вывод о том, что модель (2) покрывает некоторые свойства предметной области ССЗ. Однако, очевидны и существенные противоречия между требованиями исходной задачи и свойствами модели ПрО по П.Чену:

конечность множества сущностей противоречит свойству динамичности;

алгоритм позволяет получить статический одномоментный «снимок» ПрО в виде жестко формализованной ERD-модели;

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

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

Таким образом, прямое использование модели (2) и алгоритма П.Чена для распределенных ПрО невозможно.

Построение динамической модели Критичным компонентом модели (2) является ЕRD-граф, который соответствует иерархическому представлению целевой задачи, однако не решает проблему представления знаний в вершинах графа. Используя онтологический подход [3], уточним способ представления знаний в вершинах графа и построим онтологическую модель задачи. Для этого проведем модификацию модели (2) путем синтеза ERD-графа и фреймовой модели представления знаний:

Структура фрейма P определяет постановку задачи эксперту: Id – идентификатор задачи;

Text – текст постановки задачи; Spec – требования к решению. Структура фрейма Z описывает паттерн знаний: Y – решение (знания); Tool – средство реализации Y. Терминальные узлы графа представлены фреймами P (содержательная составляющая подзадачи) и Z (технологообразовательная составляющая). Слоты фрейма P заполняются центром, cлоты фрейма Z пусты.

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

Предлагается алгоритм построения модели ПрО, состоящий из двух этапов. На первом из них необходимо построить статическую часть модели, представляющую иерархию задач целевой задачи, на втором – динамическую часть, подключая к терминальным узлам фреймы P и Z. В результате формируется полная динамическая модель ПрО (см. рис.).

Наличие в модели динамического компонента позволяет подключать паттерны P и Z различной структуры для различных приложений, что соответствует свойству динамичности. Изолированность частей модели позволяет реализовать их в отдельных программных компонентах, что обеспечивает формирование второй части модели удаленными экспертами и тем самым удовлетворяется требование распределенности. Таким образом, предложенная модификация модели и алгоритма П.Чена, позволяет устранить статичность и неделимость модели ПрО.

Интеграция распределенных экспертных знаний: проблемы и решения / В.В. Краснопрошин [и др.] // Инфоматика – 2004. – № 1. – С. 45–53.

Чен, П. Модель «сущность-связь» – шаг к единому представлению данных / П. Чен // СУБД. – 1995. – Технология построения систем поддержки принятия решений на основе распределенных разнородных знаний / В.В. Краснопрошин [и др.] // Информатика. – 2004. – № 3. – С. 49–58.

Карканица Анна Викторовна, старший преподаватель кафедры программного обеспечения интеллектуальных и компьютерных систем факультета математики и информатики Гродненского государственного университета имени Янки Купалы, [email protected].

УДК 004.652.

О ПОСТРОЕНИИ ЭЛЕМЕНТАРНОГО БАЗИСА СИСТЕМЫ

ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ В БАЗЕ ДАННЫХ

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

Введение Все существующие алгоритмы нормализации отношений в реляционной базе данных проводят анализ системы функциональных зависимостей (ФЗ) между атрибутами, существующими в предметной области. На первом этапе алгоритмов нормализации решается задача удаления тех ФЗ, которые выводятся из остальных ФЗ, а именно задача построения элементарного базиса системы ФЗ. Эта задача, как и другие задачи анализа системы ФЗ, формализуется с помощью аксиом Армстронга [1]. При большом числе атрибутов и ФЗ актуальной становится задача построения элементарного базиса, содержащего минимальное число ФЗ (минимального элементарного базиса), и задача построения минимального элементарного базиса, содержащего минимальное число атрибутов (оптимального элементарного базиса).

Задачи построения минимального и оптимального элементарных базисов системы ФЗ впервые, по-видимому, были поставлены в работе [2], где были введены понятия тривиальной и нетривиальной псевдотранзитивных зависимостей в элементарном базисе системы ФЗ и был разработан алгоритм построения минимального элементарного базиса на основе выделения и анализа тривиальных псевдотранзитивных зависимостей. В фундаментальной монографии [3], англоязычное издание которой вышло одновременно с публикацией работы [2], Д. Мейер ввел понятие прямой определяемости в системе ФЗ, на основе которого также разработал алгоритм построения минимального элементарного базиса системы ФЗ. Что касается задачи построения оптимального элементарного базиса системы ФЗ, то в [3] также приведена постановка этой задачи, однако отсутствуют методы и алгоритмы ее решения. В доступной литературе по теории реляционных баз данных автору не удалось найти опубликованного алгоритма решения этой задачи. В настоящей работе введено обобщение понятия псевдотранзитивной зависимости в элементарном базисе системы ФЗ (понятие P – зависимости) и приведены свойства P – зависимостей, позволяющие построить все элементарные базисы системы ФЗ и выбрать из них минимальный и оптимальный элементарные базисы.

Формализация задачи Определение 1. Пусть R – конечное множество, A, B, C и D – подмножества R. Будем обозначать AB A B. Системой ФЗ на множестве R называется бинарное отношение на булеане B(R), удовлетворяющее аксиомам Армстронга [1]:

если B A, то A B (аксиома рефлексивности);

если A B и BC D, то AC D (аксиома псевдотранзитивности).

если имеет место ФЗ A B, то говорят, что A функционально определяет B или B функционально зависит от A.

Из приведенных аксиом можно вывести ряд свойств системы ФЗ, которые в литературе [ – 6] также называются аксиомами, хотя точнее называть их правилами вывода. Наиболее важными являются следующие правила вывода:

если A BC, то A B и A C (правило декомпозиции), действительно, по аксиоме рефлексивности имеем ABC B и ABC C, тогда по аксиоме псевдотранзитивности получим A B и A C ;

если A B, то AC BC (правило пополнения), действительно, по аксиоме рефлексивности имеем ABC BC, тогда по аксиоме псевдотранзитивности получим AC BC ;

если A B и A C, то A BC (правило объединения), действительно, по правилу пополнения имеем A AB и AB BC, тогда по аксиоме псевдотранзитивности получим В некоторых источниках, например в [4], в состав независимых аксиом Армстронга ошибочно включают правило пополнения, которое, как показано выше, легко выводится из аксиом рефлексивности и псевдотранзитивности. В работах [2, 4, 7] система ФЗ на множестве R называется структурой ФЗ на R, однако такое название не совсем удачно, поскольку отношение не обладает свойством антисимметричности, следовательно, не определяет структуру на R в математическом смысле этого понятия.