RUS  ENG
Полная версия
ЖУРНАЛЫ // Информационные технологии и вычислительные системы // Архив

ИТиВС, 2010, выпуск 2, страницы 50–58 (Mi itvs13)

Критерий существования непрерывного размещения двусимвольных слов в матрице размера $L\times(2k+1)$

Д. М. Алекберли

Управление информационно-аналитического обеспечения при Министерстве экономики Республики Дагестан

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

Ключевые слова: непрерывное расписание, оптимизация расписания, NP-полные задачи, задачи, решаемые за полиномиальное время, критерий существования непрерывного расписания.



© МИАН, 2024