правил (знаний).
Как минимум кортеж ФОБП включает в себя:
ФОБП = , (3.4)
где:
ФВА - функция выбора альтернативы;
ФДП - метод для добавления правила в базу знаний;
ФУП - метод для удаления правила из базы знаний;
ФРП – метод для редактирования правила в базе знаний.
Функция выбора альтернативы определяет механизмы построения синтаксиса правила, выборки из множества и оценки результатов на основе критериевg-адекватности.
Функции добавления/удаления/редактирования правил содержат в своем теле два основных блока: блок добавления/удаления/редактирования правила и блок добавления/удаления/редактирования альтернативы.
3.2.Правила представления знаний
Правила, представленные в ФБП делятся на две основные группы:
декларативные и продукционные.
Декларативные правила (ДП) определяют в базе знаний множество фактов. Факт в данном случае однозначно отождествляется с конкретным объектом-альтернативой абстрактного типа данных. Факт в зависимости от количества атрибутов объекта класса может иметь простую или сложную (составную) структуру.
Продукционные правила (правила ЕСЛИ-ТО) позволяют явным образом задавать критерии необходимости и достаточности количества входных параметров для идентификации объекта-альтернативы. Также в теле правил данного типа могут содержаться записи математических законов описания множества объектов.
Вне зависимости от типа, правила имеют два вида представления: текстовый и двоичный. Возможные связи между текстовым и двоичным представлением правил в базе знаний представлены на рис. 3.1.
Одинарной линией на рис. 3.1. показана связь типа «один к одному», а двойной – связь типа «один к многим».
Связь типа «один к многим» реализуется правилом, имеющим в своем теле следующий функциональный элемент:
FOR = , (3.5)
где
В - определяет начальное значение счетчика;
Е - определяет конечное значение счетчика;
S - определяет шаг приращения значения счетчика;
F(С, Ao1, …, Aoi, …, Aon) - определяет математическую базу для генерирования объекта-альтернативы;
С - текущее значение счетчика;
Aoi- атрибут объекта;
О – определяет режим отображения объекта класса: О=base – отображение в файл БД, О=memory – отображение в оперативную память.
Рис. 3.1. Связи между текстовым и двоичным представлением правил
При 0=base объемы-альтернативы собираются в файл базы данных (DBF-файл), где хранится в упакованной виде. Для файлов подобного типа определяются стандартные операции индексирования и фильтрации записей, что упрощает и убыстряет механизм поиска и выборки информации из БД.
3.3. Фрагмент решения задачи "Формирование учебного расписания"
Формальное представление алгоритма решения задачи формирования расписания отображено на рио.З.2.
Из рисунка видно, что базовым элементом в системе составления расписания является учебный блок занятий (класс "Учебный блок" на рис. 1.4.).
3.3.1. Класс "Учебный блок"
Блок занятий необходимо рассматривать как совокупность пар (занятий), следующих друг за другом и распределенных по неделям семестра между различными учебными формированиями.
Структура блока занятий представлена в виде матрицы на рис. 3.3.
Учебный блок составляют две компоненты:
- количество часов в блоке (КЧБ) определяет количество часов, которое блок занимает в сетке расписания одного учебного дня (одна строка матрицы соответствует двум часам занятий);
- деление блока (Д) распределяет занятие по неделям семестра.
Значения КЧБ и Д рассчитываются на основании данных, из комбинированного учебного плана. Связующим звеном здесь являемся абстракция "Количество часов нагрузки" (КЧН), которая объединяет три класса:
- количество часов лекционных занятий в неделю (КЧЛК);
- количество часов лабораторных занятий в неделю (КЧЛР);
- количество часов практических занятий в неделю (КЧПР).
Рис. 3.2 Общая схема решения задачи сопоставления расписания занятий методами БАС на ООС на основании продукционной модели
КЧБ
Д
Рис. 3.3. Структура блока занятий
Обозначим количество недель в семестре как КНС. Тогда, суммарное количество часов занятий эа семестр (Sч) определяется произведением КНС и КЧН:
Sч = КНС*КЧН, (3.6)
или
Sч = (КНС/Д)*КЧБ. (3.7)
Из чего следует:
КЧН = КЧБ/Д. (3.8)
Декларативные правила, входящие в классы КЧЛК, КЧЛР и КЧПР
описывают следующие наборы фактов:
КЧЛК = {0, 1.0, 1.5, 2.0}, (3.9)
КЧЛР = {0, 1.0, 2.0}, (3.10)
КЧПР = {О, 1.0, 2.0}, (3.11)
Объединяя множества в мета-класс, получим:
КЧН = {0, 1.0, 1.5, 2.03}. (3.12)
Используя формулу 3.8, определим область значений объектов-экземпляров класса КЧБ и класса Д:
КЧБ = {2, 4, 6}, (3.13)
Д = {2, 3, 4}, (3.14)
Класс «Учебный блок» является наследником класса «Блок занятия».
3.3.2. Класс «Блок занятия»
Столбец матрицы, представленной на рис.3.3., определяет часть семестра, которую назовём долей. Доля может быть занята (занятие проводится – столбец матрицы закрашен) или свободна.
Свободные доли описывают свободные часы занятий в неделю (КЧС).
Декларативное правило генерации параметра КЧС имеет вид:
ПРАВИЛО 1.
блок.КЧС = FOR (1, блок.Д-1, RETURN(C), base).
Объединяя КЧС с данными класса "Учебный блок", сформируем класс "Блок занятия".. Количество свободных (КСД) и занятых (КЗД) долей в блоке занятия определим через его параметры:
КСД = КЧС/КЧН. (3.15)
Используя формулу 3.8, получим;
КСД = Д * (КЧС / КЧБ). (3.16)
Очевидно, что:
КСД + КЗД = Д. (3.17)
Следовательно:
КЗД = Д * (1 - КЧС/КЧБ). (3.18)
На рис. 3.4. приведена структура БАС с алгоритмами навигации для класса "Блок занятий". В результате работы алгоритма, ФВА класса "Блок занятий" был получен набор решений, образующих блок альтернатив, представленный на рис. 3.5.
Рис. 3.4. Схема БАС формирования объекта «Блок занятий»
Рис. 3.5. ВАС формирования объекта класса «Блоки занятий»
3.3.3. Класс «Блоки занятий».
Уравнения 3.16 и 3.18 необходимы для понятия совместимости блоков занятий.
Два блока БIи Б2 совместимы, если:
KЧH1 = КЧН2, КЧБ1 = КЧБ2 и КЗД1 <= КСД2 (КЗД2 <= КСД1), (3.19)
Понятие совместимости блоков используется в правилах слияния нескольких блоков в один объект класса "Блоки занятий":
ПРАВИЛО 1.
ЕСЛИ стратегия.тип = общая
И блок(&А).КЧН = блок(&Б).КЧН
И блок (&A).КЧБ = блок (&Б).КЧБ
И блок(&А).КЗД <= блок (&Б).КОД ТО блок(&С) = блок(&А) U блок(&Б).
ПРАВИЛО 2.
ЕСЛИ стратегия.тип = общая
B блок(&А).КЧН == блок(&Б) .КЧН
И блок (&A). КЧБ = блок(&Б). КЧБ
И блок(&А). КCД >= блок(&Б). КЗД ТО блок(&C) = блок(&A) U блоков(&Б).
Класс "Блоки занятий" объединяет абстрактные потоки, которые характеризуются параметром "Количество групп в потоке" (КГ), и оптимальную совокупность блоков.
Схема алгоритма генерации объектов класса "Блоки занятий" отображена на рис. 3.6.
В схеме .алгоритма использованы следующие сокращения:
Ptr - указатель на текущий объект в описке альтернативных блоков занятий;
AltList - список блоков занятий, определяющих в совокупности одну альтернативу для текущего количества групп;
Len(AltList) - длина списка AltList.
ДА
НЕТ
ДА
НЕТ
ДА
НЕТ
ДА
ДА
НЕТ
Рис 3.6. Схема алгоритма генерации объектов класса "Блоки занятий"
Системная задача Рd
IM
IA
IP
IR
PM
PA
PP
PR
Rd
Исходная задача
Задача метода
Задача алгоритма
Задача программы
Задача результата
Конец
М=?
A=?
P=?
R=?
M=ЎM
A=ЎA
P=ЎP
R=ЎR
нет
нет
нет
нет
нет
нет
нет
нет
да
да
да
да
да
да
да
да
Кафедра
П
Р
Е
П
О
Д
А
В
А
Т
Е
Л
И
Д
И
С
Ц
И
П
Л
И
Н
Ы
П1
Пi
ПN
Д1
Дj
ДМ
Ф1
Фк
ФК
План нагрузки
Учебный план
Расписание
Комбинированный учебный план
Учебные формирования
РАСПИСАНИЕ
Количество групп
в потоке
Приоритеты
преподавателей
Аудитория
Блоки занятий
Блок занятия
Деление
КЧС
КЧБ
КЧН
КЧЛР
КЧЛК
КЧПР
Учебный блок
Функциональное назначение
Назначение
Тематическая направленность
Временной поток
Преподаватель
Дисциплина
Учебное формирование
Комбинированный УП (форма 101)
Семестр
Количество недель
Поток
Группа
Решение - R
А1
Аn
АN
an1
anо
anmn
Аn
an1
anо
anm
an1
anо
anm
якорь
R
T
вход
выход
Аn
Тn
ФБА
Rn
АnУ
АnХ
A*1
R1
Т1
ТN
RN
A*N
БАn
AN
A*n
БАN
An
Rn
Тn
БА1
A1
Тn
ТN
R1
Т1
An
A*n
AN
A*N
A*1
Rn
БАn
RN
БАN
БА1
