| E-mail: DavidovSV@yandex.ru |
| Сообщество исследователей РАСПИСАНИЯ |
| Compiler & Schedule Builder sources |
| [home] |
All rights reserved by Давыдов С.В. (c) 1999
При пассивном участии: Салоп Ю.
ВВЕДЕНИЕ
ФОРМУЛИРОВКИ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЙ
Общая формулировка задачи составления расписаний
Формулировка задачи составления расписаний в применении к расписанию учебных занятий
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
Математическая модель
Особенности практической реализации модели системы
Реляционный подход
Иерархический подход
Сетевой подход
ОРГАНИЗАЦИЯ ХРАНЕНИЯ ИНФОРМАЦИИ
Организация и хранение входной информации
Формат текстового файла для входных данных
Формат двоичного файла для входных данных
Организация и хранение выходной информации
Особенность физического хранения трехмерной матрицы
Организация работы с трехмерной матрицей
АЛГОРИТМ ПРОЦЕДУРЫ ПОСТРОЕНИЯ РАСПРЕДЕЛЕНИЯ
Алгоритм построения расписания
Сложность алгоритма
ОПТИМАЛЬНОСТЬ РЕШЕНИЯ
Выбор критерия оптимальности
Оптимальность построения распределения
Критерий оптимальности в практической реализации
ОПИСАНИЕ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ
Описание практической реализации
Визуальный редактор исходных данных
Компилятор иерархической модели данных
Генератор расписания
Cравнительная оценка практической реализации с имеющимися аналогами
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ. ГРАММАТИКА ЯЗЫКА ИЕРАРХИЧЕСКОЙ МОДЕЛИ ДАННЫХ
Грамматика
Нетерминальные символы
Терминальные символы
Предопределенные опции
Формат данных
Рис. 1. Иерархический способ организации данных Рис. 2. Сетевой способ организации данных Рис. 3. Порядок обработки информации Рис. 4. Структура текстового файла входных данных Рис. 5. Трехмерная матрица расределения Рис. 6. Слой трехмерной матрицы
В основе этой работы лежат элементы общей теории расписаний, описанные в книге Э.Г. Коффмана "Теория расписаний и вычислительные машины" [1]. Нашей целью было перенести общую теорию на практическую основу, для использования ее в автоматическом построении расписания учебных занятий учебного заведения.
В качестве основных предпосылок для этой работы было текущее состояние разработок на эту тему (в нашем распоряжении были две разработки на тему расписания занятий, которые описаны в "Сравнительная оценка..."), наш практический интерес к этому вопрсу, а также перспективы ее положительного завершения.
За время исследований, нами было рассмотрено несколько вариантов, и, в дальнейшем, некоторые из них были реализованы в виде отдельных элементов системы построения расписания.
Далее в отчете подробно рассмотрены все аспекты рассматриваемой нами проблемы.
В наиболее общей формулировке задача составления расписаний состоит в следующем. С помощью некоторого множества ресурсов или обслуживающих устройств должна быть выполнена накоторая фиксированная система заданий. Цель заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочивания заданий, оптимизирующий или стремящийся оптимизировать требуемую меру эффективности. В качестве основных мер эффективности изучаются длина расписания и среднее время пребывания заданий в системе. Модели этих задач являются детерминированными в том плане, что вся информация, на основе которой принимаются решения об упорядочивании, известны заранее.
Общая теория расписаний предполагает, что все обслуживающие устройства (или процессоры) не могут выполнять в данный момент времени более одного задания, что для расписания учебных занятий не является достаточным, если в качестве процессора при распределении заданий принять учебную аудиторию. Так как в некоторых случаях в одной аудитории могут проводится занятия с более чем одной группой одновременно, например общие лекции для нескольких потоков.
Поэтому, при переносе общей теории расписаний на расписание учебных занятий нами были сделаны следующий допущения:
В итоге, формулировка задачи составления расписания учебных занятий звучит следующим образом: "Для заданного набора учебных аудиторий (в данном случае под учебной аудиторией понимается широкий круг помещений, в которых проводятся учебные занятия (от компьютерной лаборатории до спортивного зала)) и заданного набора временных интервалов (т.е. по сути, уроков или учебных пар) построить такое распределение учебных занятий для всех объектов (учителя и учебные группы), для которого выбраный критерий оптимальности является наилучшим".
В качестве критерия оптимальности в данном случае могут выступать различные показатели, которые будут отдельно рассмотрены в "Выбор критерия..."
| G = {T1, T2, …, Tn} | - | множество заданий; |
| < | - | отношение частичного порядка, заданное на множестве заданий G; |
| [tijk] | - | трехмерная матрица размером n x m x p, представляющая распределение заданий по процессорам в заданный интервал времени; |
| P = {P1, P2,…,Pm} | - | множество процессоров; |
| R = {R1, R2,…,Rp} | - | множество временных интервалов; |
| <' | - | отношение частичного порядка, заданное на множестве R; |
| U | - | множество ограничений. |
Замечания:
На практике не очень удобно работать с информацией в том виде, в котором она определяется в математической модели. Поэтому нами было рассмотрено несколько способов организации исходных данных задачи построения расписания учебных занятий.
В качестве основных способов организации мы рассмотрели реляционный способ - данные в виде реляционных таблиц, организацию в виде иерархической структуры и сетевой способ организации с помощью сетевой базы данных. Далее мы рассмотрим их подробнее.
Реляционный способ организации данных был нами рассмотрен в первую очередь из-за его простоты и хорошо распространенных методов работы с ними.
В случае реляционного подхода входные данные представляются в виде базы данных, состоящей из набора таблиц, содержащих информацию об аудиториях, учебных группах, преподавателях, времени занятий и т.д.
В базу данных также могут входить и простейшие методы обработки данных в таблицах (это возможно при реализации клиент/сервер например с помощью СУБД MS SQL Server, Oracle, DB2, Interbase и др., которые имеют возможность определять для набора таблиц триггеры и хранимые процедуры).
Однако, приступив к разработке этого способа организации данных, мы сразу же натолкнулись на некоторые особенности, которые свели на нет все его достоинства. Главная из них - реляционный подход не подразумевает структуризации данных (на сегодняшний день имеются СУБД, которые реализуют объектно-ориентированный подход (например Jasmin или Informix Dynamic Server) и которые подразумевают удобную структуризацию, однако на момент разработки мы не имели возможность их использовать) (не более чем разбиение их на таблицы), что делает очень неудобной работу с разнородной информацией, кроме того, хранение ограничений в реляционной базе данных в том виде, в каком они фигурируют в системе, оказалось невозможным.
Следующим способом организации входных данных, который был нами рассмотрен, был иерархический способ.
В этом случае данные представляются в виде дерева (см. рис. 1). Иерархический способ организации данных оказался более удобным для работы, поэтому он был принят нами в качестве базового. Нами был разработан язык описания входных данных, который подробно описан в приложении.
Однако в процессе моделироания алгоритма построения распределения были обнаружены некоторые неудобства в работе с иерархической структурой данных. В процессе анализа мы выяснили причину их появления.
Данные в иерархической структуре связывались между собой по ключевым полям (примерно также, как организуется связь таблиц в реляционной базе данных), что приводило к их дублированию в различных узлах дерева. Например, при указании допустимых дисциплин для каждого преподавателя, связка осуществлялась путем указания для него списка названий дисциплин. Кроме этого оказалось неудобным получать доступ к полям объектов в глубине иерархической структуры (все это свойственно для любой иерархической базы данных, что объясняет причину отказа от их использования в СУБД. Впрочем это не единственная причина).
Всвязи с этим, нами был разработан сетевой вариант модели данных.
Для организации сетевой модели данных нами была незначительно пересмотрена структура дерева исходных данных, которое мы преобразовали в граф (см. рис. 2).
Первоначальная структура в общем случае сохранилась. Вместо связей с помощью ключевых значений полей были введены непосредственные связи между элементами с помощью горизонтальных (горизонтальная связка - связка между элементами в одном "уровне" графа, например, связь между преподавателями и дисциплинами) и вертикальных связок (вертикальная связка - связка между элементами на разных "уровнях" графа, например связь между дисциплинами и допустимыми аудиториями, в которых могут проводится занятия по этим дисциплинам).
Вся работа по построению расписанию ведется на основе сетевой модели, однако все исходные данные задаются в иерархической структуры. К сожалению у нас не было времени для "исключения" иерархической организации данных, поэтому на данный момент вся работа происходит по следующему принципу, условно изображенному на рис. 3:
Входная информация для построения расписания организуется в виде древовидной структуры, изображенной на рис. 4.
Указанная структура может хранить в двух видах: в виде текстового или в виде двоичного файла.
Информация в текстовом файле записана на языке Иерархической модели данных расписания, грамматика и описание которого приведены в приложении.
Все параметры полей, содержащих текстовую информацию, должны быть представлены в 866 кодировке MS DOS (это не принципиально, но необходимо для полной совместимости консольных и оконных пакетов построения распределения и редактирования исходных данных расписания).
Возможность использования двоичного файла была предусмотрена нами для более быстрого доступа к имеющимся данным. Восприятие программой текстового входного файла осуществляется путем его компиляции в удобоваримый для программы вид, что, не смотря на простоту языка (он задается LL(1) (подробнее о языках и грамматиках см. [3]) грамматикой, которая приводима к автоматной грамматике), занимает некоторое время, которое довольно сильно растягивается при большом размере входного файла.
Бинарный файл не нуждается в компиляции, поэтому его чтение и запись значительно быстрее, чем у текстового.
Однако у хранения информации в бинарном виде есть и существенный недостаток: непереносимость между системами с различной аппаратной основой (при чтении файла записанного компьютером на базе архитектуры Intel x86 сервером на RISC (например) платформе, этот файл будет воспринят неверно, из-за различной последовательности байт в слове и слов в двойном слове на этих двух архитектурах) (этого недостатка лишены данные, хранящиеся в текстовом файле) (это вполне реальная проблема, т.к. очевидно, что при работе мало кто захочет вводить входные данные в текстовом виде с терминала Unix-ого сервера, а моделировать распределение на маломощном PC).
Поэтому, нам представляется логичной следующая схема работы по построению расписаний с переносом данных и результатов между различными платформами (например в гетерогенной сети): информация хранится в текстовом виде, что делает возможным ее переносимость, а для внутреннего использования используются бинарные файлы, для более быстрой работы.
Под выходной информацией подразумевается информация, полученная после работы процедуры построения расписания (см Алгоритм...), т.е. та, которая хранится в трехмерной матрице (см. рис 5.).
Сама по себе трехмерная матрица является удобной только для визуального восприятия человеком, но не для непосредственной работы. Всвязи с этим, в системе предусмотрены процедуры для переноса расписания из трехмерной матрицы по слоям для каждого объекта, будь то преподаватель или учебная группа.
Для реальных расписаний характерной большое количество входных данных для построения распределения, в силу этого размеры матрицы при ее реализации в виде "как она есть", ее размеры могут достигать чудовищных значений (мы попытались прикинуть размеры матрицы хотя бы для нашего ВУЗа, и вот что у нас получилось: n - число заданий ~ 4000-9000, m - число процессоров ~ 400-500, p - число временных интервалов ~ 120. Итоговая максимальная размерность матрицы = 9000x500x120 = 540,000,000. Если в каждой ячейки хранить 4 байта, то получаем объем памяти необходимый, для матрицы ~ 2Г, а это уже слишком даже для хорошего и большого сервера).
Однако, матрица при реальных данных будет достаточно разреженной (например, для вечерних и дневных групп требуется различное количество задействованных ячеек матрицы), поэтому имеет смысл хранить ее в виде списка.
Еще одним моментом, связанным с хранением и работой с трехмерной матрицей, является возможность ее кластеризации - разделения матрицы на фрагменты, соответствующие, например, аудиториям, находящимся в различных корпусах (корпус = кластер (невольно напрашивается сравнение с организацией разделенных вычислений, когда несколько вычислительных модулей с (процессорами), объединяются в вычислительный кластер)). При кластеризации аудиторий, возможна последовательная или параллельная обработка различных кластеров трехмерной мтрицы, что значительно снизит требуемые вычислительные емкости и повысит скорость построения распределения (при параллельной обработке).
Основное достоинство введения в систему трехмерной матрицы, по нашему мнению, заключается в совершенно "прозрачной" реализации процедуры построения распределения. Достаточно только "посмотреть" сверху в низ на аудиторию в заданный интервал времени, сразу становится ясным, занята эта аудтория или нет. Или, для построения расписания для аудиторий с неединичной вместимостью, возможно ли "добавить" в аудиторию еще одну группу в заданый временной интервал. Все это значительно упрощает представление того, что нам требуется сделать, и упрощает процедуру построения расписания (к сожалению только на семантическом уровне).
Если сравнить выбранный нами способ построения и хранения распределения с другими разработками в этой области (см. Сравнительная оценка...), то по простоте и интуитивности наш способ превосходит реляционный способ реализации в других разработках.
Впрочем, здесь еще остались открытые вопросы.
В данном параграфе мы опишем алгоритм построения расписания на семантическом уровне, так, как его практическая реализация пока не доведена до конца.
К этому простому алгоритму можо добавить множество дополнений, связанных, например, с кластеризацией аудиторий или с некоторыми другими моментами практической реализации. Однако на данном этапе это не представляется нам возможным, из-за плохо исследованных свойств нашей системы.
Задача составления расписания для произвольного числа процессоров и заданий является NP-полной (NP-полной называется NP (Nondeterministically Polynomial) задача, к которой с полиномиальной временной сложностью сводится любая задача NP. Например задача комивояжера. Подробнее см. [1], [2]) и, как показано в [1, п.4.6.], в произвольном случае сложность ее решения не полиномиальна, т.е. она экспоненциальна.
Отсюда следует, что решать ее методом полного перебора (или перебора с возвратом) не эффективно. Поэтому, для реальной задачи необходимо использовать приближенные методы, один из которых описан в Критерий оптимальности...
В качестве критерия оптимальности можно выбрать различные характеристики системы. Например, в книге Э.Г. Коффмана [1] рассматривается средняя длина расписания.
Для нашего случая, сложно выбрать универсальный критерий оптимальности, так, как для каждого элемента системы этот критерий будет своим. Для учебных групп и преподавателей, например, это чисто субъективное представление об удобном расписании. Поэтому, в качестве такого более менее униерсального критерия можно взять плотность заполнения заданиями временных интервалов (в этом случае мы не учитываем субъективные мнения объектов распределения, а интересуемся исключительно собственным удобством - компактной загрузкой слоев трехмерной матрицы) и плотность заполнения заданиями аудиторий.
На рис. 6. показан пример заполнения.
Плотность заполнения заданиями временных ячеек для данного слоя будет равна 4/5 - 4 задания, 5 временных ячеек. А плотность заполнения заданиями аудиторий равна 4/3 - 4 задания, 3 занятых аудитории.
Из-за скудных практических результатов что-либо определенное сказать о данных критериях оптимальности невозможно.
Как это ни странно, в самой системе (заданной семеркой объектов) содержатся элементы, которые могут непосредственно влиять на оптимальность (в некоторых случаях даже на субъективную оптимальность) построенного распределения.
За счет выбора опреатора <' частичного упорядочивания, заданного на множестве временных интервалов, можно влиять на характер распределения заданий по процессорам. Это непосредственно следует из алгоритма постоения расписания.
По ходу алгоритма, когда ищется допустимая ячейка трехмерной матрицы для задания, процедура построения последовательно проверяет все временные интервалы в составе матрицы, соответствующие предварительно заданному множеству R временных интервалов. На множестве временных интервалов задано отношение частичного порядка <', с помощью которого оно и упорядочено. Следовательно, ячейки матрицы (в размерности временных ячеек) соответствуют временным интервалам в том порядке, котором они располагаются в упорядоченном множестве R.
Поэтому с помощью выбора отношения частичного порядка на множестве R можно упорядочить временные интервалы таким образом, чтобы при построении расписания они заполнялись необходимым на образом.
В практической реализации нашей модели мы использовали упорядочивание временных интервалов в зависимости от времени и в зависимости ото дня недели, т.е. наше множество R выглядит следующим образом:
R = { (830, понедельник), (830, вторник), …, (830, суббота), (1010, понедельник),…}
Если количество занятых дней более критично, чем количество уроков в день, целесообразно выбрать другое упорядочивание, например такое:
R = { (830, понедельник), (1010, понедельник), (1150, понедельник),…}
Все написанное выше было учтено при создании практической разработки. Наша практическая реализация процедуры построения расписания учитывает два критерия оптимальности: плотность заполнения заданиями аудиторий и плотность заполнения заданиями временных интервалов именно в такой последовательности. Причем в нашем случае определяется не глобальный оптимум по выбранным критериям оптимальности, а некоторое приближение к нему.
В качестве схемы нахождения оптимума используется приближенная схема поиска в локальной области (Более подробно эта схема применительно к нахождению оптимального расписания описана в книге Э.Г. Коффмана [1]). В общем виде его алгоритм выглядит следующим образом:
На данный момент окончательная версия программы для автоматического построения расписания еще не готова. Текущая версия не полностью использует критерии оптимальности, ограничения и различные варианта входных данных.
Весь пакет прикладных программ автоматического построения расписания состоит из трех частей: визуальный редактор исходных данных, работающий под Windows 95/98/NT, компилятор текстовых файлов языка иерархической модели данных и прогамма генератор собственно расписания. В таблице 1. приведена основная информация по этим трем программам:
| Программа | Разработчик | Платформа | Законченность |
|---|---|---|---|
| Визуальный редактор | Салоп Ю. | Windows 95/NT | 60% |
| Компилятор иерархической модели данных | Давыдов С. | Windows 95/NT (переносима на UNIX) | 98% |
| Генератор расписания | Давыдов С. | Windows 95/NT (переносима на UNIX) | 65% |
Далее эти три программы будут рассмотрены более подробно.
Данная програма написана на языке C++ с использованием прикладного пакета разработки Borland C++ Builder v.1.0.
Вся структура данных представляется в стандартном управляющем элементе просмотра и редактирования дерева. Более подробную информацию об этой программе можно получить у ее автора. На данный момент мне она на глаза не попадалась.
Компилятор иерархической модели данных представляет собой программу на языке C++, работающую в тектсовом режиме (при его написании использовались только стандартные функции и структуры языка C++, соответствующего спецификации ANSI C++, благодаря чему обеспечен его перенос на любую платформу, для которой имеется компилятор с ANSI C++ (практически все современные UNIX-ы, Win32, OS/2)). Компиляция данной программы осуществлялась с помощью компилятора фирмы Symantec Inc. - Symantec C++ 7.2. В настоящий момент она отлично работает под Windows 95.
Компилятор имеет простую структуру, блягодаря простой структуре языка иерархической модели данных. Суть его работы состоит в переводе текстового описания иерархической структуры в ее представление в бинарном виде, в котором оно может быть прочитано генератором расписания.
Требования к памяти зависят от размера входного файла данных, более конкретную информацию пока мы привести не можем, так, как тестирование для реальных данных еще не были произведены.
В данном отчете не приведены исходные тексты компилятора в силу его большого размера. Однако они доступны изучения (их можно получить, написав письмо автору с запросом по E-mail: DavidovSV@yandex.ru).
Генератор расписания представляет собой программу, написанную на языке C++ с использованием копилятора Symantec C++ v.7.2 при соблюдении спецификации ANSI C++.
На настоящий момент программа генерации расписания находится на стадии доводки и отладки, поэтому никаких тестирований на реальных данных нами произведено не было. Алгоритм построения расписания еще окончательно не отлажен.
Исходные тексты доступны у автора.
Кроме нашей разработки нам известно еще две практических разработки на тему построения построения расписания. Одна из них сделана в нашем университете на кафедре вычислительной техники при участии Ю.Э. Резникова. Однако эта система на данный момент не занимается автоматической генерацией расписания, она только проверяет достоверность готового расписания, которое составляется вручную работниками университета.
Сведения о другой практической разработке опали к нам случайно и мы слышали о ней только со слов очевидцев ее работы. Эта программа занимается автоматическим составлением расписания для школы. Причем работает вполне корректно и быстро. О примененных в ней алгоритмах нам неизвестно ничего.
В таблице 2 приведены основные сравнительные характеристики нешей системы и описанных выше двух разработок.
| Параметр | Наша система | Система Ю.Э. Резникова | Система неизвестных |
|---|---|---|---|
| Используемая модель данных | иерархическая, сетевая | реляционная | реляционная |
| Операционная система | Windows 95/NT (переносима) | MS-DOS | Windows 95/NT |
| Выполняемые действия | автоматическое построение расписания | проверка непротиворечивости готового расписания | автоматическое построение расписания |
| Степень готовности | 75% | 90% | 99.9% |
| Расширяемость | высокая | невысокая | неизвестно |
| Переносимость | высокая | непереносима (написана на Cliper) | неизвестно |
| Наша критическая оценка (1-10) (для той задачи, на которую расчитаны разработки) | 7 | 5 | 8 |
На основе проделанной работы мы можем сделать следующие выводы:
В данной области знаний черезвычайно мало публикаций (мы нашли всего две, использовать из которых удалось только одну). Это возможно или из-за "ненужности" решения данной проблемы или, что более вероятно, из-за его трудности.
В том, что решение данной проблемы не тривиально (имеется ввиду четкое математическое обоснование решения для произвольных начальных данных), мы убедились на собственном опыте.
Возможно, новые методы обработки данных и моделирования, появившиеся за последние несколько лет, скажут новое слово (что уже не раз было в некоторых областях знаний) в попытке решения данной проблемы.
| <scool> | ::= | <faculties><departments><buildings><lessons><options> |
| <faculties> | ::= | faculties={<faculty><faculty list> |
| <faculty list> | ::= | <faculty><faculty list>|} |
| <faculty> | ::= | faculty[<fac.title>]={<speciality><speciality list> |
| <speciality list> | ::= | <speciality><speciality list>|} |
| <speciality> | ::= | speciality[<spec.code>,<spec.title>]={<group><group list> |
| <group list> | ::= | <group><group list>|} |
| <group> | ::= | group[<group code>,<group title>]={<course><course list> |
| <course list> | ::= | <course><course list>|} |
| <course> | ::= | course[<course number>]={<semester><sem.list> |
| <learn disc.list> | ::= | <learn disc.>;<learn disc.list>|} |
| <learn disc.> | ::= | learn_disc[<disc.of dep.>,<number of hours>] |
| <disc.of dep.> | ::= | <dep.title>.<disc.title> |
| <departments> | ::= | departments={<department><department list> |
| <department list> | ::= | <department><department list>|} |
| <department> | ::= | department[<dep.title>]={<teachers><disciplines>} |
| <teachers> | ::= | teachers={<teacher><teacher list> |
| <teacher list> | ::= | <teacher><teacher list>|} |
| <teacher> | ::= | teacher[<teacher name>]={<disc.title>;<disc.title list> |
| <disc.title list> | ::= | <disc.title>;<disc.title list>|} |
| <disciplines> | ::= | disciplines={<discipline><discipline list> |
| <discipline list> | ::= | <discipline><discipline list>|} |
| <discipline> | ::= | discipline[<disc.title>]={<preference><commitment>} |
| <preference> | ::= | preference={<place>;<place list> |
| <commitment> | ::= | commitment={<place>;<place list> |
| <place list> | ::= | <place>;<place list>|} |
| <place> | ::= | <build.code>.<aud.number>|<build.code>.all|<build.code>.none |
| <buildings> | ::= | buildings={<building><building list> |
| <building list> | ::= | <building><building list>|} |
| <building> | ::= | building[<build.code>]={<auditory>;<auditory list> |
| <auditory list> | ::= | <auditory>;<auditory list>|} |
| <auditory> | ::= | auditory[<aud.number>,<capacity>] |
| <sem.list> | ::= | <semester><sem.list>|} |
| <semester> | ::= | semester[<sem.number>,<weeks>]={<learn disc.>;<learn disc.list> |
| <options> | ::= | options={<option>;<option list> |
| <option list> | ::= | <option>;<option list>|} |
| <option> | ::= | <option name>=<option value> |
| <lessons> | ::= | lessons={<lesson>;<lesson list> |
| <lesson list> | ::= | <lesson>;<lesson list>|} |
| <auditory> | - | Аудитория |
| <auditory list> | - | Список аудиторий |
| <building> | - | Корпус |
| <building list> | - | Список корпусов |
| <buildings> | - | Корпуса |
| <commitment> | - | Желательные места проведения занятий по дисциплине |
| <course> | - | Курс |
| <course list> | - | Список курсов |
| <department> | - | Кафедра |
| <department list> | - | Список кафедр |
| <departments> | - | Кафедры |
| <disc.of dep.> | - | Дисциплина с кафедры |
| <disc.title list> | - | Список названий дисциплин |
| <discipline> | - | Дисциплина |
| <discipline list> | - | Список дисциплин |
| <disciplines> | - | Дисциплины |
| <faculty> | - | Факультет |
| <faculty list> | - | Список факультетов |
| <faculties> | - | Факультеты |
| <group> | - | Группа |
| <group list> | - | Список групп |
| <learn disc.> | - | Изучаемая дисциплина |
| <learn disc.list> | - | Список изучаемых дисциплин |
| <lesson list> | - | Список уроков |
| <lessons> | - | Уроки |
| <option> | - | Параметр |
| <option list> | - | Список параметров |
| <options> | - | Дополнительные параметры |
| <place> | - | Место |
| <place list> | - | Список мест |
| <preference> | - | Обязательные места проведения занятий по дисциплине |
| <semester> | - | Семестр |
| <sem.list> | - | Список семестров |
| <scool> | - | Аксиома |
| <speciality> | - | Специальность |
| <speciality list> | - | Список специальностей |
| <teacher> | - | Преподаватель |
| <teacher list> | - | Список преподавателей |
| <teachers> | - | Преподаватели |
| all | - | Reserved word (RW) Все аудитории == 0 |
| auditory | - | RW |
| building | - | RW |
| buildings | - | RW |
| commitment | - | RW |
| course | - | RW |
| department | - | RW |
| departments | - | RW |
| discipline | - | RW |
| disciplines | - | RW |
| faculties | - | RW |
| faculty | - | RW |
| group | - | RW |
| learn_disc | - | RW |
| none | - | RW Ни одна из аудиторий == -1 |
| options | - | RW |
| preference | - | RW |
| semester | - | RW |
| semesters | - | RW |
| speciality | - | RW |
| teacher | - | RW |
| teachers | - | RW |
| <aud.number> | - | Номер аудитории (целое) |
| <build.code> | - | Код корпуса (целое) |
| <capacity> | - | Вместимость аудитории (в группах) (целое) |
| <course number> | - | Номер курса (целое) |
| <dep.title> | - | Название кафедры (строка) |
| <disc.title> | - | Название дисциплины (строка) |
| <fac.title> | - | Название факультета (строка) |
| <group code> | - | Код группы (строка) |
| <group title> | - | Название группы (строка) |
| <lesson> | - | Время начала урока (время) |
| <option name> | - | Название параметра (строка) |
| <option value> | - | Значение параметра (строка) |
| <number of hours> | - | Число часов (целое) |
| <sem.number> | - | Номер семестра (целое) |
| <spec.code> | - | Код специальности (строка) |
| <spec.title> | - | Название специальности (строка) |
| <teacher name> | - | Имя преподавателя (строка) |
| <weeks> | - | Число недель в семестре (целое) |
| { } | - | Ограничители "группы" |
| [ ] | - | Ограничители параметров |
| , | - | Разделитель параметров |
| . | - | Разделитель доменного имени |
| ; | - | Раздилитель элементов "группы" |
| : | - | Разделитель времени |
| = | - | Символ принадлежности |
| days_per_week | - | Число дней в неделе (целое) |
| twin_weeks | - | Использовать разделение на числитель и знаменатель (bool) |
| Целое | - | Целое число 0, 1,..., 231-1 |
| Строка | - | "<последовательность символов>" |
| Время | - | <целое>:<целое> |
| bool | - | yes | no |