Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления
Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления
ИНСТИТУТ
РАДИОТЕХНИКИ,
ЭЛЕКТРОНИКИ
И АВТОМАТИКИ
(ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ)
Факультет
Кибернетики
Кафедра
Интеллектуальных
технологий
и систем (ИТС)
Курсовая
работа
Тема: Решение
творческих
задач методом
блочных альтернативных
сетей: объектно-ориентированные
представления.
Студенты:
Группа: АИ-1-91
Руководитель:
Нечаев В. В.
Москва 1996 г.
Задание
на курсовое
проектирование
по дисциплине
«Основы теории
творческой
деятельности»
студентам
группы АИ-1-91.
Тема
исследования
: решение творческих
задач методом
блочных альтернативных
сетей для
объектно-ориентированных
систем.
Исходные
данные:
Теория
концептуального
метамоделирования.
Методы
решения системных
задач.
Список
литературы.
Методические
указания к
курсовому
проектированию.
Конспект
лекций.
Тема
дипломного
проекта.
Перечень
вопросов, подлежащих
разработке:
Описание
проблемной
области задач,
выносимой на
дипломный
проект.
Проведение
анализа конкретной
задачи, выносимой
на курсовую
работу.
Выбор
и обоснование
метода решения
задачи.
Анализ
и описание
метода решения
задачи.
Описание
решения задачи
на основе
выбранного
метода.
Календарный
план-график
работы:
Получение
задания 21.04.96.
Анализ
задания, подбор
и изучение
литературы
25.04.96.
Разработка
концептуальной
метамодели
объекта моделирования
09.05.96.
Оформление
пояснительной
записки и сдача
проекта на
проверку 21.05.96.
Защита
курсового
проекта 24.05.96.
Руководитель
…………..(Нечаев
В. В.)
(подп.)
Исполнители
(подп.)
Содержание
Введение
Постановка
задачи
Концептуальное
метамодельное
представление
задачи
Форма
организации
учебного процесса
и базовые
компоненты
предметной
области
Аудиторный
фонд
Контингент
учащихся
Профессорско-преподавательский
состав
Комбинированный
учебный план
Расписание
занятий
Методология
решения задачи
2.1. Модель
представления
знаний для
проекта «Учебное
расписание»
2.1.1.
Объектно-ориентированная
модель представления
знаний
2.1.2 Блочная
альтернативная
сеть
2.1.2.1. Элементарный
блок альтернатив
2.1.2.2
Структура БАС
2.2. Методы
формирования
решения
2.2.1
Алгоритмы
навигации на
БАС
2.2.2. Маршруты
на БАС
2.2.3 Оценка
результатов
решения задачи
на БАС
Реализация
БАС на ОО системе
в проекте «Учебное
расписание»
3.1.
Структура
класса
3.2.
Правила представления
знаний
3.3. Фрагмент
решения задачи
«Формирование
учебного расписания»
3.3.1.Класс
«Учебный блок»
3.3.2.
Класс «Блок
занятия»
3.3.3.
Класс «Блоки
занятий»
Список
литературы
4
5
8
8
8
9
10
11
13
13
14
16
16
21
22
22
23
26
27
27
29
31
31
35
38
40
Формирование
расписания
занятий для
учебных заведений
представляет
собой сложную
задачу с большим
количеством
исходных данных
и генерируемых
решений. Проблема
создания
автоматизированных
инструментальных
средств, позволяющих
полноценно
решить данную
задачу, все еще
актуальна, т.к.
существующие
на данный момент
системы проектирования
расписания
не обладают
достаточной
степенью
эффективности.
Это объясняется
тем, что данные
программные
средства не
основываются
на методах
искусственного
интеллекта.
С развитием
интеллектуальных
информационных
технологий
и концепции
объектно-ориентированного
проектирования
систем появилась
возможность
более эффективно
решить рассматриваемую
задачу.
Для этого
необходимо
ее формализовать,
т.е. разбить на
подзадачи
и выделить
основные цели
решения:
1) выбор
методологии
решения задачи
на основе
искусственного
интеллекта;
2) определение
алгоритма
реализации
метода;
3) разработка
пакета программ,
реализующих
алгоритм.
Целью
работы является
описание модели
представления
знаний и методов
решения творческих
задач на примере
задачи формирования
расписания
на основе анализа
учебного плана,
дополненного
планом нагрузки
преподавателей
(форма 101).
В первом
разделе рассматривается
постановка
системной
задачи на основе
концептуального
метамодельного
представления.
Во втором
разделе представлена
методология
решения творческих
задач на блочных
альтернативных
сетях для
объектно-ориентированных
систем,
В третьем
разделе рассматривается
применение
выбранных
методов для
решения фрагмента
задачи, выносимой
на дипломное
проектирование.
Экономическая
эффективность
решения задачи
будет оценена
на основе методов
функционально-стоимостного
анализа
1. Постановка
задачи
1.1. Концептуальное
метамодельное
представление
задачи
Концептуальное
метамодельное
(КММ) представление
задачи определим
в виде кортежа:
Z
- определяет
цели "неудовлетворенной
потребности",
в результате
которой порождается
проблемная
ситуация;
С -
определяет
условия достижения
цели;
I - определяет
исходную информацию,
в зависимости
от которой
цель порождает
различные
решения (R).
В качестве
условий определим
следующий
необходимый
и достаточный
набор компонент:
- метод решения
(М);
- алгоритм (А);
- программу
(Р);
- оценку адекватности,
релевантности
(ад).
Кортеж целей
тогда запишется
в следующем
виде:
Z
= < М, А,
Р, ад>.
(1.2)
Исходная информация
включает в
себя данные
(D),
необходимые
для решения
задачи, и знания
(К) о
предметной
области задачи:
I
= ,
K>
(1.3)
С другой стороны
используемую
информацию
можно рассматривать
как совокупность
информации
о целях и условиях
задачи:
I*
= Z,
IM,
IA,
IP,
I>.
(1.4)
Адекватность
решения задачи
представим
как совокупность
показателей
качества и
эффективности:
ад = Г (Qw,
Ef).
(1.5)
Развитие задачи
(Тр) связано с
заполнением
задачной оболочки
в форме КММ
конкретными
сведениями,
определяемыми
решением задачи.
Как известно,
возможны следующие
постановки
задач:
1) Рутинная задача,
когда кортеж
(1.1) и (1.2) заданы
полностью
(ТP-РR).
2) Творческая
задача уровня
программы
(Тр-Рр), когда
задано все,
кроме программной
реализации
(Р) , и требуется
определить
Р, осуществляя
тем самым переход
к рутинной
задаче, и результат
(R).
3) Творческая
задача уровня
алгоритма
(ТР-РА), т.е.
неизвестен
алгоритм (А) и
его программная
реализация.
4) Творческая
задача уровня
метода решения
(Тр-Рм), когда
неизвестны
метод, алгоритм
и программа.
Схему решения
задачи в общем
виде представлена
на рис. 1.1, а логическая
схема решения
задачи в виде
схемы алгоритма
на рис. 1.2.
В качестве
базовых процедур
решения выделим
следующие
технологические
процедуры:
- генерации
решений;
- анализ полученных
решений;
- формирование
парадигмы
решений;
- упорядочение
альтернативных
решений ;
- выбор удовлетворительного
результата;
- оптимизация
предпочтительных
решений. Таким
образом, общая
процедура
решения задачи
формально
определяется
записью вида:
R = F:{(ZR/C
(R/IR)},
(1.6)
т. е. решение
определяется,
исходя из заданных
целей и условий
достижения
целей.
Системная
задача Р
PM
PA
PP
PR
Р
Исходная
задача
Задача
метода
Задача
алгоритма
Задача
программы
Задача
результата
нет
нет
нет
нет
нет
нет
нет
нет
да
да
да
да
да
да
да
да
ис. 1.1 Схема
решения системной
задачи
Рис.
1.2 Логическая
схема (алгоритм)
решения системной
задачи
1.2. Форма организации
учебного процесса
и базовые компоненты
предметной
области
В соответствии
с принятой
системой правил
организации
учебного
процесса каждый
факультет
(кафедра) ВУЗа
самостоятельно
формирует
себе расписание
занятий, согласовывая
с другими
факультетами
(кафедрами)
вопросы совместного
использования
аудиторного
фонда и труда
профессорско-преподавательского
состава.
Ниже рассмотрены
базовые объекты,
входящие в
систему организации
учебного процесса.
1.2.1. Аудиторный
фонд
Аудиторный
фонд (АФ) - каталог
помещений
ВУЗа, в которых
планируется
проведение
занятий.
Каждое помещение
(аудитория)
характеризуется
двумя основными
параметрами:
АФ = <ФНА, ЕВ>,
(1.7)
где ;
ФНА - определяет
функциональное
(занятийное)
назначение
аудитории;
ЕВ - характеризует
единовременную
вместимость,
определяющую
набор требований
экологического
и эргономического
характера.
По своему
функциональному
назначению
различают три
типа помещений:
- аудитории
для проведения
лекций;
- аудитории
для проведения
практических
занятий (семинаров);
- аудитории
для проведения
лабораторных
занятий.
1.2.2. Контингент
учащихся
Контингент
учащихся (КУ)
- иерархическая
древовидная
структура
организации
учебных формирований
(УФ) (рис. 1.3). В целях
минимизировать
возможность
потери общности
данных о КУ
определим
следующие
базовые единицы:
- курс;
- поток;
- временный
поток;
- учебная группа.
Курс - условное
обозначение
вершины дерева,
в которое
включаются
всё учебные
группы, сформированные
в определенный
год.
Поток - объединение
одной или нескольких
учебных групп
одного года
формирования.
Временный
поток - поток,
сформированный
на период, равный
одному семестру,
или сформированный
для проведения
специальных
учебных занятий.
Учебная группа
- самостоятельная
неделимая
учебная формация.
К
урс
Поток 1
Поток 1.1
Учебная группа
I.I.I
Поток 1.2
Учебная группа
1.2.1
Учебная группа
1.2.2
…………………………………
Рис. 1.3. Организация
КУ
1.2.3 Профессорско-преподавательский
состав и дисциплины
Профессорско-преподавательский
состав (ППС)
объединяет
людей (преподавателей),
ответственных
за проведение
занятий.
Преподавателя
характеризуют
две составляющие:
ППС = <З, ТНД>,
(1.8)
где
З - определяет
звание (должность)
преподавателя;
ТНД - определяет
тематическую
направленность
дисциплины
(Д), которую
"читает"
преподаватель:
Д <=> <ТНД>,
(1.9)
Должность
преподавателя
определяет
формальную
систему приоритетов:
- профессор;
- старший
преподаватель;
- преподаватель;
- совместитель;
- аспирант.
ТНД может иметь
также и сложную
структуру,
объединяя в
себе набор
дисциплин с
разными тематиками:
ТНД*= {ТНД1, ... ,
ТНДN}.
(1.10)
1.2.4. Комбинированный
учебный план
Комбинированный
учебный план
(КУП) - таблица,
в которой каждому
учебному
формированию
поставлены
в соответствие
определенные
дисциплины
с указанием
учебной нагрузки,
выраженной
в академических
часах в неделю
для каждого
вида занятия,
и преподавателя,
ответственного
за проведение
занятия.
По значению
ТНД дисциплины
выбирается
преподаватель.
Параметры
КЧЛК, КЧЛР, КЧПР
формируют
абстрактное
понятие количество
часов нагрузки
(КЧН).
1.2.5. Расписание
занятий
Расписание
занятий (РЭ) -
таблица, в которой
указаны место
и время проведения
занятий.
При формировании
таблицы РЗ
используются
практически
все данные,
рассматриваемые
при организации
учебного процесса.
Формальная
постановка
задачи составления
расписания
представлена
на рис. 1.4.
На рис. 1.5. отображена
система отношений
между объектами
проекта "Учебное
расписание".
Учебные формирования
Кафедра
П
Р
Е
П
О
Д
А
В
А
Т
Е
Л
И
Д
И
С
Ц
И
П
Л
И
Н
Ы
Комбинированный
учебный план
План
нагрузки
Учебный
план
Расписание
Рис 1.4 Постановка
исходной задачи
составления
расписания
Рис. 1.4 Ключевые
абстракции,
характеризующие
словарь предметной
области
2. Методология
решения задачи
2.1 Модель представления
знаний для
проекта «Учебное
расписание»
При обсуждении
задачи составления
(планированию)
расписания
важно выделить
требования,
предъявляемые
к знаниям. Знания,
необходимые
для выполнения
функций планирования
расписания,
должны быть
полными, хорошо
определенными
и тщательно
структурированными.
Методы для
представления
и использования
этих знаний
должны иметь
результатом
расписание,
достаточно
эффективное
и гибкое. Среда,
для которой
создается
расписание
на базе искусственного
интеллекта,
должна демонстрировать
недетерминизм,
означая, что
возможен более
чем один допустимый
путь его составления.
Для решения
здесь требуются
рассуждения,
которые связаны
с объектами,
обладающими
гибкими (полиморфными)
характеристиками.
На
данном этапе
введем понятие
архитектуры
для обработки
и представления
знаний (АОЗ).
АОЗ имеет две
составляющих:
внутреннюю
и внешнюю. Внешняя
составляющая
напрямую связана
с моделью
представления
знаний, а внутренняя
отождествляется
с конкретной
аппаратной
(,или программной,)
архитектурой
электронной
вычислительной
машины (ЭВМ),
на платформе
которой создается
программный
продукт. Естественно,
что указанные
составляющие
должны иметь
как можно более
простые связи,
т.е. каждому
семантическому
элементу модели
представления
знаний должна
быть сопоставлена
естественная
аппаратная
(программная)
реализация.
В ЭВМ "неймановского
типа" для того,
чтобы выполнить
некоторую
обработку
данных, необходимо
написать алгоритм
обработки в
виде программы
и ввести ее в
компьютер. Если
попытаться
подобным методом
разработать
систему обработки
знаний, то неизбежно
возникают
две проблемы.
Первая связана
со слиянием
знаний с механизмом
логического
вывода. Она
состоит в том,
что знания об
объекте и механизм
логического
вывода, использующий
эти знания, не
должны отличаться
друг от друга,
т.е. их следует
представлять
в виде цельной
процедуры.
Вторая проблема
обуславливается
сложностью
обновления
знаний, когда
пополнение,
уничтожение
или изменение
знаний, ломающихся
объекта, означает
изменение
программы, и
трудно точно
определить,
до какой части
программы
распространяется
это влияние.
Эти проблемы
можно разрешить,
если разработать
систему с модульным
представлением
знаний.
Наиболее часто
используемые
модели представления
знаний для
решения задач
искусственного
интеллекта
(ИИ) приведены
в табл. 1.1.
Таблица 1.1
Описательные
формализмы
Иерархия
Наследование
Модульность
Семантические
сети
+
-
-
Фреймовая
модель
+
+
-
Продукционная
модель
+
-
+
ОО
модель
+
+
+
Для проекта
"Учебное расписание"
был выбран
объектно-ориентированный
(ОО) формализм
представления
знаний, который
можно трактовать
как уточнение
формализма
фреймов (в формализме
фреймов не
делается различия
между видом
отношений
класс/подкласс
и видом отношений
класс/конкретный
экземпляр, в
то время как
в ОО формализме
эти два вида
отношений
являются
ортогональными).
ОО модель знаний
также выгодна
с точки зрения
процесса
представления
знаний, который
включает в себя
следующие
этапы:
1. Идентификация
классов и объектов
данного уровня
абстракции;
2. Идентификация
семантики
классов и объектов;
3. Идентификация
связей между
классами и
объектами;
4. Идентификация
классов и объектов
(программная
реализация).
2.1.1.
Объектно-ориентированная
модель представления
знаний
Концептуальной
основой
объектно-ориентированного
стиля представления
систем является
подход, которому
соответствуют
четыре главных
элемента:
- абстрагирование;
- ограничение
доступа;
- модульность;
- иерархия.
Под абстрагированием
понимают выделение
существенных
характеристик
(атрибутов)
объектов (определение
абстрактного
типа данных),
которые отличают
его от всех
других видов
объектов и,
таким образом,
четко определяют
особенности
данного объекта
с точки зрения
дальнейшего
рассмотрения
и анализа.
На
данном этапе
введем понятие
инкапсуляции
как объединения
атрибутов
объектов и
функций управления
объектами в
единую описательную
структуру -
класс. Таким
образом, понятие
класс определяет
множество
объектов, связанных
общностью
структуры и
поведения.
Следует разделять
внутреннее
и внешнее проявление
класса. Интерфейсная
часть описания
класса соответствует
его внешнему
проявлению,
подчеркивает
его абстрактность,
но скрывает
его структуру
и особенности
поведения.
Реализация
класса составляет
его внутреннее
проявление
и определяет
особенности
поведения,
т.е. в данной
части раскрывается
реализация
тех операций,
которые перечислены
в интерфейсной
части описания.
Интерфейсная
часть класса
состоит из
перечня действий,
который допускает
описание, других
классов, констант,
переменных
и других особенностей,
необходимых
для полного
определения
данной абстракции.
Интерфейсная
часть описания
класса разделена
на три составные
части:
- общедоступная;
- защищенная;
- обособленная
(скрытая).
К = <А, Ф>,
(2.1)
где
А – атрибуты
класса;
Ф – функции
(методы) класса.
В
свою очередь:
А
=<ОА,
ЗА,
СА>,
(2.2),
а
Ф = <ОФ, ЗФ,
ОФ>,
(2.3)
где
О[А,Ф] - общедоступные
элементы класса;
З[А,Ф] - защищенные
элементы класса;
С[А,Ф] - скрытые
элементы класса.
В общедоступной
части интерфейса
класса декларируются
определения,
"видимые" для
всех объектов-пользователей
данного класса.
В защищенной
части интерфейса
класса даются
определения,
"видимые"
только для
объектов,
относящихся
к подклассам
данного класса.
В обособленной
части интерфейса
класса декларируются
определения,
"скрытые" для
объектов всех
других классов.
Созданию абстракции
объекта предшествуют
решения о способе
ее реализации.
Выбранный
способ реализации
должен быть
скрыт и защищен
для большинства
объектов,
обращающихся
к данной абстракции.
Ограничение
доступа определяет
процесс защиты
отдельных
элементов
объекта, не
затрагивающий
существенных
характеристик
объекта как
целого.
Модульность
является свойством
системы, которое
связано с
возможностью
декомпозиции
ее на ряд тесно
связанных
модулей (областей).
Иерархия реализует
механизм отношений
между классами
объектов.
Отношения
между классами
могут быть
комбинацией
следующих
типов иерархий;
- наследование;
- использование;
- метаклассы.
Наследование
– отношение
между классами,
когда один
класс повторяет
(включает в
себя) структуру
и поведение
другого (простое
наследование)
или других
(множественное
наследование)
классов. Класс,
структура и
поведение
которого
наследуются,
называются
суперклассом
(класс-предок),
а производный
от суперкласса
класс навивается
подклассом
(класс-наследник).
Очевидно, что
лучшим способом
сохранения
единства подхода
к проекту и
решения проблемы
избыточности
описания, является
создание для
каждого вида
данных отдельного
класса, что
позволит защитить
данные в каждом
классе и увязать
их с выполняемыми
операциями.
Отношение
использования
связано с
объявлением
общности
(дружественности)
классов, которая
означает возможность
доступа к
защищенным
элементам
класса объектам
других классов.
Метакласс
(абстрактный
класс) является
классом, объекты
которого сами
являются классами.