Моделі, методи та засоби управління навчанням користувача роботі в автоматизованій інформаційній системі

Размещено на http://www.allbest.ru/

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

МОДЕЛІ, МЕТОДИ ТА ЗАСОБИ управління НАВЧАННЯМ КОРИСТУВАЧА РОБОТІ в АВТОМАТИЗОВАНІЙ ІНФОРМАЦІЙНІЙ СИСТЕМІ

Спеціальність 05.13.06 - Автоматизовані системи управління та прогресивні інформаційні технології

Пригожев Олександр Сергійович

Одеса - 2007

Дисертацією є рукопис

Робота виконана на кафедрі системного програмного забезпечення Одеського національного політехнічного університету Міністерства освіти і науки України

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

Офіційні опоненти: доктор технічних наук, професор Цейтлін Георгій Овсійович, Інститут програмних систем НАН України, провідний науковий співробітник

кандидат технічних наук, доцент Малахов Євгеній Валерійович, Одеський національний політехнічний університет, завідувач кафедрою інформаційних систем у менеджменті

Захист відбудеться “20” вересня 2007 року в 13:30 на засіданні спеціалізованої вченої ради Д 41.052.01 в Одеському національному політехнічному університеті за адресою: 65044, м. Одеса, проспект Шевченко, 1, ауд. 400-А.

З дисертацією можна ознайомитися в бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченко, 1.

Автореферат розісланий “20” серпня 2007 р.

Вчений секретар спеціалізованої вченої ради Ямпольский Ю. С.

АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня кандидата наук за фахом 05.13.06 Автоматизовані системи керування та прогресивні інформаційні технології. - Одеський національний політехнічний університет - Одеса, 2007.

Метою дослідження є розробка моделей та методів, що дозволяють покращити результати навчання користувача АІС за рахунок використання експертних систем.

У роботі проведений аналіз існуючих засобів навчання й консультування користувачів. У результаті аналізу виявлена недостатність розвитку таких засобів, зокрема - відсутність підтримки на етапі планування дій користувача.

Для рішення цієї проблеми запропоновано управляти процесом взаємодії “користувач-АІС”, використовуючи як управляючу структуру експертну систему. Засобом придбання знань для такої системи обраний апарат формальних перетворень структурних схем алгоритмічних алгебр. Побудована інтерпретація абстрактної схеми управління В.М. Глушкова для людино-машинної системи. Взаємодія користувача з інтерфейсом описано за допомогою апарата формальної алгебри. Сформульовано стратегії поведінки користувача у АІС і доведене твердження про функціональну повноту таких стратегій в алгебрі Дейкстри.

Розроблені стратегії запропоновано представляти для експертної системи у вигляді графа. Розроблено алгоритми обробки такого графа. Запропонована інформаційна технологія навчання й консультування користувача. Проведено автоматизацію основних етапів цієї технології: розроблена експертна система допомоги й система управління базою знань для неї. Проведено апробацію розроблених засобів у рамках навчального процесу кафедри системного програмного забезпечення ОНПУ. Показано, що використання підсистеми допомоги дозволяє покращити якість навчання (зі ступенем достовірності 90% за критерієм Вілкоксона-Манна-Уітні).

Ключові слова: автоматизована інформаційна система, взаємодія “користувач-АІС”, знання про рішення задач, сценарій, алгебра сценаріїв, алгоритмичні алгебри, алгебри Дейкстри, алгебри Глушкова.

автоматизований інформаційний алгоритмічний алгебра

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

Диссертация на соискание учёной степени кандидата наук по специальности 05.13.06 Автоматизированные системы управления и прогрессивные информационные технологии. - Одесский национальный политехнический университет - Одесса, 2007.

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

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

Для решения задачи предложено управлять процессом взаимодействия “пользователь-АИС”, используя в качестве управляющей структуры планирующую экспертную систему на основе сценариев. Это позволяет реализовать принципы ситуационного управления системой “пользователь-АИС”. Построена интерпретация абстрактной схемы управления В.М. Глушкова для человеко-машинной системы. Показано, что реализация такого управления позволит существенно упростить взаимодействие с АИС обычных и специальных групп пользователей.

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

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

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

Проведена апробация разработанных средств в рамках учебного процесса кафедры системного программного обеспечения ОНПУ, а также при обучении незрячих пользователей. Разработанная экспертная система была использована при проведении лабораторных работ по дисциплинам “Объектно-ориентированное программирование”, “Системное программирование и операционные системы” и “Основы проектирования систем искусственного интеллекта”. Показано, что использование разработанных средств позволяет улучшить результаты обучения пользователя (на уровне достоверности 90% по критерию Вилкоксона-Манна-Уитни).

Ключевые слова: автоматизированная информационная система, взаимодействие “пользователь-АИС”, знания о решении задач, сценарий, алгебра сценариев, алгоритмические алгебры, алгебры Дейкстры, алгебры Глушкова.

Prigozhev A.S. Models, methods and control means for tutoring of the user to operate in the automated intelligence system. - Manuscript

Thesis for a candidate's degree of technical sciences by speciality 05.13.06 - Automated control systems and progressive information technologies. - Odessa national polytechnic university - Odessa, 2007.

The aim of this research is development of models and methods, allowing to improve tutoring results of AIS user due to the expert system usage.

In this work the analysis of existing training tools and users consultations is carried out. As a result of the analysis unsufficiency of evolution of such means is revealed, in particular - lack of support at the stage of user's actions scheduling.

To solve this problem it is offered to control process of human-computer interacting, using the expert system as a control structure. As means of knowledge acquisition for such system the apparatus of formal conversions of algorithmic algebras skeleton diagrams is offered Interpreting of an abstract control diagram of V.M.Glushkov for human-machine system is built. Interacting of user with interface is presented by means of formal algebra apparatus. Strategies of behaviour of the user in AIS are formulated and statement about functional entirety of such strategies in Dejkstra's algebra is proved.

The developed strategies are offered for representing for expert system in the form of graph. Algorithms of such graph handling are developed. The tutoring and consultation information technology for the user is offered. Automation of the fundamental stages of this technology is carried out: the support expert system and KBMS for it are developed. Approbation of developed tools within the educational process of chair „System software” at ONPU is carried out. It is shown, that usage of help subsystem allows to improve quality of user tutoring (with reliability degree 90 % by the Wilkokson-Manna-Whitney criterion).

Keywords: automated intelligence system, human-computer interaction , knowledge of problem solving, scenario, scenarios algebra, algorithmic algebras, Dejkstra's algebras, Glushkov's algebras.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Розвиток автоматизованих інформаційних систем (АІС) призвів до їх впровадження в різних сферах людської діяльності. Як наслідок цього відбулося ускладнення самих систем і розширення кола їх користувачів. Якщо раніше з комп'ютерами працювали люди, що мають спеціальну підготовку, то тепер користувачі можуть не бути фахівцями в області обчислювальної техніки. Крім того, найчастіше має місце віддаленість користувача від розроблювача АІС. Тому виникає задача підтримки користувача, тобто навчання й консультування в процесі його роботи, для підвищення ефективності керування АІС із боку користувача.

Для навчання користувачів застосовують текстові керівництва й електронні довідкові системи, убудовані в АІС. Недоліком текстових посібників є неоднозначність їхнього розуміння, відсутність опису всіх можливих задач, рішення яких необхідно користувачеві при роботі. А оперативне відновлення електронної довідки викликає труднощі, пов'язані з необхідністю спеціального програмного забезпечення (ПЗ), і може бути складним для непідготовленого користувача.

Для розширення можливостей текстових засобів консультування й навчання в користувальницьких інтерфейсах застосовуються спливаючі підказки, графічні піктограми, дружні майстри (Wizards), демонстраційні програми. Загальним недоліком цих засобів є неповнота або неоднозначність подання потрібних користувачеві задач, а для їх зміни необхідне втручання програмістів АІС.

Тому потрібно вирішити проблему забезпечення більшої гнучкості існуючим засобам допомоги користувачеві, а також можливості їхнього розвитку. Один з перспективних напрямків удосконалення систем підтримки користувачів це використання знань про інтерфейс, користувача і, особливо, розв'язувані задачі. Використання цих знань дозволяє управляти процесом взаємодії користувача й АІС. Як базу пропонується використати плануючу експертну систему (ЕС), модель подання знань у вигляді фреймів із заданим на них відношенням несуворого порядку, так звані сценарії. Ієрархія таких фреймів дозволить відобразити структуру задач, а відношення порядку ? послідовність дій користувача в АІС. При підготовці знань для ЕС зручно використати алгоритмічні алгебри.

Актуальність теми дослідження обумовлена необхідністю розробки підходів, що дозволяють вирішити важливу задачу - поліпшення якості й прискорення освоєння користувачем способів взаємодії з АІС, використовуючи знання про розв'язувані задачі.

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконувалася відповідно до плану НДР кафедри системного програмного забезпечення ОНПУ № 539-73 “Методи та засоби побудови автоматизованих інформаційних систем обробки інформації та управління”, № 393-73 “Інформаційні системи в проектуванні й керуванні”.

Мета і задачі дослідження. Метою дослідження є розробка моделей і методів, що дозволяють поліпшити результати навчання користувача АІС за рахунок використання експертних систем.

Для досягнення цієї мети вирішені наступні задачі:

- провести аналіз різних інтерфейсів взаємодії користувача і АІС, а також використаних у них систем навчання й консультування з метою виявлення шляхів їх подальшого розвитку;

- розробити абстрактну модель управління взаємодією користувача й АІС, що характеризує можливі режими навчання й консультування користувача;

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

- побудувати подання моделі поводження користувача у вигляді дерева задач;

- розробити способи планування рішення задач користувачем;

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

- провести програмну реалізацію експертної системи підтримки й дослідити її ефективність.

Об'єктом дослідження є системи навчання та консультування користувача в автоматизованих інформаційних системах.

Предметом дослідження є застосування плануючих ЕС для керування навчанням користувача.

Методи дослідження. Для аналізу існуючих систем навчання й консультування користувачів використовувалися методи загальної теорії задач.

У процесі розробки моделі діяльності користувача й опису стратегій рішення задач використані методи теорії формальних алгебр, перетворення структурних схем алгебр Дейкстри й Глушкова.

Побудова ЕС підтримки користувача й розробка відповідної інформаційної технології проведено з використанням теорії експертних систем і об'єктно-орієнтованого проектування.

Наукова новизна отриманих результатів полягає в розвитку й поглибленні теоретичних і методологічних основ побудови інтелектуальних систем підтримки користувача й розробки на їх основі експертної системи для навчання й консультування. У дисертаційній роботі отримані наступні нові наукові результати:

- вперше запропонована модель управління взаємодією користувача і АІС, заснована на абстрактній моделі управління Глушкова, з використанням плануючої експертної системи як управляючої структури;

- вперше запропонована модель поводження користувача при роботі з АІС у вигляді алгебри сценаріїв і доведена функціональна повнота цієї алгебри в алгебрі Дейкстри, що дає можливість описати за допомогою алгебри сценаріїв будь-який алгоритм рішення задачі користувачем;

- одержала подальший розвиток модель подання знань у вигляді сценаріїв, який полягає в розширенні характеристик підцілей умовою циклу й списком команд для досягнення підцілей, що дозволяє описати задачі користувача АІС;

- вперше розроблений метод перетворення структурних схем алгебри Дейкстри у дерево сценаріїв з використанням моделі поводження користувача на основі алгебри сценаріїв;

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

Практичне значення отриманих результатів. Розроблена прикладна інформаційна технологія допомоги користувачеві АІС, і її основі створена експертна система для його навчання й підтримки. Розроблені бази знань для виконання лабораторних робіт з курсу “Об'єктно-орієнтоване програмування”, “Системне програмування та операційні системи” та “Основи проектування систем штучного інтелекту”, які викладаються на кафедрі системного програмного забезпечення ОНПУ, і для навчання користувачів з особливими потребами роботі з офісними програмами.

Показано, що застосування запропонованих підходів дозволяє спростити навчання користувача роботі з АІС, а також покращити результати його навчання.

Особистий внесок здобувача складається в застосуванні підходу, заснованого на алгоритмічних алгебрах, для проектування систем навчання й підтримки користувача в АІС.

Автором запропоноване використання ієрархічної структури для подання задач, розв'язуваних в АІС [1, 7, 9]. Розроблено стратегії з використанням формального апарата алгебр Дейкстри, що дозволяють описати взаємодію користувача й АІС, і апарат формальних перетворень структурних схем алгоритмів рішення задач у ці стратегії [5]. Удосконалено подання знань у вигляді сценаріїв [2, 6, 7, 8]. Реалізовано експертну систему навчання й консультування користувача АІС [3, 4]. Автор брав участь у проведенні й аналізі результатів випробувань системи.

Апробація наукових результатів дисертації. Результати дослідження доповідалися на міжнародному семінарі “Современное компьютерное образование для лиц с ограниченными физическими возможностями” (м. Київ, 24-25 листопада 2003 р.), на XXXV конференції молодих дослідників ОНПУ (м. Одеса, 2004 г), на Міжнародній конференції “Искуственный интеллект - 2004. Интеллектуальные и многопроцессорные системы - 2004” (сел. Кацивелі, 20-25 вересня 2004 р.), науковому семінарі кафедри системного програмного забезпечення ОНПУ “Інтелектуальні системи й сучасні інформаційні технології”.

Публікації. За результатами досліджень опубліковано дев'ять наукових праць, у тому числі сім статей у спеціалізованих журналах, рекомендованих ВАК України, дві - у збірниках наукових праць конференцій.

Структура дисертації Дисертація складається з 138 сторінок, вступу, 4 розділів, 19 підрозділів, висновків, 43 рисунків, 25 таблиць, списку використаних джерел (102 найменування), 4 додатків.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

Взаємодія користувача й АІС охарактеризована як управління АІС користувачем. Зазначено, що метою взаємодії користувача й АІС є результат рішення задачі.

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

Розглянуто існуючі інтелектуальні інтерфейси користувача, їх структура й функції. Проаналізовано сучасні засоби інтелектуалізації користувальницького інтерфейсу: адаптивний інтерфейс, технологія Microsoft Intellisense, природно-мовні засоби. Для управління системою “користувач-АІС” обрано й обґрунтовано застосування методів ситуаційного управління із застосуванням плануючої ЕС.

У другому розділі на основі абстрактної моделі управління, запропонованої В.М. Глушковим, розроблена абстрактна модель управління взаємодією “користувач-АІС” (рис. 1), сформульовані стратегії поводження користувача з використанням формального апарата алгебр Дейкстри й доведене твердження про їх функціональну повноту.

З використанням абстрактної моделі управління “користувач-АІС” уведені три режими підтримки користувача: автономний (I режим), режим спостереження за діалогом (II режим) і режим автоматизованого виконання команд (III режим). Відповідність режимів підтримки користувача та етапів рішення задачі наведене в табл. 1.

Таблиця 1. Відповідність режимів роботи управляючої структури й етапів рішення задачі

	Ознайомлення	Планування	Виконання	Контроль
I режим	+	+		+
II режим	+		+	+
III режим	+	+	+	+

Рис. 1. Абстрактна схема управління системою “користувач-АІС”.

Для опису користувальницьких стратегій в алгебрі Дейкстри проведена класифікація елементів управління в графічному інтерфейсі. Запропоновано розглядати три класи елементів управління: командні, призначені для уведення команд; інформаційні для вводу-виводу даних; елементи-колекції, до яких відносяться вікна графічного інтерфейсу, групи компонентів управління й т.п. Розроблений формальний опис графічного інтерфейсу АІС у вигляді алгебраїчної системи:

(1)

де MASS - розмічений масив станів елементів інтерфейсу. У розмітку входять символи початку й кінця масиву, а також покажчик на поточний елемент. Масив складається з кортежів виду:

(2)

де t - тип елемента управління (однорядкове поле, кнопка й т.д.), d - дані, що перебувають в елементі управління l - кількість рядків вводу, займаних даними, c позиція курсору в елементі управління, f_t - гарнітура шрифту тексту в елементі управління в позиції праворуч від курсору вводу, f_s - розмір шрифту в елементі управління в позиції праворуч від курсору вводу, f_b - тип шрифту в елементі управління напівжирний, курсив, підкреслений, f_ch - додаткові характеристики шрифту, e - доступність даного елемента управління для користувальницького вводу. := - операція, визначена на підмножині інформаційних елементів, що дозволяє змінювати й одержувати значення параметрів елементів. () - операція застосується для будь-якого елемента масиву MASS і повертає значення елемента кортежу (2), індекс якого переданий як операнд. EXEC - операція дозволяє виконати команду, зіставлену елементу управління. MOVEB(), MOVEF() - операції зміни положення покажчика. >, <, = - двомісні предикати, що приймають значення “істина” у тому випадку, якщо ліва частина більше, менше або дорівнює правій.

Щоб урахувати в стратегіях допустимість команд і можливість їх циклічного виконання, у роботі проведена класифікація дій користувача й АІС. Вони розбиті на два класи: припустимі й неприпустимі дії. Клас припустимих дій розділений на два підкласи: дії виконувані циклічно й однократно.

Для опису взаємодії користувача й АІС запропоновано використати алгоритмічні алгебри Дейкстри. Вибір саме цієї форми подання обумовлений тим, що структурна схема алгоритму є найбільш простим способом опису процесу рішення задачі. Також у вигляді структурної схеми може бути представлений відразу декотрий клас алгоритмів. Це дозволить однократно побудовану базу знань використати для цілого класу задач. Важливе достоїнство цього підходу - наявність формального апарата перетворень одних схем в інші і перетворення граф-схеми алгоритму в схему алгебри Дейкстри, що дозволяє позбавити інженера по знаннях від необхідності вивчення формального апарата алгебр Дейкстри та дає можливість описувати рішення задач у вигляді звичайної граф-схеми алгоритму.

У розгляд уведені дві структурні схеми:

(3)

(4)

Структурна схема (3) являє собою опис виконання команди в АІС. Якщо виконується умова альтернативи u_a, то виконується команда, що привласнена змінній A. Команда виконується доти, поки не стане істинною умова . Якщо ж умова не виконується, то користувач нічого не виконує, що відображено у схемі за допомогою тотожнього оператора . Користувач виконує всі команди в АІС послідовно. Тому в розгляд включена композиція (4), що полягає в послідовному застосуванні операторів A і B.

Відповідно до розробленої класифікації дій користувача в АІС побудована алгебра структурних схем - алгебра сценаріїв:

(5)

де SUPER - сигнатура, що складається з операцій суперпозиції, підстановки і ототожнення змінних, L(2) - множина булевих операцій: кон'юнкція, диз'юнкція та заперечення.

У роботі доведене наступне твердження.

Твердження (про функціональну повноту системи ALGS). Система ALGS є функціонально повною системою в алгебрі Дейкстри.

Зі справедливості твердження випливає, що за допомогою системи ALGS можливо описати будь-яку структурну схему алгебри Дейкстри, а, отже, представити будь-який алгоритм.

Застосувавши до схеми (3) L-згортку й привласнивши першому входженню змінної u_a значення “0”, а другому - “1”, одержимо тотожний оператор:

(6)

Далі, застосовуючи до схеми (3) L-згортку, інверсію логічних змінних і привласнюючи змінній u_l значення “1”, приходимо до усіченої альтернативи:

(7)

Привласнивши обом входженням u_a значення “1” і застосувавши до схеми (3) С-згортку, будемо мати:

(8)

Отримано цикл із постумовою. Для перетворення його в цикл із предумовою застосуємо до останнього вираження з (8) тотожність і перше входження змінної A замінимо на тотожний оператор E. Отриманий цикл представимо у вигляді:

(9)

У результаті знову отримана схема з алгебри (5).

Повна альтернатива в алгебрі сценаріїв може бути представлена за допомогою локально замкнутих умов. Локально замкнуті умови в алгебрі Дейкстри - це умови, значення яких можуть змінитися лише один раз. Для подання повної альтернативи необхідно, щоб умова повної альтернативи була локально-замкнутою. Тоді повна умова в алгебрі сценаріїв приймає вид:

(10)

Таким чином, нами побудована система тотожностей (6) ? (10), що дозволяє перетворити будь-яку структурну схему алгебри Дейкстри в схему з алгоритмічної алгебри сценаріїв.

Побудована алгоритмічна алгебра дозволяє представити будь-який алгоритм взаємодії користувача з інтерфейсом. Структурну схему в алгебрі сценаріїв зручно використати при аналізі алгоритму рішення задачі з метою придбання знань про процес рішення задачі. Такий аналіз проводиться у два етапи: перетворення структурної схеми алгоритму в алгебрі Дейкстри в алгоритмічну алгебру сценаріїв і аналіз отриманого виразу з метою побудови структури задач.

У третьому розділі на основі побудованої алгебри сценаріїв (5) розроблене подання знань для ЕС на основі дерева задач.

Як вказувалося раніше, інженер по знаннях уводить інформацію про процес рішення задачі у вигляді граф-схеми алгоритму. Однак використання граф-схеми для підтримки користувача неприйнятно, тому що потребує від нього знань позначень, що застосовуються у граф-схемах алгоритмів. Тому при взаємодії користувача із плануючою експертною системою підтримки йому видається структура задач у вигляді дерева. Використання дерева дозволяє інтуїтивно зрозуміло пояснити користувачеві кроки рішення задачі, не вимагаючи від нього знань спеціальних термінів і позначень із галузі комп'ютерних наук.

Для побудови графа виділені найбільш чітко формалізовані ознаки АІС. До них відносяться: команди, алгоритми рішення задач, структура задач. Під структурою задач розуміється взаємозв'язок задач і підзадач.

Вихідні дані для побудови моделі подання знань для системи “користувач-АІС” - це множина задач T, які розв'язуються в АІС. Серед істотних властивостей задач можна виділити назву і опис задачі, вихідні дані, команди для рішення задачі, алгоритм її рішення й опис результатів. Під T² розуміється декартовий добуток, що визначає множину усіх пар задач:

(11)

Визначимо тепер формальне відношення “бути підзадачею” на множині задач.

Визначення. Відношенням “бути підзадачею” назвемо множину пар ідентифікаторів таких, що процес рішення задачі t_j входить у рішення задачі t_i.

Позначивши уведене відношення S_t, можна записати:

(12)

Відношення (12) ілюструє зв'язок задач і підзадач АІС. Отже, граф цього відношення можна використати для моделювання ситуацій у процесі взаємодії користувача із системою. Розглянемо особливості графа відношення S_t. Задачі, що виникають перед користувачем у процесі його роботи в АІС, є алгоритмічно розв'язними. Тому під включенням процедури рішення підзадачі в процедуру рішення задачі розуміється суворе включення структурної схеми алгоритму рішення підзадачі в структурну схему алгоритму рішення задачі. Отже, відношення S_t іррефлексивно, тому граф відношення S_t не містить петель. У силу визначення поняття підзадачі відношення S_t транзитивно і несиметрично. Це означає, що граф зазначеного відношення буде містити тільки спрямовані ребра.

Уведемо в розгляд множину подзадач тільки однієї задачі.

(13)

У формулі (13) - задача, що не є підзадачею жодної задачі з множини . Визначимо множину :

(14)

Побудоване відношення буде містити транзитивні пари, а на графі відношення будуть присутні транзитивні ребра. Далі будемо розглядати піддерево безпосередніх підзадач, яке є остовним деревом для графа задач тільки однієї задачі.

Визначення. t_j є безпосередньою підзадачею задачі, t_i якщо:

1.

2. Не існує такого , що й

Виходячи з наведеного визначення безпосередньої підзадачі, можна стверджувати, що остов графа задач містить тільки безпосередні підзадачі. Коренем дерева є задачі, які не є підзадачею жодної задачі, яке входить у дерево. Формулювання цієї задачі збігається з метою діалогу користувача та АІС. Формально цю умову можна записати в такий спосіб:

(15)

На основі наведеного вище визначення введемо множину , елементами якого є пари елементів множини , що задовольняють визначенню безпосередньої підзадачі.

(16)

Результати рішення задачі можуть залежати від порядку рішення підзадач. Це пов'язане з тим, що в загальному випадку операція композиції не комутативна. Тому для визначення порядку виконання підзадач, що є безпосередніми для однієї задачі, кожній задачі поставимо у відповідність номер, і тоді припускаємо, що підзадачі одного рівня вирішуються в порядку зростання номерів.

Для подальшого подання графа задач зручно скористатися розширеною матрицею суміжності дерева задач, яка визначається за формулою:

(17)

У формулі (17) M - матриця суміжності графа задач. Ідентифікаторами рядків і стовпців розширеної матриці є ідентифікатори задач.

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

Властивість 1. У рядку, що відповідає кореню дерева задач, можуть перебувати тільки “1” і “0”, а в стовпці ? тільки “-1” і “0”.

Властивість 2. У рядку, що відповідає термінальній вершині дерева, може перебувати один і тільки один елемент “-1”, інші елементи дорівнюють “0”.

Властивість 3. Кожному елементу “1” відповідає симетричний йому елемент “-1” щодо головної діагоналі.

Властивість 4. У кожному рядку може перебувати не більше одного елемента рівного “-1”.

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

Для подання цієї інформації розроблений спосіб представлення умов на графі задач. Граф, навантажений умовами, будемо називати умовним графом задач.

Уведемо в розгляд множину умов U, а також два відображення: , що визначає умову альтернативи, і , що визначає умову циклу.

(18)

(19)

Зіставимо кожній вершині графа команду для рішення деякої задачі. Якщо вершина графа містить підзадачі, то їй зіставляється спеціальна команда “алгоритм”, що говорить про те, що дану задачу можна вирішити за допомогою алгоритму, який складається з певної послідовності команд АІС. Пропоновану розширену множину команд АІС будемо позначати буквою С^#. Визначимо відображення A:

(20)

Таким чином, навантажений граф задач можна охарактеризувати підмножиною B декартова добутку:

 (21)

Визначимо цю множину формально:

(22)

Нехай - це множина п'ятірок з B, у яких перший компонент дорівнює . Тоді утворить сценарій для рішення задачі .

Третій, четвертий і п'ятий компонент кожної п'ятірки, що належить множині B, залежать від вибору першого й другого компонента. Тому для подання умов зручно використати формат раніше описаної матриці суміжності графа задач. На перетинанні рядка й стовпця даної матриці будуть перебувати умови альтернативи. Ці умови перевіряються тільки при проходженні в одному напрямку ребра графа задач. Тому їх формулювання в пропонованій матриці суміжності будуть розташовані в тих же позиціях, у яких розташовані “1” у розширеній матриці суміжності графа задач. Інші комірки матриці умов порожні. Матриця умов циклу аналогічна по способу побудови матриці умов альтернативи.

Для одержання описаного графа задач зі структурних схем алгебри сценаріїв (5) розроблено подання основ (3) і (4) алгебри сценаріїв (5) у вигляді графа. У структурній схемі (3) спочатку перевіряється умова, і якщо вона істинна, то виконується циклічно оператор A до досягнення значення “істина” умовою циклу. У випадку хибності умови альтернативи нічого не виконується. Якщо операторні змінні SUBP і A позначати як вершини умовного графа, то граф, що відповідає схемі (3), показаний на рис. 2.



Рис. 2. Подання структурної схеми SUBP у вигляді графа.

Рис. 3. Подання композиції на графі задач.

Композиція двох операторів представляється в алгебрі сценаріїв відповідно до співвідношення:

(23)

Відповідний схемі фрагмент графа задач наведений на рис. 3.

Таким чином, побудовано подання знань про розв'язувані задачі у вигляді графа, засноване на алгебрі сценаріїв (5).

Опишемо механізм підтримки користувача з використанням графа задач. Для цього необхідна інформація про ступінь рішення задачі. Уведено три ступені рішення задачі: не вирішена, частково вирішена, повністю вирішена.

Визначення. Задача повністю вирішена користувачем в АІС до даного моменту часу, якщо користувач виконав необхідні йому перетворення предметної області до необхідного стану.

Визначення. Задача частково вирішена користувачем в АІС до даного моменту часу, якщо виконано частину кроків по перетворенню предметної області.

Визначення. Задача не вирішена користувачем в АІС у тому випадку, якщо користувач не виконав перетворення предметної області.

Для розрізнення ступенів рішення кожної задачі введемо множину міток:

(24)

Символ F використовується для повністю вирішеної задачі, P - для задачі, що перебуває в процесі рішення, N - для невирішеної задачі. На графі мітки F, P, N будуть проставлятися на ребрах графа, що відповідають підзадачам деякої задачі. У вершині, з якої здійснюється процес планування, мітка P проставляється в момент старту процесу планування. Зміна оцінки P на F на всіх ребрах, що виходять із початкової вершини, буде означати закінчення процесу планування.

Побудовано алгебраїчну систему, що описує базові операції й предикати, необхідні при плануванні:

(25)

де MATRS - матриця суміжності, ACMATR - матриця умов альтернативи, LCMATR - матриця умов циклу, WFMATR - матриця робочої області фактів, яка представляє з себе дерево індентифікаторів задач, що співпадає за структурою з базою знань. У робочій області фактів позначається ступінь рішення задачі користувачем. P - множина покажчиків на рядок і стовпець матриць. Визначимо на основах MATRS, ACMATR, LCMATR, WFMATR операцію “[]”. Параметрами цієї операції є покажчик на рядок і стовпець матриці, до якої застосовується операція. Результатом виконання операції є значення на перетинанні рядка й стовпця матриці. Уведена також елементарна операція “:=”, що привласнює значення виразу або змінної, розташованої праворуч від знака операції, змінній ліворуч від знака операції. Для покажчиків визначена елементарна операція EX, параметрами якої є значення покажчиків на рядок і стовпець. Результатом виконання цієї операції є обмін значень покажчиків на рядок і стовпець матриці, що еквівалентно операції переходу між вершинами графа задач. Для пересування покажчика на одну позицію убік першого рядка або стовпця уведена елементарна операція “--”, а для пересування убік останньої “++”.

На матрицях ACMATR і LCMATR уведені два предикати TRANSLATEA і TRANSLATEL. Параметрами цих предикатів є покажчики на рядок і стовпець матриці, а результатом твердження про істинність або хибність умови альтернативи або циклу відповідно.

На матриці WFMATR визначені дві елементарні операції: USERMARK і CLEARUM. Застосування першої з них буде означати спробу користувачем поставити мітку про рішення задачі, а другої - зняття такої мітки. Також у сигнатуру операцій уводяться логічні операції: кон'юнкція, диз'юнкція, заперечення й операція зміни пріоритету логічних операцій “()”. Перераховані операції розуміються у звичайному їхньому змісті. На цій же матриці вводяться три предикати. Предикат NOTMARKED є істинним у тому випадку, якщо на перетинанні рядка й стовпця матриці, обумовлених аргументами предиката, відсутня мітка, яка свідчить про виконання задачі. Предикат PMARKED істинний у тому випадку, якщо на перетинанні рядка та стовпця WFMATR стоїть мітка, що відповідає частково вирішеній задачі. Предикат FMARKED істинний у тому випадку, якщо вершина графа задач, що задається параметрами предиката, відповідає повністю вирішеній задачі.

У сигнатуру предикатів входять предикати порівняння “=”, “>”, “<”, “>=”, “<=”. Визначимо далі ці предикати. Предикат “<” є істинним, якщо позиція покажчика, який стоїть в лівій частині відношення, менше позиції покажчика, що знаходиться в правій частині. Предикат “<=” аналогічний за значенням предикату “<”, однак він є істинним також і у випадках, якщо значення покажчика в лівій частині дорівнює значенню покажчика в правій частині предиката. Предикат “>” істинний, якщо позиція покажчика, який знаходиться в лівій частині відношення, більше позиції покажчика, що стоїть в правій частині. Предикат “>=” аналогічний за значенням предикату “>”, однак він істинний також і у випадках, якщо значення покажчика в лівій частині дорівнює значенню покажчика в правій частині предиката.

Уведено алгоритмічну алгебру Глушкова, яку зручно використати для опису алгоритмів плануючої ЕС, оскільки в її сигнатуру, крім основних операцій алгебри Дейкстри, уведена операція прогнозування, за допомогою якої зручно описати алгоритми перевірки коректності й узгодженості плану користувача:

(26)

де SOP - сигнатура операцій алгебраїчної системи (25), SPR - сигнатура предикатів алгебраїчної системи (25), СИГН_АГ сигнатура алгебри Глушкова, що складається з композиції, альтернативи, циклу й операції прогнозування. З використанням даної алгебри сформульований алгоритм планування на графі задач.

(27)

Оператор CHECKCORRECT дозволяє перевірити коректність постановки мітки користувачем. Він істинний, якщо користувач може поставити мітку в даній вершині дерева. Оператор SETMARK у випадку істинності умови альтернативи дозволяє вибрати мітку, яку потрібно проставити, в залежності від стану рішення задач, які відповідають дочірнім вершинам дерева. CHANGEPARENT змінює мітки батьківських і дочірніх, стосовно поточної, вершин відповідно до зміненого стану задачі, обраної користувачем. Предикат CHECKCORRECT реалізує перевірки умов збереження коректності плану, операція SETMARK і CHANGEPARENT- стратегії постановки мітки, CLEARUM - стратегії зняття мітки.

На основі запропонованої алгебри сценаріїв (5), формальних перетворень схем алгебри Дейкстри в алгебру сценаріїв (6) ? (10) і подання схем алгебри сценаріїв у вигляді графа (див. рис. 2, 3) розроблена інформаційна технологія допомоги користувачеві, що складається із двох етапів: попереднього й навчального. Попередній етап містить у собі підготовку й зберігання бази знань про задачі на основі графа. Він містить у собі наступні кроки:

1. Формулювання задач. На цьому етапі складаються словесні описи задач, розв'язуваних в АІС. Ці описи можуть створюватися розроблювачем бази знань із інструкції користувача системи або за результатами діалогу з користувачами АІС.

2. Розробка алгоритму рішення задачі. Розроблювач бази знань, на основі власного досвіду роботи з наявною АІС, описує порядок дій при рішенні задачі за допомогою граф-схеми алгоритму рішення.

3. Формальні перетворення алгоритму рішення із граф-схеми до структурних схем алгебри Дейкстри. Цей етап може бути виконаний розроблювачем бази знань вручну або автоматизований за допомогою відповідних розширень системи управління базою знань (СУБЗ). Для цього використовуються перетворення граф-схем у схеми алгебри Дейкстри.

4. Формальні перетворення структурних схем алгоритмів в алгебрі Дейкстри до структурних схем алгебри сценаріїв, відповідно до формул (6) ? (10). Даний етап може виконуватися вручну або автоматизовано. Для цього в СУБЗ передбачається транслятор виразів в алгебрі Дейкстри в алгебру сценаріїв.

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

6. Редагування й перевірка коректності бази знань. Здійснюється з використанням СУБЗ розроблювачем бази знань.

Використання пропонованої технології не вимагає від інженера по знаннях обов'язкового знайомства з алгебрами алгоритмів, тому що пункти 3 ? 5 можуть виконуватися автоматично. Розроблювач бази знань уводить граф-схему, а одержує граф задач.

На навчальному етапі відбувається безпосередня взаємодія кінцевого користувача АІС (учня) з ЕС навчання й консультування. У нього включені наступні кроки:

1. Ознайомлення зі структурою задач в АІС.

2. Складання послідовності дій при рішенні задачі планування.

3. Виконання дій в АІС.

4. Контроль ходу рішення задачі.

У четвертому розділі розглядається побудова ЕС підтримки користувача й СУБЗ, а також проведення експериментів з метою дослідження ефективності розробленої системи.

Проведено об'єктно-орієнтований аналіз і проектування СУБЗ і ЕС навчання, побудовані діаграми прецедентів, послідовностей і класів.

Основними функціями СУБЗ є: завантаження файлу бази знань, вивантаження бази знань із пам'яті, коректування дерева задач, введення алгоритму рішення задачі й перевірка бази знань.

Розроблено плануючу ЕС допомоги користувачеві. Структура й функції цієї системи у вигляді діаграми прецедентів представлені на рис. 4.

Рис. 4. Діаграма прецедентів для ЕС навчання й консультування.

Акторами на даній діаграмі виступають користувач, АІС, для якої розробляється база знань. Також на діаграмі представлені засоби інтеграції розроблювальної системи й АІС. Для забезпечення функціонування у режимі II необхідний монітор, що дозволяє перехоплювати команди користувача й повідомлення АІС, та інтерпретатор “команда-задача”, що ставить у відповідність команді задачу в робочій області фактів. Також за допомогою зворотнього інтерпретатора “задача-команда”, що формує команди АІС, і емулятора команд, що передає їх на виконання в АІС, можна виконати побудований план. Ці блоки забезпечують функціонування ЕС у третьому режимі.

Основними функціями експертної системи є відмітка задачі, зняття мітки з задачі, перевірка плану, перегляд плану й видача повідомлень про помилки. Прецеденти пересилання команди в інтерпретатор, одержання команди, формування команди й виконання команди дозволяють забезпечити інтеграцію ЕС і АІС.

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

Розроблені й випробувані бази знань для лабораторних робіт з дисциплін “Об'єктно-орієнтоване програмування”, “Системне програмування та операційні системи” та “Основи проектування систем штучного інтелекту”. Алгоритми виконання робіт містять у собі всі базові алгоритмічні структури.

Експерименти були проведені за участю студентів трьох курсів, загальною чисельністю 185 чоловік. Із числа студентів, що навчаються на кожному курсі, були сформовані дві рівні по чисельності й успішності групи. Формування груп проводилося на основі попередньо розрахованого середньозваженого бала успішності по спеціальних дисциплінах. За допомогою критерію однорідності було доведено, що перед проведенням експерименту вони статистично нерозрізнені по успішності (на рівні вірогідності 90% за крітерієм Вілкоксона-Манна-Уітні).

Кожної із груп була дані однакові задачі. Перша група вирішувала задачі без використання розробленої ЕС, друга - з використанням. Результати роботи оцінювалися по якісній шкалі “задовільно” (3), “добре” (4), “відмінно” (5). Приклад гістограми розподілу оцінок у експериментальній та контрольній групах одного курсу наведено на рис. 5. Гістограми для інших двох курсів наведено у роботі.



Рис. 5. Гістограма розподілу оцінок в експерименті.

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

За результатами експериментів була обчислена медіана варіаційного ряду оцінок, які отримали студенти. Було встановлено, що відбулося статистично значиме зрушення (на рівні вірогідності 90% за критерієм Вілкоксона-Манна-Уітні) медіани убік поліпшення: у групи без використання ЕС він склав 3 бали, у групи з її використанням - 4 бали. Тому що до експерименту групи були статистично однорідні по успішності, то дана зміна пов'язана з поліпшенням результатів роботи в АІС із використанням ЕС.

ВИсновки

У дисертації розроблена й науково обґрунтована нова система підтримки користувача, що є автоматизованою й базується на застосуванні перетворень структурних схем алгебри Дейкстри та моделі подання знань у вигляді сценаріїв.

У ході виконання даної дисертаційної роботи отримані наступні результати:

1. Проаналізовано основні типи інтерфейсів користувача й засоби підтримки при роботі з ними. Зроблено вивід про необхідність подальшого вдосконалення засобів підтримки користувача з метою надання можливості керування взаємодією, що дозволить істотно спростити роботу з АІС звичайних і спеціальних груп користувачів. Система “користувач-АІС” охарактеризована як нетрадиційний об'єкт управління, тому запропоновано використати ситуаційне управління й плануючу експертну систему.

2. Розроблено абстрактну схему управління взаємодією користувача й АІС. Уведено три режими управління взаємодією й показано, що вони дозволяють реалізувати навчання й підтримку користувача в АІС на всіх етапах рішення задачі.

3. З використанням запропонованих операцій і предикатів уведена алгоритмічна алгебра сценаріїв, що моделює дії користувача в АІС. Доведено твердження про те, що за допомогою даної алгебри можна представити будь-який алгоритм взаємодії користувача й АІС. Сформульовано співвідношення, що встановлюють зв'язок між розробленою алгеброю й алгеброю Дейкстри.

4. Розроблено формальне подання структурних схем алгебри сценаріїв у вигляді графа , що дозволяє формалізувати знання про структуру задач в АІС.

5. Розроблено способи фіксації дій користувача при рішенні задач в АІС у термінах даного дерева. Розроблено способи планування на дереві задач.

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

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

8. Показано, що застосування розроблених підходів дозволяє спростити роботу користувача з АІС, а також поліпшити результати навчання роботі в АІС. Твердження доведене на рівні вірогідності 90% за критерієм Вілкоксона-Манна-Уітні.

9. Розроблені методи, алгоритми й системи були впроваджені в навчальний процес ОНПУ в дисциплінах “Об'єктно-орієнтоване програмування”, “Основи проектування систем штучного інтелекту”, “Теорія алгоритмів” і дипломному проектуванні.

СПИСОК ОПУБЛІКОВАНИХ праць ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Рувинская В.М. Пригожев А.С. Средства построения звукового интерфейса для незрячих пользователей ПК // Проблемы программирования. - 2003. - № 4. - с. 100-106.

2. Рувинская В.М. Пригожев А.С. Построение подсистемы помощи пользователю ПК с использованием сценариев. // Искусственный интеллект. - 2004. - № 3.- с. 371-378.

3. Рувинская В.М., Пригожев А.С. Разработка планирующей экспертной системы для поддержки работы пользователя с программной системой //Вестник ХГТУ.- 2005. - №3 . - с. 133 - 137.

4. Пригожев А.С. Реализация решателя и базы знаний экспертной системы для планирования действий пользователя при разработке программ// Радиоэлектроника и информатика. - 2005. - № 4. - с.110 - 116.

5. Пригожев А.С. Информационная технология помощи пользователю // Холодильная техника и технология. - 2007. - № 2. - с. 98 - 101.

6. Пригожев А.С. Особенности разработки и применения планирующей экспертной системы для обучения // Искусственный интеллект.-2005. - № 3. - с. 529 - 540.

7. Рувинская В.М., Пригожев А.С. Методы искусственного интеллекта для обучения // Труды Одесского политехнического университета. - 2005.- спецвыпуск. - с.35 - 39.