(3.16)

Значение целевой функции должно минимизироваться. При этом в план попадают модули с максимальным коэффициентом значимости для профессиональной подготовки.

После исключения модуля из графа будут исключены также и связи этого модуля с его предками. Следовательно, в последний слой графа могут попасть предки исключенного модуля.

Из объема предложенных к изучению модулей вычитается объем исключенного модуля. Новый полученный объем модулей сравнивается с объемом плана. Если он превышает объем плана, то алгоритм продолжается с п.2. Если нет, то отбор прекращается.

Состояние учебного плана после исключения модуля из расчета

(3.17)

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

(3.18)

M - множество всех исключенных из расчета модулей.

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

После отбора модулей для наполнения учебного плана для оптимизации плана используется критерий минимизации временных разрывов между информационно связанными модулями (1.37).

Алгоритм отбора модулей в учебный плана по методу максимизации суммарной профессиональной значимости модулей, включенных в план.

схема 3.1

3.3.2 При выборе метода максимизации суммарной обобщенной значимости модулей без учета связности

В этом случае сначала отбираются модули для обработки, имеющие максимальную обобщенную значимость (3.19). Связи, прилегающие к модулям, исключенным из расчета, исключаются также из графа связности. В расчете участвуют связи между модулями, участвующими в расчете (3.20).

(3.19)

(3.20)

После отбора модулей для наполнения учебного плана и дуг графа связности при построении решения используется критерий минимизации временных разрывов между информационно связанными модулями (1.37).

3.3.3 При выборе метода максимизации суммарной обобщенной значимости модулей с учетом связности

Алгоритм отбора модулей аналогичен алгоритму отбора по критерию максимизации суммарной профессиональной значимости с учетом связности, с той разницей, что в п. 3 алгоритма из последнего слоя выделяется модуль, имеющий наименьшую обобщенную значимость.

(3.21)

3.4 Алгоритм оптимизации по критерию минимизации временных разрывов информационно связанных модулей

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

На начальном этапе обрабатывается введенная пользователем информация: рассчитывается по графику учебного процесса объем каждого семестра (1), делаются «жесткие» назначения модулей (2), рассчитываются цепочки дисциплин (последовательность изучения модулей внутри дисциплины, алгоритм описан в п. 4.3.1), вычисляются модули, не имеющие предков(3) (схема 3.2).

Расчет ведется пошагово. На каждом шаге назначается по одному модулю (или несколько в зависимости от ситуации). Начальный шаг расчета - это назначение к изучению модулей, которые не имеют предков. В базе вариантов появляется одна запись (или несколько в зависимости от установленного пользователем параметра) (4). Для этого состояния рассчитываются все возможные дальнейшие назначения. Возможным к назначению считается модуль, все предки которого к текущему состоянию наполнения плана изучены.

Затем проводится анализ этих модулей по ограничениям (1.21), (1.22), (1.24), (1.26).



схема 3.2

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

Далее расчет идет сканированием базы до тех пор, пока не будет заполнен весь объем учебного плана или не будут назначены все модули. Для начального состояния сканируется одна запись в базе с назначенными модулями, не имеющими предков.

Расчет идет по семестрам, т.е. обрабатываются только записи текущего семестра. Переход к следующему семестру происходит только после достижения конца базы. Итак, обрабатывается первая запись базы, и все возможные варианты дальнейшего назначения записываются в конец базы. Для каждого вновь созданного состояния рассчитываются все возможные дальнейшие назначения.

Расчет возможных вариантов заполнения учебного плана ведется по следующему алгоритму (схема 3.3).

Если текущий семестр еще не заполнен. Сначала выясняется возможность дальнейшего назначения модулей из уже «начатых» дисциплин. Для этого имеются ранее составленные цепочки всех дисциплин, благодаря которым известно, какой модуль внутри дисциплины следует за уже назначенным.

Если такая возможность существует, то назначаются следующие модули из «начатых» дисциплин и в базу записывается только этот вариант. Это аргументировано тем, что при маленькой интенсивности изучения дисциплины материал плохо усваивается. Кроме того, при большой (но в пределах максимальной для каждой дисциплины) интенсивности изучения получается меньший временной разрыв между информационно связанными модулями, что уменьшает значение выбранного нами критерия оптимальности. Количество вновь образуемых вариантов в этом случае равно единице.

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

Если текущий семестр заполнен и нужно начинать наполнение следующего семестра.

Вне зависимости от возможности назначения следующих модулей из уже «начатых» дисциплин, назначаются следующие по цепочкам дисциплин модули. Это аргументировано ограничением, что, однажды начавшись, дисциплина должна изучаться непрерывно (1.29). Если есть продолжение для «начатых» дисциплин, то этот вариант будет единственным.

Если все «начатые» дисциплины закончились в предыдущем семестре, то в каждый вариант назначается по одному возможному к назначению модулей из других дисциплин.

После записи вариантов, которые вытекают из обработанной записи, возвращаемся на следующую за обработанной запись и приступаем к ее обработке по вышеописанному алгоритму. Так как расчет ведется по семестрам, то обрабатываются только те записи, которые относятся к текущему семестру. Например, если обрабатывается первый семестр, то обрабатываются только записи наполнения первого семестра. Записи для второго семестра (которые возникают при обработке уже заполненного первого семестра) пропускаются. Семестр окажется полностью обработанным, когда будет достигнут конец базы.

Результатом всего расчета является дерево вариантов, т.е. каждый вариант после обработки имеет веер вариантов-потомков. Таким образом, число вариантов заполнения учебного плана растет со скоростью геометрической прогрессии. Именно поэтому необходимо их ограничение, т.к. обработка их всех будет неэффективной в связи с ограниченным быстродействием ЭВМ, ресурсами оперативной памяти и дискового пространства и, как следствие, неприемлемым увеличением времени расчета (при расчете всех вариантов - до нескольких суток на ПК с процессором Pentium и тактовой частотой 120 МГц).

Алгоритм заполнения учебного плана

схема 3.3

Наполнение семестра осуществляется исходя из ограничения на количество аудиторных часов в неделю (1.24). Т.е. при дальнейшей обработке какого-либо варианта рассчитывается объем уже назначенных в семестр модулей. Объем семестра при заданной интенсивности обучения и длительности (в неделях) известен. Если ни один из предназначенных для дальнейшего назначения модулей «не умещается» в семестр, то расчет семестра по данному варианту закончен. Отказ от назначения модулей, не умещающихся полностью в семестр, связан с тем, что начало и окончание изучения каждого модуля должно находиться внутри какого-либо семестра, т.е. не допускается разрывать изучение модулей во времени (1.25). И хотя в модуле может быть несколько разделов, он не может быть раздроблен на более мелкие составляющие для обеспечения равномерной интенсивности изучения дисциплины в семестре и обеспечения принципа типовой учебной недели (объем модуля соответствует минимальной интенсивности изучения дисциплины, соответствующей проведению одного часа какого-либо вида занятий в неделю).

После расчета всех вариантов расположения модулей внутри одного семестра для всех полученных вариантов рассчитываются времена начала и окончания изучения модулей. Для этого рассчитываются цепочки дисциплин для всех назначенных в семестр модулей. При известных номерах недель начала и окончания семестра и условии, что дисциплина изучается в течение всего семестра, не прерываясь и имея постоянную интенсивность, несложно рассчитать номера недель начала и окончания изучения каждого модуля по следующей схеме.

Объем лекций дисциплины в семестре :

(3.13)

где и - соответственно начало и конец семестра .

Интенсивность лекций дисциплины в семестре :

(3.14)

Номер недели начала и окончания первого модуля в семестре по цепочке дисциплины :

(3.15)

(3.16)

Рекурсивные формулы для вычисления начала и окончания каждого последующего по цепочке дисциплины модуля:

(3.17)

(3.18)

где - номер модуля по цепочке дисциплин в текущем семестре .

Расчет номеров недель начала и окончания изучения модулей необходим для подсчета критерия. По значению критерия отсекаются неперспективные варианты учебного плана, которые имеют большой критерий. При расчете критерия для назначенных модулей из полного графа связей вырезается подграф, в который входят только назначенные к текущему моменту модули. Связи, выходящие из этого подграфа, включаются в расчет критерия и направляются в начало следующего семестра. Перебирая оставшиеся связи, рассчитывается значение приращения критерия при известных номерах недель начала и окончания изучения модулей. Полное значение критерия есть сумма значения критерия в предыдущем семестре и приращения критерия - формулы (3.8), (3.10), (3.11).

Определенное количество вариантов (задаваемое пользователем) с наименьшим критерием оставляется для дальнейшей обработки, а остальные исключаются.

При переходе к следующему семестру вступает в действие другой алгоритм назначения, который вытекает из ограничения, что дисциплина, начавшись, должна изучаться непрерывно (1.29). Исходя из этого ограничения, мы всегда должны знать, какой следующий модуль начавшейся изучаться дисциплины нужно назначить в следующем семестре. Поэтому модули дисциплины должны быть связаны между собой в цепочку, и эта цепочка не должна «расслаиваться». Это значит, что проходя последовательно по цепочке модулей внутри дисциплины от начального до конечного модуля, мы должны обойти все модули дисциплины, т.е. должен быть известен порядок следования модулей внутри дисциплины. Даже если модули внутри дисциплины связаны между собой очень слабо или не связаны вообще, необходимо организовать цепочку внутри дисциплины (из очень слабых связей для правильной организации расчета).

Исходя из вышесказанного, при переходе к следующему семестру в него назначаются (несмотря на другие ограничения) модули, следующие за назначенными. Дальнейшее наполнение семестра выполняется по вышеописанному алгоритму.

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

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

3.5 Заключение по главе III

Сделано обоснование применения методов динамического программирования для решения задачи синтеза учебных планов вузов.

Разработаны алгоритмы синтеза учебных планов, а именно:

по критерию максимизации суммарной значимости модулей для профессиональной подготовки с учетом связей между модулями;

по критерию максимизации суммарной обобщенной значимости модулей без учета связей между модулями;

по критерию максимизации суммарной обобщенной значимости модулей с учетом связей между модулями.

Разработан алгоритм оптимизации плана по критерию минимизации временных разрывов между модулями с учетом тесноты связей.

Следующим этапом необходимо создать автоматизированную систему синтеза учебных планов и провести расчеты для подтверждения или опровержения эффективности предложенных алгоритмов.

Практическая реализация и результаты исследования

4.1 Исходные данные для расчета и возможности настройки расчета

Структура автоматизированной системы синтеза учебных планов вузов представлена в приложении VII.

Начальным этапом работы является настройка на конкретный учебный план. Учебный план определяется формой обучения, специальностью и годом обучения.

Для синтеза каждого учебного плана исходными данными являются следующие:

график учебного процесса;

список циклов дисциплин;

список предлагаемых для изучения дисциплин;

список учебных модулей с содержанием (тезаурусом) и расчасовкой (количество часов лекций, лабораторных работ, практических занятий, индивидуальной и самостоятельной работы);

нормы времени по дисциплинам: каждой дисциплине может соответствовать максимально допустимая интенсивность изучения;

нормы времени по циклам дисциплин: для каждого цикла возможно указание минимального количества часов в цикле;

список экспертов;

результаты экспертного опроса по коэффициенту значимости каждого учебного модуля для профессиональной подготовки;

результаты экспертного опроса по коэффициенту тесноты связи между модулями;

список курсовых работ и проектов с множеством учебных модулей для каждого, после изучения которых планируется курсовая работа или проект.

список «жестко» назначаемых по семестрам модулей.

Пользователь программы составления учебных планов должен иметь некоторую свободу действий. Ведь составленный программой план - это не догма, несмотря на то, что он считается оптимальным по предложенному критерию. Поэтому в программе предусмотрены различные возможности для настройки расчета.

Назначение некоторых модулей «жестко» в определенные семестры.

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

Отделение «жестко» назначенных модулей от графа связности.

Для каждого «жестко» назначенного модуля нужно задать параметр - отделять его от графа связности или нет. В случае отделения все связи, входящие в модуль и выходящие из него, отбрасываются и не анализируются. Этот модуль получается оторванным от графа связности. Он не является ни для каких других модулей базой и не использует базу других модулей. В случае, когда модуль не отделяется, все связи, входящие в него и выходящие из него, анализируются и влияют на последовательность изучения связанных с ним модулей.

Назначение всех модулей без предков сразу в первый семестр или начинать заполнение только с одного модуля.

Во втором случае начальных вариантов расчета будет столько, сколько имеется модулей без предков в графе связности. В этом случае при большом количестве таких модулей значительно (в несколько раз) увеличивается время расчета.

Задание количества вариантов, которые оставляются для дальнейшей обработки после расчета каждого семестра.

Рекомендуемое значение - 20. При увеличении этого числа увеличивается время расчета. При уменьшении - могут быть удалены перспективные варианты заполнения учебного плана. Если быстродействие ПЭВМ позволяет увеличить это число, то рекомендуется это сделать, т.к. это позволяет обработать большее количество вариантов заполнения.

Выбор алгоритма отбора модулей.

Пользователь имеет возможность провести отбор модулей в план по различным алгоритмам, а именно:

максимизация суммарной значимости модулей, включенных в план с учетом связности;

максимизация суммарной обобщенной значимости модулей, включенных в план без учета связности;

максимизация суммарной обобщенной значимости модулей, включенных в план с учетом связности.

4.2 Инфологическая модель задачи синтеза

На схеме инфологической модели (приложение III) показаны базы, участвующие в расчете и связи между ними.

Сплошными стрелками показаны связи между базами по полям. Рядом со стрелкой указан тип связи (1-n - один ко многим, 1-1 - один к одному).

Пунктирными стрелками показаны информационные потоки, т.е. когда в одну базу поступает информация из других при помощи какой-либо обработки, расчета.

4.3 Некоторые алгоритмы решения частных задач

4.3.1 Нахождение цепочек дисциплин

Для обеспечения ограничения, что однажды начавшись, дисциплина должна изучаться непрерывно (1.29), нужно знать, какой модуль дисциплины за каким следует, то есть модули дисциплин должны быть связаны между собой в цепочку, причем возможно разветвление этой цепочки (рис. 4.1), но невозможно расслоение (рис. 4.2). Это требование вполне обоснованно, т.к. внутри одной дисциплины разные ее модули никогда не изучаются параллельно.

Такое представление информации правильно:

1 3 2 4

рис. 4.1

Такое - неправильно:

1 3 2 4

5

рис. 4.2

При разветвленной структуре связей внутри одной дисциплины необходимо упорядочить учебные модули внутри дисциплины. Для этого используется следующий алгоритм.

Сначала выделяется множество всех дисциплин, которые присутствуют в графе связей. Коды этих дисциплин хранятся в массиве DISC. Все связи между объектами хранятся в базе данных со следующими полями: код предка, код потомка, коэффициент тесноты связи. Из этой базы последовательно делается выборка по коду дисциплины. Коды дисциплин для каждого модуля находятся в базе RAZDEL, а наименования - в классификаторе дисциплин. Поэтому для получения выборки необходимо организовать соответствующую систему реляций: SVYAZI.KOD_PRED-RAZDEL.KOD и SVYAZI.KOD_POTOM-RAZDEL.KOD . Эта выборка дублируется в другой рабочей области. Рабочие области связываются друг с другом так: SVYAZI.KOD_PRED - SVYAZI.KOD_POTOM. В первой области ищется тот модуль, которого нет во второй как потомка. Это значит, что данный модуль не имеет предков и образует первый слой обрабатываемой дисциплины. Он записывается в базу цепочек дисциплин SLOY, где будут храниться цепочки дисциплин, с номером слоя 1. В выборке найденная запись удаляется. После удаления модуль, следующий вторым номером, не будет иметь предков и может быть найден по тому же алгоритму. Описанная процедура повторяется до тех пор, пока в выборке не останется последняя запись. Она образует последний слой дисциплины. После окончания всей обработки по каждой дисциплине мы знаем, какой модуль за каким следует внутри каждой дисциплины.

Приведем пример нахождения порядка следования модулей в дисциплине по рис. 4.1. Произведена выборка из графа связности для данной дисциплины. Два дубликата выборки с индексацией по коду предка и коду потомка представлены в табл. 4.1 и табл. 4.2. Ищем номер модуля, который есть в предках, но его нет в потомках. Это модуль 1. Удаляем в обеих рабочих областях связи, в которых участвует модуль 1 (строки помечены маркерами). Удаляемый из графа модуль является его первым слоем. Записываем его в таблицу слоев под номером 1. Далее таким же образом выделяются модули 3, 2 и 4.

Связи
предок	потомок
1	3
1	4
2	4
3	2

табл. 4.1

Связи
потомок	предок
2	3
3	1
4	1
4	2

табл. 4.2

модуль	слой
1	1
3	2
2	3
4	4

табл. 4.3

Еще одним условием, предъявляемым к входным данным, является отсутствие контуров внутри одной дисциплины. При их наличии невозможно будет выделить цепочки дисциплин, которые обеспечивают условие непрерывности изучения дисциплины. Это ограничение обычно не вызывает трудностей, т.к. замкнутые контуры в графе связности учебного материала обычно возникают при оценке связей между модулями различных дисциплин разными экспертами. При оценке же связей между модулями одной дисциплины разногласий даже между разными экспертами не возникает.

4.3.2 Нахождение вершин, принадлежащих контурам

Вершины, принадлежащие контурам, находятся с помощью транзитивного алгоритма бинарного замыкания [40]. Приведу описание этого алгоритма.

Граф связей представляется в виде матрицы A(N,N), каждый элемент которой A(i,j) является единицей, если есть связь между модулем i и j, направленная из i в j, и нулем в противном случае. N - количество модулей. Пусть в первой строке находится единица в позиции A(1,k). Тогда из строки с индексом k в первую строку в соответствующие ячейки по вертикали переписываются все единицы. Так повторяется до конца строки. Затем таким же образом обрабатываются следующие строки матрицы. Алгоритм повторяется снова с первой строки матрицы до тех пор, пока матрица не перестанет меняться. Тогда индексы единиц, которые после обработки находятся на главной диагонали матрицы, указывают на номера модулей, которые принадлежат контурам. Эти номера записываются в отдельную матрицу - CYCLE.

Так, в примере, приведенном на рис. 4.3, контуру принадлежат вершины 2, 3, 6. Составляем для графа матрицу связности. Это табл. 4.4.После применения к ней транзитивного алгоритма бинарного замыкания матрица 1 преобразуется в матрицу, представленную в табл. 4.5.

Вершины, принадлежащие контурам, находятся на главной диагонали матрицы. Это вершины 2, 3, 6. В матрице они выделены другим шрифтом.

1 2 3 4

5 6 7

рис. 4.3

	1	2	3	4	5	6	7
1		1
2			1
3				1		1
4
5						1
6		1					1
7

табл. 4.4

	1	2	3	4	5	6	7
1		1	1	1		1	1
2		1	1	1		1	1
3		1	1	1		1	1
4
5		1	1	1		1	1
6		1	1	1		1	1
7

табл. 4.5

4.3.3 Обработка контуров

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

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

Недостатками данного метода являются следующие:

алгоритм такой обработки графа является очень сложным и при наличии многих контуров в графе его обработка будет занимать много времени, что при объеме всей рассматриваемой задачи может оказаться существенным;

при разрыве связей между модулями происходит потеря информации.

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

На каждом шаге расчета ищутся возможные модули для назначения. Первый этап их поиска - нахождение потомков назначенных на предыдущем шаге модулей. Второй шаг - анализ возможности назначения каждого из потомков в зависимости от изученности его базы (всех его предков). Если имеется неизученная база, то в случае отсутствия в графе контуров его назначение невозможно. Если же в графе присутствуют контуры, то все модули неизученной базы ищутся в матрице CYCLE. При отсутствии какого-либо модуля в этой матрице назначение исследуемого модуля невозможно до назначения модулей, которые не принадлежат контурам. Если вся неизученная база принадлежит контурам, то назначить исследуемый модуль можно. Таким образом, контур размыкается для последующей обработки. В разных вариантах расчета модулями, размыкающими контур, являются различные модули, что влияет на значение критерия оптимальности. При этом не происходит потери информации, а лишь анализируются по выбранному критерию различные варианты назначения учебных модулей. Неизбежное нарушение ограничения (1.28) при разрыве контура включено в критерий.

Еще одна особенность расчета при сохранении контуров в исходном графе возникает, если вершины контура попадают на начало графа, т.е. если модули, принадлежащие контурам, не имеют в качестве предков вершин, не принадлежащих контурам. Для таких вершин ищется вся неизученная база на всю глубину. Если в этой базе имеются неизученные модули, не принадлежащие контурам, то назначение модуля невозможно. Если нет, то модуль включается в список возможных назначений.

4.3.4 «Жесткое» назначение разделов

Возможность назначения некоторых разделов «жестко» в определенные семестры порождает множество нюансов в алгоритме расчета. Начальная обработка введенной информации для каждого «жестко» назначаемого модуля ведется в зависимости от признака, введенного для него (отделять или не отделять от графа связности). Если для модуля проставлен признак удаления из графа, то из базы связей между модулями удаляются все связи, в которых присутствует этот модуль в качестве предка или потомка.

Если при «жестком» назначении модулей в семестры они не вырезаются из графа связности, то алгоритм расчета следующий. При переходе к расчету следующего семестра проверяется наличие для него «жестких» назначений. Но, исходя из постановки задачи, модуль назначать нельзя, пока у него имеется неизученная база. Поэтому необходимо найти всю неизученную базу всех «жестко» назначаемых модулей для данного семестра. Неизученная база ищется на всю глубину, а не только в близлежащем слое.

Например, для графа, изображенного на рис. 4.4, где к текущему моменту времени изучены затемненные модули 1, 5 и 3, неизученной базой для модуля 7 будут являться модули 4, 2 и 6.

1 4

5 7

2 6

3

рис. 4.4

Подсчитывается объем найденной неизученной базы и сравнивается с объемом семестра. Если объем неизученной базы вместе с объемом «жестко» назначаемых модулей не превышает объем семестра, то все они назначаются в семестр. Если нет, то выдается предупреждение об ошибке и расчет данной ветки прекращается. В этом случае рекомендуется предварительно сделать расчет без «жесткого» назначения модулей, чтобы приблизительно сориентироваться, в какие семестры попадают модули исходя из анализа связей между модулями.

Если «жестко» назначаемые модули вырезаются из графа связей, то алгоритм расчета упрощается и нет необходимости поиска неизученной базы «жестко» назначаемых разделов. Но в этом случае эти модули получаются оторванными от графа и не имеют предков. А вершины, не имеющие предков, ищутся для начального назначения в первый семестр. Поэтому после нахождения модулей, не имеющих предков, необходимо исключить из них модули, назначаемые «жестко».

Еще один возникающий нюанс - это то, что при поиске возможных к назначению модулей после расчета какого-либо варианта необходимо проверить, не назначается ли модуль «жестко» в другой семестр. Если да, то нужно исключить его из множества возможных назначений.

4.3.5 Разворачивание графа полученных вариантов в отдельные учебные планы

После просчета всех вариантов заполнения очередного семестра учебного плана исходными модулями мы имеем некоторый граф вариантов. Вершинами этого графа являются состояния изученности модулей в конкретный момент времени (в конце каждого семестра), причем одного и того же состояния можно достичь различными путями. Например, модуль 1 назначен в первом семестре, модуль 2 - во втором или наоборот. И в том, и в другом случае мы в конце второго семестра имеем состояние, описываемое двоичной маской следующим выражением - «11», т.е. назначен первый и второй модуль, о чем говорят единицы в соответствующих позициях.

Мы имеем столько вариантов заполнения семестра учебного плана, сколько путей имеется из начальной вершины графа в конечную. Причем начальная вершина всегда одна: ни один модуль еще не назначен, а конечных может быть несколько. Это объясняется тем, что в один и тот же семестр в различных вариантах назначаются разные модули.

Для получения всех вариантов заполнения плана в базе организована система ссылок. Каждая запись должна иметь ссылку на запись-родитель, после обработки которой она возникла. Но для расчета нужны только записи, соответствующие окончанию семестра. Именно после заполнения всего семестра можно рассчитать начала и окончания изучения учебных модулей. Поэтому при обработке незаполненных семестров в качестве ссылки указывается не запись-родитель, а запись, соответствующая предыдущему заполненному семестру.

Цепочкой учебного плана будем называть номера записей базы вариантов заполнения учебного плана, соответствующие наполненному семестру. Например, цепочка учебного плана может выглядеть так: 1125,576,294,53,2. В этом случае данные о заполнении первого семестра находятся в записи 2, второго - в записи 53, третьего - в записи 294, четвертого - в записи 576, пятого - в записи 1125.

Просмотр базы начинается с конечных вершин. В базе вариантов заполнения учебного плана ищется запись с признаком заполнения (все модули назначены или заполнен объем учебного плана). В базу цепочек (CHAINS) добавляются запись следующего содержания: код записи с последним семестром - семестр - признак окончания цепочки (достигнут ли первый семестр) - код записи с последним семестром. Второй код записи будет являться началом цепочки, описывающей учебный план. Признак окончания цепочки будет false, т.к. это последний семестр. Когда будет достигнут первый семестр и не будет указателя на предыдущий семестр, признак окончания цепочки будет переведен в true.

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

Такая обработка продолжается до конца базы. После окончания обработки в базе имеется несколько записей с признаком окончания true. Именно они образуют возможные варианты заполнения учебного плана.

4.3.6 Вычисление наименьшего критерия для каждого состояния

При расчете вариантов заполнения учебного плана мы имеем некоторый граф. Каждая вершина этого графа представляет собой некоторую ступень заполнения учебного плана. Причем каждой вершине соответствует несколько критериев оптимальности, значения которых формируются из значения критерия в предыдущем семестре и приращения в текущем (3.7). Это связано с тем, что к одному и тому же состоянию можно прийти различными путями. Исходя из условия задачи, нас интересует минимальный критерий, соответствующий каждой вершине (3.9). Поэтому вновь полученному состоянию приписывается минимальное значение из всех рассчитанных критериев, а также устанавливается ссылка на запись-родитель, из которой это значение сформировано. Эта операция отсекает множество неоптимальных вариантов учебных планов из дальнейших расчетов.

4.3.7 Назначение контрольных точек

Контрольные точки проставляются после составления учебного плана.

Первоначально в соответствии с ограничением (1.33) расставляем экзамены и зачеты по дисциплинам, длящимся более чем в одном семестре.

Затем устанавливаются курсовые проекты и работы в те семестры, в которые попали последние модули в дисциплине, необходимые для выполнения курсового проекта или работы. Список модулей, необходимых для выполнения курсового проекта или работы устанавливается пользователем в исходных данных. Для соблюдения ограничения (1.34) при попадании в один семестр более 2 курсовых работ и проектов курсовые сдвигаются в следующий семестр у дисциплин, которые имеют в нем продолжение.

Следующим шагом устанавливаются экзамены по всем оставшимся дисциплинам. По каждому семестру осуществляется проверка ограничения (1.31). Если имеет место нарушение этого ограничения, то в данном семестре экзамены заменяются зачетами для дисциплин, имеющих минимальную суммарную обобщенную значимость по всем модулям, попавшим в данный семестр.

Если нет противоречия в исходных данных между ограничениями (1.22) и (1.31), (1.32), т.е. если KSEx+Z, то ограничение (1.32) в данном алгоритме выполняется автоматически.

4.4 Результаты расчетов

По разработанным алгоритмам были проведены расчеты при следующих начальных условиях:

Все модули без предков назначаются в первый семестр.

Модули дисциплин цикла гуманитарных и социально-экономических дисциплин назначались по семестрам «жестко» аналогично варианту существующего плана. Это объясняется слабой связью этих дисциплин с дисциплинами остальных циклов.

Ограничения на интенсивность изучения дисциплин по всем дисциплинам - 6 часов в неделю, кроме дисциплины «Технология хлеба, кондитерских и макаронных изделий». По этой дисциплине максимальная интенсивность 9 часов в неделю, т.к. это соответствует существующей интенсивности ее изложения.

Количество оставляемых для расчета вариантов - 20.

Расчеты по разработанным алгоритмам выявили следующее.

При оптимизации плана по специальности 27.03.00 - «Технология хлеба, кондитерских и макаронных изделий» по критерию минимизации временных разрывов критерий расчетного плана составил 2 839 428,5, в то время как у существующего плана он равен 4 723 095,8. Таким образом, значение расчетного критерия составило 60% от существующего, т.е. улучшение плана по данному критерию составило 40%. Распределение модулей по семестрам в исходном и расчетном варианте при оптимизации плана по специальности 27.03.00 представлено в приложении V.

При синтезе четырехгодичного плана из пятилетнего по различным алгоритмам получены результаты, представленные в табл. 4.6. Эти же данные представлены на диаграмме.

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

По алгоритмам синтеза плана с учетом связности получены хорошие результаты наполнения и всех остальных критериев. Но наилучшие результаты достигнуты в случае применения алгоритма максимизации обобщенной значимости с учетом связности модулей.

Распределение модулей по семестрам в существующем плане по направлению 55.24.00 «Технология продуктов питания» и в расчетных вариантах представлено в приложении VI.

табл. 4.6

	Существующий план	Максимизация проф. зн-ти с учетом связности	Максимизация обобщ. зн-ти без учета связности	Максимизация обобщ. зн-ти с учетом связности
	зн-ние	зн-ние	%	зн-ние	%	зн-ние	%
Qпроф	52	58,9	113,3	57,6	110,8	59,5	114,4
Qvпроф	130.8	151.8	115.7	147.7	112.9	152.5	116.6
Qобоб	28,39	31,84	112,2	31,19	109,8	32,14	113,2
Qvобоб	73.17	83.42	114.0	81.62	111.5	84.02	114.8
Qвр	1503095	1290521	85,9	999125	66,5	1198949	79,8
Vпл	3167	3502	110,6	3366	106,3	3536	111,6

Максимальный объем плана - 3591 час.

Qпроф - суммарная значимость модулей для профессиональной подготовки;

QVпроф - суммарная значимость модуле для профессиональной подготовки с учетом объема модулей;

Qобоб - суммарная обобщенная значимость модулей;

QVобоб - суммарная обобщенная значимость модулей с учетом объема модулей;

Vпл - объем плана в часах.



Исходя из приведенных данных, можно сделать вывод, что при научном подходе к процессу составления учебных планов вузов можно добиться значительного улучшения их качества. Анализ связи между дисциплинами позволяет наилучшим образом расположить дисциплины во времени, а, следовательно, добиться наилучшего их усвоения.

При обработке исходных данных благодаря предусмотренным в программе параметрам расчета синтезируется план, не противоречащий государственным образовательным стандартам.

4.5 Заключение по главе IV

Разработана инфологическая модель автоматизированной системы синтеза учебных планов вузов для реализации в среде С++.

Разработаны алгоритмы решения частных проблем, возникающих при расчете учебного плана по методу динамического программирования.

Создана гибкая автоматизированная система синтеза учебных планов вузов, позволяющая изменять параметры расчета и получать, таким образом, учебный план, максимально удовлетворяющий запросам вуза.

Сделаны расчеты по оптимизации учебного плана по специальности 27.03.00 - «Технология хлеба, кондитерских и макаронных изделий» синтезирован план по направлению 55.24.00 - «Технология продуктов питания». В результате расчетов доказана эффективность разработанных алгоритмов.

Заключение

В диссертации получены следующие результаты:

1. Проведен анализ процесса составления учебных планов вузов. Выяснено, что при существующем множестве ограничений, налагаемых на учебный план, его составление вручную сопряжено со значительными трудностями.

Сделана математическая постановка задачи, а именно:

описана система ограничений, налагаемых на план;

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

Предложен метод формирования исходных данных для решения задачи синтеза. Метод основан на составлении тезаурусов учебных модулей и анализе использования информации, описанной в тезаурусе, в информационно связанных модулях.

Предложена методика проведения экспертиз. Обоснован выбор в каждом конкретном случае того или иного метода. Разработана анкета для проведения экспертиз по определению коэффициента значимости модуля для профессиональной подготовки и коэффициента тесноты связи между информационно связанными модулями.

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

Предложен метод обработки экспертных оценок, когда оценка каждого эксперта проверяется на согласованность с остальными экспертами и в зависимости от этой оценки вычисляется компетентность каждого эксперта.

Разработан алгоритм оптимизации учебного плана по критерию минимизации временных разрывов с учетом тесноты связи информационно связанных модулей. Алгоритм основан на принципах динамического программирования, когда задача решается пошагово с отсечением неперспективных вариантов построения плана.

Разработаны три алгоритма синтеза учебного плана, а именно: максимизация суммарной профессиональной значимости модулей, включенных в план, с учетом связности; максимизация суммарной обобщенной значимости модулей, включенных в план, с учетом и без учета связности.

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

При помощи созданной автоматизированной системы проведена оптимизация плана специальности 27.03.00 и синтез плана направления 55.24.00 и подтверждена эффективность разработанных алгоритмов. При оптимизации плана специальности 27.03.00 получено улучшение критерия минимизации временных разрывов на 40%. При синтезе плана направления 55.24.00 наилучшие результаты получены по алгоритму максимизации суммарной обобщенной значимости модулей, включенных в план.

Список используемой литературы

Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л.: Изд-во Ленингр. ун-та, 1981. 328 с.

Агранович Б.Л., Кабанов В.И. Модель оценки качества подготовки специалистов в высших учебных заведениях. //Кибернетика и вуз. Вып.13. Томск, 1987 , с.19-22.

Алексеева Л.Н. Формирование гибкого содержания образования и обучения в средних специальных учебных заведениях. Автореф. дисс. ... канд. тех. наук. Москва, 1997.

Анисимов Б.В., Савельев А.Я. и др. Применение ЭЦВМ для автоматизации процесса составления учебных планов и расписаний. //Использование ЭВМ в организации и планировании учебного процесса. М.: «Высшая школа», 1972, с.121-142.

Архангельский С.И. Учебный процесс в высшей школе, его закономерные основы и методы. М.: «Высшая школа», 1980. 368 с.

Архангельский С.И., Михеев В.И. Теоретические основы научной организации педагогических исследований. М.: «Знание», 1976. 27 с.

Архангельский С.И., Михеев В.И., Машников С.А. О моделировании и методике обработки данных педагогического эксперимента. М.: «Знание», 1974. 48 с.

Архангельский С.И., Михеев В.И., Перельцвайг Ю.М. Вопросы изменения, анализа и оценки результатов в практике педагогических исследований. М.: «Знание», 1975. 42 с.

Бабинцев В.С., Подиновский В.В. Выбор решений по многим критериям, упорядоченным по важности. М., 1977. 44 с.

Белкин Е.Л. Разработка методов построения системы изложения учебного материала. Отчет о научно-исследовательской работе.

Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. Москва, 1976.

Бенайюн Р., Ларичев О.И. Линейное программирование с многими критериями. Метод ограничений. //Автоматика и телемеханика, 1971, №8.

Берж К. Графы и их применение. М.: Изд-во иностранной лит-ры, 1962. 319 с.

Беспалько В.П. Основы теории педагогических систем. Воронеж, 1977, с. 40-86.

Бешелев С.Д., Гурвич Ф.Г. Математико-статистические методы экспертных оценок. Москва, 1980. 262 с.

Герман Э.И. Разработка моделей и алгоритмов многоцелевой оптимизации планов учебного процесса. Дисс. ... канд. тех. наук. Томск, 1975, 194 с.

Горбатова Р.Е. Системный анализ деятельности специалиста и моделирование задач подготовки инженерных кадров. Автореф. дисс. ... канд. тех. наук. Томск, 1981.

Государственный образовательный стандарт высшего профессионального образования. Москва, 1995.

Гусев И.Т., Мухин Э.В., Сорокин А.С., Сумароков Л.Н. Методика разработки учебного плана. //Использование ЭВМ в организации и планировании учебного процесса. М.: «Высшая школа», 1972, с.176-195.

Гусев И.Т., Мухин Э.В., Сумароков Л.Н. Некоторые семантические аспекты проблемы разработки учебных планов. //Использование ЭВМ в организации и планировании учебного процесса. М: ВШ, 1972, с.168-175.

Джоффрион А., Дайер Дж., Фрайнберг А. Решение задачи оптимизации при многих критериях на основе человеко-машинных процедур. Применение к задаче оптимизации учебного процесса факультета университета. //Вопросы анализа и процедуры принятия решений. М.: «Мир», с. 126-145.

Димова В. И др. К вопросу о методе составления тезауруса по специальности. //Современная высшая школа, 1978, №3.

Евланов Л.Г., Кутузов В.А. Экспертные оценки в управлении. М.: «Экономика», 1978. 133 с.

Информационная технология. Комплекс стандартов и руководящих документов на автоматизированные системы. (ГОСТ 34.201-89, ГОСТ 34.602-89, РД 50-682-80, РД 50-680-88, ГОСТ 34.601-90, ГОСТ 34.401-90, РД 50-34.698-90, ГОСТ 34.003-90, Р 50-34.119-90). М.:1991. 144 c.

Каган В.И., Сычеников И.А. Основы оптимизации процесса обучения в высшей школе. Москва, 1987.

Карпов В.И. Составление учебных планов вузов с помощью ЭЦВМ. //Применение ЭЦВМ для автоматизации обучения и управления учебными заведениями. Киев, 1972 ., с.121-130.

Карпов В.И., Казакова И.Е. и др. Вычислительная техника в инженерных и экономических расчетах. Москва, 1977. 68 с.

Кендэл М. Ранговые корреляции. М., 1978.

Кини Р.Л., Райфа Х. Принятие решения при многих критериях: предпочтения и замещения. М.: «Радио и связь», 1981. 560 с.

Китаев Н.Н. Групповые экспертные оценки. М., 1975.

Комплексные подходы к построению и применению экономико-статистических моделей./Под редакцией Б.Б. Розина, Новосибирск, 1981, с.7-55, 96-132.

Концептуальные основы разработки современных информационных технологий формирования содержания подготовки по информатике. Москва, НИИПВШ, вып.6-7, 1994.

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

Кофман А., Дебазей Г. Сетевые методы планирования и их применение. М.: Прогресс, 1968. 181 с.

Кристофидес Н. Теория графов. Алгоритмический подход. Москва, 1978.

Кузнецов А.В., Холод Н.И. Математическое программирование. Минск: «Вышэйшая школа», 1984. 221 с.

Леднев В.С. Содержание образования: сущность, структура, перспективы. М, ВШ, 1991. 224 с.

Леонтьев Л.П., Гохман О.Г. Проблемы управления учебным процессом. Рига, 1984, с. 24-62.

Липский В. Комбинаторика для программистов. Москва, 1988.

Мартынюк В.В. Экономное построение транзитивного замыкания бинарного отношения. //Журнал вычислительной математики и математической физики, 1962, т.2, №4.

Методика научно-обоснованного составления учебного плана. М.: НИИВШ, 1976. 80 с.

Миронова В.А. Разработка моделей и алгоритмов автоматизированного решения задач (на примере планирования учебного процесса в АСУ ВУЗ). Дисс. ... канд. тех. наук. М., 1978. 294 с.

Михеев В.И. Моделирование и методы теории измерений в педагогике. М.: ВШ, 1987. 200 с.

Мишева П. И др. Основные положения и направления совершенствования учебных планов и программ для подготовки рабочих по профессиям широкого профиля в Народной Республике Болгария. //Научные основы совершенствования учебных планов и программ для подготовки рабочих широкого профиля. Сборник научных трудов. Ленинград, 1987, с.22-35.

Моргунов И.Б. Аналитические методы исследования учебных программ. Дисс. ... канд. тех. наук. М., 1965. 152 с.

Московиченко А.Л. Дерево целей инженерной деятельности. //Кибернетика и вуз. Выпуск 13. Томск, 1987, с.123-129.

Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: «Наука», 1970.

Никитин А.В. Вопросы оптимального составления учебных планов и программ. Дисс. ... канд. тех. наук. Москва, 1969. 179 с.

Никитин А.В., Романкова Л.И., Чурсин Н.Н. Построение тезауруса специальности при определении содержания образования. Рукопись депонирована в НИИ ВШ регистр. №185-82.

Овчинников А.А., Пучинский В.С. От логической сети к линейной диаграмме. //Вестник высшей школы, №9, 1968.

Овчинников А.А., Пучинский В.С., Петров Г.Ф. Сетевые методы планирования и организации учебного процесса. М.: «Высшая школа», 1972. 157с.

Оре О. Графы и их применение. Москва, «Мир», 1965. 174 с.

Основы педагогики высшей школы. //Под ред. Белкина Е.Л. М., 1987. 122 с.

Плаксина Н.А. Основные направления совершенствования учебного процесса в свете современных требований к высшей школе. //Актуальные проблемы улучшения подготовки специалистов в университете. Воронеж, 1975, с 3-5.

Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: «Советское радио», 1975. 192 с.

Подиновский В.В., Ногин В.Д. Парето оптимальные решения многокритериальных задач. М.: «Наука», 1982. 254 с.

Применение методов сетевого планирования и управления для организации учебного процесса. М.: Информационный центр МВ и ССО СССР, 1968.

Розенберг Н.М. Проблема измерений в дидактике. М.:ВШ, 1979. 175с.