Научный журнал
Международный журнал экспериментального образования
ISSN 2618–7159
ИФ РИНЦ = 0,839

ОСОБЕННОСТИ ПРИМЕНЕНИЯ ТЕОРИИ ГРАФОВ ПРИ ПРОЕКТИРОВАНИИ ОБРАЗОВАТЕЛЬНОЙ ТРАЕКТОРИИ В ВУЗЕ

Мальтекбасов М.Ж. 1 Прокофьева М.А. 1 Ескендиров Б.Н. 1 Нурбосынова Г.С. 1
1 «Жетысуский государственный университет им. И. Жансугурова»
В статье раскрываются особенности применения теории графов при проектировании образовательной траектории. Разработаны соответствующие различным видам образовательных траекторий математические модели.
образовательная траектория личности
теория графов
математическая модель образовательной траектории.
1. Хаггарти Р. Дискретная математика для программистов. – М.: Техносфера, 2003. – 320с.
2. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер с анг. – М.: Издательский дом «Вильямс», 2003. – 960 с.
3. Оре О. Теория графов. – М.: Мир, 1999.

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

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

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

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

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

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

Однако, эффективный алгоритм решения данной задачи пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального слишком велико. В тоже время существуют алгоритмы поиска субоптимального решения. Субоптимальное решение необязательно даст цикл минимального общего веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов. Алгоритм ближайшего соседа выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством вершин V. Цикл, полученный в результате работы алгоритма, будет совпадать с конечным значением переменной маршрут, а его общая длина — конечное значение переменной w.

Этот способ удобно использовать при проектировании образовательной траектории непрерывного образования, повышения квалификации, составления расписания занятий, то есть в тех случаях, когда порядок «посещения» не играет никакого значения. В случае же направленных ребер, когда четко описана взаимосвязь и порядок посещения поиск оптимального решения в графе будет затрудненным. Кроме того при проектировании подобным образом предполагается, что осуществляется последовательное прохождения через вершины, т.е. подобный граф является цепью. Однако при детализации до уровня учебных дисциплин мы получаем эффект «одновременного присутствия в различных городах», так в течении семестра студенты параллельно изучают в среднем 7-8 дисциплин. Кроме того «обязательное посещение» относится только к базовым дисциплинам, предусмотренным ГОСО РК специальности, и не применимо к выборности элективных дисциплин.

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

Еще одним классом графов, используемых при моделировании образовательных процессов и явлений, является класс, называемый деревья. Деревья являются естественной моделью, представляющей данные в иерархическую систему. Граф G=(V,T) с n вершинами и m ребрами называется деревом, если он связан и ацикличен (не содержит циклов). Этот вид графа определяют следующие необходимые и достаточные условия: любая пара вершин в графе соединена единственным путем, граф связен и m= n-1, удаление хотя бы одного ребра нарушает связность графа, ацикличен, но добавление хотя бы одного ребра приводит к появлению цикла.

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

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

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

1) нахождению составителями ГОСО и типового учебного плана специальности в нагруженном подграфе обязательных дисциплин образовательной программы остовного дерева наименьшего веса (минимального остовного дерева);

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

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

4) дополнения студентом графа новыми вершинами, т.е. учебными предметами, удовлетворяющими личные образовательные потребности.

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

Для моделирования ситуаций, в которых есть отношения частичного порядка между объектами используются ориентированные графы (орграфы). Возникающие при этом схемы используются для моделирования информационных потоков, сетевого планирования и планирования заданий. Для такого планирования и руководства разработками используется система PERT (Program Evaluation and Review Technique). Так же системой ПЕРТ (PERT) называется в задаче о планировании заданий соответствующий бесконтурный граф. Существование путей устанавливается с помощью матриц достижимости, одним из эффективных алгоритмов достижимости является алгоритм Уоршелла. Для поиска кратчайшего пути в сетях традиционно используется алгоритм Дейкстры. Под сетью понимается направленный математический граф, моделирующий совокупность и последовательность логически связанных работ, объединенных общей целью. Событие сетевого графика представляет собой факт завершения какого-либо процесса, получение определенного результата. При представлении проектируемой траектории образовательной программы студента недопустимо появление тупиковых вершин, из которых не выходят стрелки, хотя указанные вершины не являются завершающимися. Появление подобного логического тупика свидетельствует либо о «забытой» разработчиками графа учебных дисциплин связи, либо о том, что учебная дисциплина, соответствующая этой связи, не нужна для формирования профессиональной компетентности по данной специальности. Т.е. в данном случае наблюдается несоблюдение принципа систематичности и последовательности.

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

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

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

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

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


Библиографическая ссылка

Мальтекбасов М.Ж., Прокофьева М.А., Ескендиров Б.Н., Нурбосынова Г.С. ОСОБЕННОСТИ ПРИМЕНЕНИЯ ТЕОРИИ ГРАФОВ ПРИ ПРОЕКТИРОВАНИИ ОБРАЗОВАТЕЛЬНОЙ ТРАЕКТОРИИ В ВУЗЕ // Международный журнал экспериментального образования. – 2014. – № 1-1. – С. 102-105;
URL: https://expeducation.ru/ru/article/view?id=4526 (дата обращения: 28.09.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074