Кромеэтих данных для математической модели необходимо наличие еще некоторыхдополнительных данных, которые могут быть получены после анализа входнойинформации программным путем.
2.3.3. РАЗРАБОТКА ИНФОРМАЦИОННОГООБЕСПЕЧЕНИЯ ЗАДАЧИ
Произведеманализ исходной информации с целью определения состава и структуры информациидля последующей формализации и построения информационно-логической моделиданных (ИЛМ). Приведенная выше математическая модель, а также дополнительныесведения из описания предметной области позволяют определить роль реквизитов вовзаимосвязанной информации, содержащейся в документе. На основе такого анализаустановим функциональные зависимости реквизитов в соответствии с рекомендациямии требованиями нормализации данных, после чего проведем саму нормализацию. Цельнормализации состоит в том, чтобы уменьшить (но необязательно устранить)избыточность данных. Однако иногда некоторая избыточность данных создаетсянамеренно, чтобы повысить эффективность работы программы. Дадим определениетрех форм нормализации базы данных.
Таблицанаходится в первой нормальной форме (1NF), если она имеет первичный ключ, все атрибутыпредставляют собой простые типы данных и отсутствуют повторяющиеся атрибуты.Чтобы соответствовать 1NF, домены атрибутов должны быть атомарными значениями и не должно бытьповторяющихся групп атрибутов. Все повторяющиеся группы атрибутов должны бытьперенесены в новую таблицу.
Таблицанаходится во второй нормальной форме (2NF) тогда, когда онанаходится в первой нормальной форме и каждыйнеключевой атрибут полностью функционально зависит от первичного ключа (т.е. в2NF каждый неключевой атрибут должен полностью зависеть от полейпервичного ключа).
Таблицанаходится в третьей нормальной форме (3NF), если она находится в2NF и не содержит транзитивных зависимостей.Транзитивные зависимости – это функциональные зависимости между неключевымиатрибутами. Любой неключевой атрибут, который функционально зависит от другогонеключевого атрибута той же таблицы, создает транзитивную зависимость и долженбыть перемещен в другую таблицу.
Получающиесяфункциональные зависимости довольно тривиальны и очевидно вытекают изматематической модели, поэтому в дальнейшем описании они не приводятся. Также вдальнейшем изложении опускаются промежуточные степени нормализации. Поэтомуприведем лишь окончательную инфологическую модель базы данных (см. рис. 1.).
Рис.1. Инфологическая модель базы данных задачи составлениярасписания занятий
2.3.4. ОСОБЕННОСТИ ФОРМИРОВАНИЯ ОГРАНИЧЕНИЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ СОСТАВЛЕНИЯРАСПИСАНИЯ
Составление ограничений (1) – (7) математической моделизадачи составления расписания является достаточно тривиальной задачей, решаемойс помощью несложных SQL – запросови не требующей предварительного анализа входной информации. Поэтому подробнеелишь остановимся на ограничениях вида (8).
Заметим, что в математической модели системы читаемый предмет“привязывается” не к определенной аудитории проведения, а к некоторомумножеству аудиторий. Расстановка конкретных номеров аудиторий производится ужепосле решения поставленной задачи. Ограничения вида (8) имеют смысл толькотогда, когда множества аудиторий пересекаются. В математической модели системыпредлагается учитывать все уникальные пересекающиеся пары в виде ограничений.Количество этих пересечений может быть велико, что может привести к большомучислу дополнительных ограничений, отрицательно влияющих на скорость работыалгоритмов оптимизации. Однако можно существенно уменьшить количестводополнительных ограничений.
Рассмотрим случай линейного расположения пересекающихсямножеств (см. рис. 2.).
Рис.2. Линейно пересекающиесямножества 
В случае такого расположения множеств аудиторий дляпроведения занятий общее число ограничений вида (8) будет n-1, где n – количество множеств. Описанное выше расположениепересекающихся множеств может быть названо линейным, так как при этом n пересекающихся множеств расположены как бы в линию. Можно рассмотреть случай, когдамножества пересекают друг друга произвольным образом (см .рис. 3.).
Рис.3. Произвольнопересекающиеся множества 
Число ограничений вида (8) в этом случае можно уменьшить,проведя формирование этих ограничений по аналогии со случаем линейногорасположения множеств. Для этого необходимо предположить, что, например,множества B и D, пересекающиеся с A, являются одним множеством,определить область пересечения такого множества с множеством A, после чего провести те же самыедействия с получившейся областью пересечения.
Подробнее об этом см. [2], стр. 210.
2.4. Результаты работы программы При практической реализации системыособое внимание было уделено задаче написания “ядра” системы – методам решениязадачи и процедурам формирования ограничений. Поскольку не ставилось задачинаписать полнофункциональный коммерческий продукт, интерфейсная часть быланаписана для целей тестирования ядра и определения границ применимостиалгоритмов, поэтому включает в себя минимум функциональных возможностей и несодержит модулей предобработки входных данных.
Ядро системы и интерфейсная часть былинаписаны на Delphi 6.0.Методы решения и алгоритмы формирования ограничений написаны с использованиемобъектно-ориентированнных технологий, что позволит в будущем легкоинкапсулировать их в дальнейшие модификации системы, не нарушая целостностивзаимодействия различных алгоритмов. Текст объектов методов решения задачиприведен в приложении 2. База данных была реализована на СУБД Oracle 8i, запросы к ней осуществляются на языке PL/SQL.
