Управление информационно-аналитического обеспечения при Министерстве экономики Республики Дагестан
Аннотация:
Рассмотрен частный случай задачи составления учебного расписания, который сводится к нахождению условий размещения двусимвольных слов (далее $2$-слов) в строках матрицы $M(L\times(2k+1))$, $k\in N$ так, чтобы символы в строках стояли рядом, а в столбцах матрицы все символы были попарно различны. Найден критерий непрерывного размещения двусимвольных слов в матрице $M$, который позволяет значительно упростить процесс составления расписания, где требуется обеспечить отсутствие окон в работе преподавателей.
Ключевые слова:непрерывное расписание, оптимизация расписания, NP-полные задачи, задачи, решаемые за полиномиальное время, критерий существования непрерывного расписания.