Preview

Цифровая трансформация

Расширенный поиск

Модель построения расписания на основе прецедентов

Аннотация

В статье предложен подход по построения расписания занятий вуза на основе прецедентов. Модель базируется на математическом аппарате теории графов. В основу модели положены принципы поиска и доказательства изоморфизма графов. Процесс поиска изоморфизма графов описан в терминах реляционной алгебры. Проведены экспериментальные исследования, показавшие целесообразность использования данного подхода при подготовке реального расписания, а также возможность уменьшения размерности NP-полной задачи примерно на 38,5%.

Об авторе

С. Н. Нестеренков
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

м.т.н., начальник отдела ИТ ЦИИР БГУИР

 



Список литературы

1. Ерунов В.П., Морковин И.И. Формирование оптимального расписания учебных занятий в вузе .// Вестн. ОГУ. – 2001. – № 3.

2. Костенко В.А., Винокуров А.В. Локально-оптимальные алгоритмы построения расписаний, основанные на использовании сетей Хопфилда. // Программирование. – 2003. – № 4. – С. 27 – 40.

3. Ханов Г.В., Алабужев Е.В. Автоматизация составления расписаний с учетом неопределенности.// Информационные технологии в образовании, технике и медицине. Материалы международной конференции. В 3-х т. Т.1. – ВолГТУ, Волгоград, 2004.

4. L.P. Cordella, P. Foggia, C. Sansone, M. Vento. A (Sub) Graph Isomorphism Algorithm for Matching Large Graphs IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, 2004.

5. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.

6. К.Дж. Дейт. Введение в системы баз данных. – М.: Вильямс, 2005.


Рецензия

Для цитирования:


Нестеренков С.Н. Модель построения расписания на основе прецедентов. Информатизация образования. 2015;(1):61-73.

For citation:


Nesterenkov S. The Scheduling Model Based on Precedents. Informatization of Education. 2015;(1):61-73. (In Russ.)

Просмотров: 2773


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2522-9613 (Print)
ISSN 2524-2822 (Online)