Составление расписание в ВУЗе

← →
ClawClaw (2011-09-02 10:39) [0]

Господа, кто занимался данной темой, какие источники порекомендуете для решения сабжевой задачи?

← →
TUser © (2011-09-02 10:47) [1]

задача NP-полная и на компьютере решается медленно, поэтому нужна тетя ))

← →
Sergey Masloff (2011-09-02 11:00) [2]

TUser © (02.09.11 10:47) [1]
+ 1
;-)

← →
ClawClaw (2011-09-02 11:04) [3]

К какому разделу математики относится эта проблема? К дискретной математике?

← →
Ega23 © (2011-09-02 11:21) [4]

> какие источники порекомендуете для решения сабжевой задачи?

Учебная часть.

← →
Ega23 © (2011-09-02 11:22) [5]

> К какому разделу математики относится эта проблема? К дискретной
> математике?

СЛАУ, вроде.

← →
Palladin © (2011-09-02 11:23) [6]

http://ru.wikipedia.org/wiki/Прикладная_математика

← →
alien1769 © (2011-09-02 11:38) [7]

Насколько я помню такая задача была в учебниках и даже с примерами ее решения в исходниках от великих Гуру Дельфи. (Версия 6 )

← →
TUser © (2011-09-02 11:49) [8]

Задача типа "Дано множество предметов (каждый предмет читается одним и только одним преподавателем), также известно какие имеются группы, и какие им должны быть прочитаны предметы; требуется составить такое расписание, чтобы все требуемые предметы всем группам были прочитаны, при этом они бы не пересекались для одной группы или одного преподавателя в одно и тоже время" - такая задача относится к теории графов. Действительно, надо построить граф, где вершины соответствуют парам предмет/преподаватель+группа, и две вершины не соединены ребром, если в них есть общая группа или общий предмет (то есть они не могут быть прочитаны одновременно и должны быть разнесены в расписании). В таком графе для решения задачи требуется найти клику - множество вершин, соединенных каждая с каждой, которые соотвествуют множеству пар группа+предмет/преподаватель, которые можно ставить одновременно.

Отношение этой задачи к теории графов не означает какого-либо ее отношения к жизни, разумеется. В жизни придется учесть много других факторов - доступность и качество аудиторий, пожелания преподавателей, возможности студентов и минобровские нормативы, в конце концов, бывает можно объединять группы или отменять предметы, либо вводить новые. И много чего еще. Поэтому в реальности сидит тетя с длинным списком телефонов преподавателей, и согласовывает, согласовывает, согласовывает. Можно ей дать какой-нибудь тулз для упрощения работы, типа не просто в Экселе вбивать, а аж в БД, сразу видеть конфликты и напоминания. Но заменить тетю нельзя.

← →
Inovet © (2011-09-02 12:08) [9]

> [8] TUser © (02.09.11 11:49)
> других факторов

ещё у преподавателя окна в 1-2 пары нежелательны между занятиями. Ещё кому-нибудь надо 1-2 дня свободных.

Интересно есть автоматизированные системы такие. В принципе всё можно учесть в исходных данных.

← →
TUser © (2011-09-02 13:30) [10]

> В принципе всё можно учесть в исходных данных

ну-ну

в учебной чатси есть один проектор, и этот ресурс нужен на таких-то занятиях по таким-то предметам

такой-то просит не ставить его после физкультуры

и т.д. Жизнь, увы, сложнее, чем программирование. Так что без кнопочки "вот этого переставить туда" и без бумажки/экселя/базы_данных, а еще лучше - головы составителя расписания, все равно никак.

← →
Inovet © (2011-09-02 13:43) [11]

> [10] TUser © (02.09.11 13:30)
> Так что без кнопочки "вот этого переставить туда"

Кнопочка обязательно нужна и полностью ручное составление для неформализованной оптимизации и неперелусмотренных ситуаций, но любое изменение показывает последствия. Т.е. не просто замена листа ватмана с карандашом на электронную вписывалку в сетку, а автоматизация какая-то.

← →
ClawClaw (2011-09-02 14:12) [12]

Я где-то читал, что это переборная задача.

> Inovet © (02.09.11 12:08) [9]

> Интересно есть автоматизированные системы такие.

Есть, но TUser прав - без тёти никуда! Моя суженая исполнянла рояль тёти несколько лет, та еще херь, скажу я вам.

Реально в ВУЗах (нормальных) есть расписание с прошлого года, в него только надо внести изменения. Это на поток. А на кафедре есть закрепленные им аудитории, и не так много предметов, все делают вручную. И опять же - расписание из года в год радикально не меняется. А работа у расписательниц еще та, это точно.

> Ega23 © (02.09.11 11:22) [5]
>
>
> > К какому разделу математики относится эта проблема? К
> дискретной
> > математике?
>
>
> СЛАУ, вроде.

низачод

> TUser © (02.09.11 11:49) [8]

> Отношение этой задачи к теории графов не означает какого-
> либо ее отношения к жизни, разумеется. В жизни придется
> учесть много других факторов - доступность и качество аудиторий,
> пожелания преподавателей, возможности студентов и минобровские
> нормативы, в конце концов, бывает можно объединять группы
> или отменять предметы,

задача минимизации пробега порожняка по Всея Руси тоже вроде бы к жизни отношения не имеет, с учетом того, что придется учесть, что Вася, который возит трубы, не захочет даже на день отдать свои вагоны Феде, который возит селедку, не верит он Феде, что тот вагоны надлежащим образом вымоет и не придется судиться (на время суда вагоны будут вонять)
http://www.zdp.ru/6/1390.shtml
и это потихоньку, но уверенно взлетает, с учетом дофигища возможных ограничений.

Составление расписание в ВУЗе Найти похожие ветки