Содержание к диссертации
Введение
Глава 1. Обзор задач контроля результатов обучения с помощью виртуальных лабораторий в современных электронных курсах 10
1.1 Нормативные положения контроля результатов обучения в современном высшем образовании 10
1.2 Массовое электронное обучение и автоматизированные инструменты контроля результатов обучения 12
1.3 Виртуальные лаборатории и технологии их разработки 18
1.4 Классификация виртуальных лабораторий 23
1.5 Задачи применения виртуальных лабораторий в электронных курсах 28
Выводы 40
Глава 2. Универсальная модель распределенной электронной информационно образовательной среды, основанная на протоколе RLCP и обеспечивающая автоматическое оценивание составных результатов обучения 41
2.1 Среда управления виртуальными лабораториями 41
2.2 Порядок выполнения упражнения с помощью виртуальной лаборатории...45
2.3 Обеспечение безопасного функционирования виртуальных лабораторий ...48
2.4 RLCP - протокол управления сервером виртуальной лаборатории 54
2.5 Спецификация программных интерфейсов виртуального стенда и кадра упражнения 70
2.6 Требования к инструментам поддержки и разработки RLCP-совместимых виртуальных лабораторий 79
Выводы 81
Глава 3. Проектирование RLCP-совместимых виртуальных лабораторий для алгоритмических упражнений с помощью автоматной модели эталонного алгоритма 83
3.1 Особенности применения алгоритмических упражнений в виртуальных лабораториях 83
3.2 Автоматная модель эталонного алгоритма 85
3.3 Оценивание решений вариативных алгоритмических упражнений с помощью автоматной модели эталонного алгоритма 94
3.4 Формальное определение сложности вариантов алгоритмических упражнений с помощью автоматной модели эталонного алгоритма 97
3.5 Функции сложности и проектирование параметризованных алгоритмов построения вариантов алгоритмических упражнений 98
3.6 Учет коллизий при определении сложности вариантов алгоритмических упражнений, проектировании алгоритмов оценивания и составления вариантов 102
3.7 Применение автоматной модели эталонного алгоритма для проектирования виртуальных лабораторий на примере упражнения поиска минимального маршрута в графе с помощью алгоритма Ли 103
3.8 Применение автоматной модели эталонного алгоритма для проектирования виртуальных лабораторий на примере упражнения определения изоморфизма графов с помощью локальных характеристик 111
Выводы 117
Глава 4. Внедрение результатов исследования 118
4.1 Реализация компонентов среды управления RLCP-совместимыми виртуальными лабораториями 118
4.2 Средства разработки RLCP-совместимых виртуальных лабораторий 153
4.3 Методика проектирования и разработки RLCP-совместимых виртуальных лабораторий 164
4.4 Итоги внедрения среды управления виртуальными лабораториями и инструментов разработки 175
4.5 Способ применения RLCP-совместимых виртуальных лабораторий на платформе Open edX 177
4.6 Примеры разработки RLCP-совместимых виртуальных лабораторий 181
Выводы 221
Заключение 224
Список источников 226
- Массовое электронное обучение и автоматизированные инструменты контроля результатов обучения
- Обеспечение безопасного функционирования виртуальных лабораторий
- Формальное определение сложности вариантов алгоритмических упражнений с помощью автоматной модели эталонного алгоритма
- Средства разработки RLCP-совместимых виртуальных лабораторий
Введение к работе
Актуальность темы исследования. Развитие дистанционных образовательных технологий и электронных ресурсов для их реализации привело к тому, что возник новый тип электронных информационно-образовательных сред (ЭИОС): платформы для массовых открытых онлайн-курсов (MOOCs – Massive Open Online Courses). В этих средах электронные и дистанционные средства обучения и оценивания результатов обучения (РО) составляют основу всего курса. Перед авторами MOOCs встает задача массового оценивания составных РО, для которых в традиционном обучении применяют практические упражнения, в том числе и с неразрешимым множеством решений. Для решения этой задачи электронные тесты не подходят, поэтому авторы вынуждены прибегать к взаимному оцениванию слушателями курса решений друг друга или строить сложные информационные системы для автоматического оценивания РО. Одним из инструментов оценивания является виртуальная лаборатория (ВЛ), которая представляет собой электронную среду, позволяющую создавать и исследовать в интерактивном режиме модели систем и процессов. Применение ВЛ в учебном процессе способствует повышению качества и доступности образования, однако разработка самих ВЛ остается сложной и трудоемкой задачей.
Настоящее исследование предлагает системный подход к организации ЭИОС, обеспечивающей автоматическое оценивание составных РО с помощью ВЛ. Ключевыми особенностями предложенного подхода является стандартизация структуры и программного интерфейса автоматических ВЛ (АВЛ) и централизованный контроль над применением ВЛ в практических упражнениях. Это позволяет рассматривать ВЛ как небольшие подключаемые модули ЭИОС, предложить методы и средства их проектирования, разработки и внедрения, что ведет к снижению трудозатрат на их изготовление и применение. В связи с этим тема исследования является актуальной.
Цель диссертации заключается в разработке и реализации модели распределенной ЭИОС, обеспечивающая автоматическое оценивание составных результатов обучения с помощью ВЛ. Для достижения поставленной цели были решены следующие задачи:
– обзор и анализ подходов к разработке ВЛ, составление классификации ВЛ по архитектурным и методическим признакам, составление требований для АВЛ;
– разработка модели распределенной ЭИОС, обеспечивающей автоматическое оценивание с помощью АВЛ, разработка соответствующих спецификаций и протоколов взаимодействия;
– разработка метода проектирования АВЛ для алгоритмических упражнений на основе автоматной модели эталонного алгоритма;
– реализация и внедрение разработанной модели распределенной ЭИОС.
Положения, выносимые на защиту, обладающие научной новизной.
В работе получены следующие новые научные результаты, которые выносятся на защиту.
– Универсальная модель распределенной электронной
информационно-образовательной среды, основанная на протоколе RLCP и обеспечивающая автоматическое оценивание составных результатов обучения.
– Метод проектирования RLCP-совместимых ВЛ с пошаговой верификацией решений для алгоритмически определенных упражнений, основанный на автоматной модели эталонного алгоритма.
Методы исследования. В работе использованы методы теории алгоритмов, теории автоматов, теории информационных процессов и систем, теории вероятностей и математической статистики.
Достоверность научных результатов и выводов подтверждается корректным использованием методов исследования, обоснованием постановок задач и используемых критериев, положительными результатами применения полученных результатов, а также обсуждением на многочисленных конференциях и публикацией статей в рецензируемых изданиях.
Теоретическая значимость работы обусловлена развитием методов и средств автоматического оценивания составных РО в электронном обучении, применением моделей теории автоматов в области проектирования автоматических программных средств оценивания составных РО.
Практическая значимость работы заключается в сокращении трудозатрат на проектирование, разработку и внедрение автоматических инструментов оценивания составных РО в виде ВЛ, что способствует расширению возможностей авторов MOOCs.
Внедрение результатов работы. Результаты диссертации использованы при выполнении следующих научно-исследовательских работ: НИУ(2011)/3.1.20.12 «Разработка виртуальных лабораторий и тренажеров информационно-образовательной среды», НИУ(2012)/3.1.22.3 «Методика использования среды тестирования RLCP-совместимых виртуальных лабораторий», НИР № 610454 «Разработка интеллектуальных технологий управления, навигации и обработки информации с применением к мобильным робототехническим системам и комплексам», НИР № 615864 «Разработка методов и технологий управления и обработки информации для сложных динамических систем».
Результаты исследования легли в основу среды управления RLCP-совместимыми ВЛ в системе AcademicNT. Разработанные в рамках исследования средства и методы проектирования, разработки и внедрения ВЛ применяются при изготовлении ВЛ для электронных курсов в AcademicNT, что позволило существенно сократить трудозатраты на их разработку.
Результаты исследования использованы в учебном процессе кафедры компьютерных образовательных технологий (КОТ) Университета ИТМО. Они составили основу для лабораторного практикума и курсового проектирования
по дисциплине «Технология разработки виртуальных лабораторий», а также для подготовки выпускных квалификационных работ по направлению 09.03.02 (230400.62) «Информационные системы и технологии».
RLCP-совместимые ВЛ применяются в электронных курсах Университета ИТМО, ФГБОУ ВО ПСПбГМУ им. И. П. Павлова Минздрава России, стали основой практических упражнений для следующих MOOCs, размещенных на Национальной платформе открытого образования (НПОО): «Методы и алгоритмы теории графов», «Линейные электрические цепи», «Функциональное программирование», «Физическая оптика», «Модели и методы аналитической механики».
Апробация работы. Основные результаты работы докладывались на следующих научных и научно-практических конференциях:
– Всероссийском конгрессе молодых ученых – Санкт-Петербург,
2011-13; – Всероссийской научно-методической конференции «Телематика» –
Санкт-Петербург, 2011-13; – Международной научно-практической конференции «Новые информационные технологии в образовании» – Екатеринбург, 2012-13; – Международной конференции «Применение новых технологий в
образовании» – Троицк, 2012; – Международной конференции «The International Conference on
E-Learning and E-Technologies in Education» – Лодзь, Польша, 2012;
– Международной научно-практической конференции
«Информационная среда ВУЗа XXI века» – Куопио, Финляндия, 2012; – Международной конференции «International Conference on e-Learning e-Education and Online Training» – Новедрате, Италия, 2015; Дублин, Ирландия, 2016; – Международной конференции «International Conference on Application of Information and Communication Technologies» – Ростов-на-Дону, 2015; – Международной конференции «International Conference on Smart
Education and E-Learning» – Тенерифе, Испания, 2016. Публикации. Список научных трудов по теме диссертационного исследования содержит 23 публикации, из них восемь – в изданиях из перечня ВАК.
Личный вклад автора. Решение задач диссертации, разработанные модели, методы и их реализация принадлежат лично автору.
Структура диссертации. Диссертация изложена на 241 странице и состоит из введения, пяти глав и заключения. Список литературы содержит 123 наименования. Работа иллюстрирована 102 рисунками и 18 таблицами.
Массовое электронное обучение и автоматизированные инструменты контроля результатов обучения
Развитие дистанционных образовательных технологий [47,48] и электронных ресурсов [10, 12, 67-71, 42] для их реализации привело к тому, что возник новый тип электронных информационно-образовательных сред. В последние годы в мире произошла настоящая революция, характеризуемая аббревиатурой MOOC (Massive Open Online Courses)[95, 96], которая поставила новые задачи по модернизации информационно-образовательных сред и систем электронного обучения на основе открытых онлайн-курсов [74, 75]. В этих средах произошел переход от использования электронных, дистанционных образовательных технологий в качестве вспомогательных средств при традиционном обучении, уже прочно вошедшего в педагогическую практику на всех уровнях образования, и особенно для подготовки студентов в вузах Российской Федерации к легко масштабируемым онлайн-курсам, в которых электронные и дистанционные средства обучения и контроля составляют основу всего курса [82-85]. Такие курсы в основном независимым друг от друга и доступны всем желающим.
Возникновение платформ MOOCs, тенденции развития открытого и дистанционного образования, массовость современного образования, требование объективности педагогических измерений, предъявляют повышенные требования к процессу контроля результатов обучения [92-94].
Традиционные формы контроля, основанные на экспертных оценках результатов обучения, обладают рядом недостатков с точки зрения применения их в современных электронных информационно-образовательных средах и массовых образовательных курсов. Например, на устном экзамене классифицирующие понятия («отлично», «хорошо», «удовлетворительно» и др.) определяются субъективно с помощью суждений экзаменатора и содержат в себе, как правило, значительный ошибочный компонент. Поскольку эти суждения принимаются за оцениваемые характеристики объектов, то их надо уметь распознавать, отождествлять, сравнивать, абстрагировать и обобщать. Для удобства оценочные суждения выражают в виде некоторых баллов по традиционной пятибалльной шкале или по любой другой, которая выбирается на основе экспертных соглашений. Приписываемые числа могут быть не вполне определенны в тех случаях, когда для построения качественных шкал не используются измерители. Например, при традиционном контроле у каждого преподавателя есть свои представления о том, за что нужно ставить ту или иную оценку [43]. Из этого следует, что сравнивать оценки студентов, полученные от разных экзаменаторов, не следует из-за возможной несогласованности их мнений о правилах оценивания. На самом деле, даже один и тот же экзаменатор может по-разному оценить одинаковый ответ в зависимости от времени, места, особенностей ситуации или личности экзаменуемого.
Другим существенным недостатком традиционных форм контроля, является сложность осуществления [82]. Действительно, для проведения собеседования, защиты лабораторной или практической работы или экзамена, как правило, каждый студент должен явиться в указанное место в указанное время подготовленным, дождаться своей очереди для беседы с экзаменатором. Экзаменатор же вынужден провести беседу с каждым студентом. Все это требует значительных временных и материальных затрат, не связанных напрямую с оценкой результатов обучения. В случае же, когда эксперт проверяет работы студентов заочно, результат проверки оказывается доступен студентам лишь спустя значительное время.
Эти свойства традиционных форм обучения и контроля результатов обучения и новые появившиеся требования привели к формированию задачи автоматизации процесса контроля результатов обучения.
В настоящее время в образовании используется широкий спектр электронных средств автоматизации процессов обучения и аттестации [83-86]. Эти средства могут быть подразделены на несколько типов, различающихся назначением и методическими и архитектурными особенностями. Ниже приведено описание некоторых из таких типов электронных средств, которые могут быть включены в состав электронного УМК.
Электронные тесты – тесты, хранимые, обрабатываемые и предъявляемые тестируемому с помощью компьютерной и телекоммуникационной техники. Компьютерными не являются тесты, подразумевающие заполнение тестируемыми «бумажных» бланков и их последующую компьютерную обработку.
Электронные тесты созданы для автоматизации аттестации. Существуют и обучающие тесты, но они обычно направлены на подготовку обучающегося к аттестующему тестированию, знакомя его с видами заданий и правилами прохождения тестирования. Так, например, в руководстве по разработке электронного УМК для электронной информационно-образовательной среды AcademicNT [99] выделено следующее: «Основная задача электронных тестов – промежуточная и итоговая аттестация студентов и предварительная подготовка к ней. Система аттестующего и обучающего тестирования является одной из основных и наиболее методически отработанных подсистем в системе AcademicNT.»
Электронные тесты достаточно просты для реализации, содержатся в большинстве систем дистанционного обучения и, как правило, являются основой аттестационных средств электронных курсов. Применение электронных тестов имеют длительную историю. Электронные тесты направлены на проверку знаний испытуемого. Оценить умения и навыки с их помощью сложно. С помощью электронного теста невозможно и приобрести практические умения и навыки, особенно в рамках самостоятельной работы студентов.
Электронные конспекты представляет собой организованную совокупность страниц и кадров, содержащих учебную информацию [58]. В отличие от обучения с использованием традиционных учебников, обучение с использованием качественного электронного учебника или электронного конспекта становится нелинейным, адаптивным и, возможно, более эффективным [59]. Современный персональный сетевой компьютер предоставляет дополнительные возможности (гипертекстовое изложение материала, качественные графические иллюстрации, анимация, аудиофрагменты, видеоролики), используя которые можно вывести процесс обучения, и в частности работу с электронным конспектом, на совершенно новый уровень.
Набор электронных конспектов, безусловно, не может заменить традиционные формы изложения и изучения материала, но специфика организации материала в электронном конспекте, его структурированность и многослойность позволяет обучаемому самому выбирать траекторию обучения.
Электронные тренажеры предназначены для отработки практических умений и навыков. Такие средства особенно эффективны для обучения действиям в условиях сложных и даже чрезвычайных ситуаций при отработке противоаварийных действий [57]. Электронные тренажеры сложны для реализации, поэтому встречаются достаточно редко.
Электронные тренажеры используется для формирования и закрепления практических навыков, отработки умений. К моменту использования электронного тренажера испытуемый уже должен обладать необходимыми для решения задач умениями, что снижает эффективность такого решения в качестве средства организации самостоятельной работы студентов. Еще одним недостатком электронного тренажера является то, что он не предназначен для аттестации. Визуализатор – программа, иллюстрирующая выполнение алгоритма при определенных исходных данных. Визуализаторы сложны для реализации без использования специальных конструкторов, изготовление которых является темой отдельных исследований [11, 13, 18-22, 24-29].
В качестве примера можно привести проект «Computer Algorithm Tutor» [98] кафедры компьютерных технологий (КТ) Университета ИТМО. Существует инструмент для быстрого создания визуализаторов, и представлена библиотека построенных визуализаторов. Проект используется для обучения методам дискретной математики на кафедре КТ.
Обеспечение безопасного функционирования виртуальных лабораторий
Основным бизнес-процессом среды управления виртуальными лабораториями является выполнение практического упражнения. Модуль управления испытаниями поддерживает порядок этого процесса, а остальные модули выполняют вспомогательные функции выполнения упражнений: взаимодействуют с модулями лаборатории, предоставляют, сохраняют данные.
На рисунке 2.2 представлена диаграмма последовательности взаимодействия компонентов виртуальной лаборатории, среды управления и обучающегося в процессе выполнения упражнения. Взаимодействие компонентов среды управления виртуальными лабораториями опущено за исключением компонента кадра упражнения – ключевая особенность этого компонента состоят в том, что только этот компонент отдается под внешний контроль обучающегося и что для каждой сессии выполнения упражнения создается отдельный экземпляр кадра упражнения, связанный именно с ней. Из-за этих особенностей правила поведения кадра упражнения в рамках бизнес-процесса выполнения упражнения с помощью виртуальной лаборатории специфицируются, в отличие от прочих, скрытых компонентов среды управления виртуальными лабораториями.
При запросе от обучающегося на получение упражнения среда управления виртуальными лабораториями прежде всего проверяет, требуется ли для этого упражнения динамическая подготовка варианта, и при необходимости обращается к RLCP-серверу, передает ему запрос, в котором указываются инструкции для формирования варианта упражнения, и получает от него сгенерированный вариант. Затем она подготавливает и передает обучающемуся кадр упражнения, содержащий описание упражнения и интерактивный элемент виртуального стенда. При инициализации кадр упражнения сообщает виртуальному стенду вариант упражнения, а тот подготавливает отображение варианта для обучающегося, а также создает объект решения упражнения. В процессе выполнения упражнения состояние этого объекта меняется; добавляются данные о совершенных обучающимся действиях. Получив кадр упражнения, обучающийся может приступить к формированию решению упражнения.
В процессе выполнения упражнения обучающийся может задействовать функции виртуального стенда, требующие выполнения промежуточных вычислений, которые не могут выполнены виртуальным стендом, поскольку в этом случае он как публичный модуль виртуальной лаборатории содержал бы алгоритмы или данные, которые разработчик виртуальной лаборатории хотел бы скрыть от обучающегося. В этом случае виртуальный стенд обращается к кадру упражнения с требованием выполнить запрос на выполнение промежуточных вычислений RLCP-сервером виртуальной лаборатории. Это требование передается среде управления виртуальными лабораториями, которая подготавливает и отправляет соответствующий запрос RLCP-серверу и получает от него результат промежуточных вычислений. Затем среда управления виртуальными лабораториями возвращает полученный результат кадру упражнения, который, в свою очередь, отправляет его в виртуальный стенд, а тот обновляет свое состояние, чтобы отобразить результат для обучающегося.
Когда обучающийся выполнил выданное ему упражнение, он сообщает об этом с помощью управляющих элементов кадра упражнения, тот запрашивает решение обучающегося у виртуального стенда и отправляет его на проверку среде управления виртуальными лабораториями, после чего завершает выполнение виртуального стенда и закрывает кадр упражнения. Получив решение обучающегося, среда управления виртуальными лабораториями упаковывает решение обучающегося, проверяющие наборы данных и прочие параметры для его проверки в запрос и отправляет его на RLCP-сервер виртуальной лаборатории. RLCP-сервер осуществляет оценивание решения обучающегося, исходя из заданных параметров, и возвращает результат оценивания среде управления виртуальными лабораториями, которая сообщает обучающемуся о полученной оценке.
При реализации описанного выше бизнес-процесса выполнения упражнения с помощью ВЛ требуется учесть возможные уязвимости, которые могут привести к несанкционированному доступу, подмене данных или другим нежелательным ситуациям, могущим повлечь сбои в работе среды управления виртуальными лабораториями или самих виртуальных лабораторий.
Бизнес-процесс выполнения упражнения с помощью виртуальной лаборатории можно разбить на три этапа: – подготовительный: составление (при необходимости) варианта, выдача упражнения, инициализация кадра упражнения; – составление решения: обучающийся взаимодействует с виртуальным стендом, а тот при необходимости составляет запросы на выполнение промежуточных вычислений; – заключительный: составленное обучающимся решение отправляется на оценивание.
Осуществление контроля за выполнением упражнения со стороны среды управления виртуальными лабораториями – необходимое условие для предотвращения появления уязвимостей. Такой контроль можно осуществлять, регистрируя сессии выполнения упражнения для каждого обучающегося и для каждого выданного упражнения. Далее описаны основные возможные уязвимости на каждом из этапов и способы их предотвращения с помощью введения правил управления данными сессий.
На подготовительном этапе основная возможная уязвимость состоит в том, что обучающийся может раз за разом отправлять запросы на получение нового упражнения, пытаясь получить все возможные варианты упражнений, или получить вариант полегче остальных, или искусственно создать излишнюю нагрузку на СУВЛ или RLCP-сервер с целью вывода их из строя. Среда управления виртуальными лабораториями при обращении обучающегося за новым упражнением должна предварительно проверить, есть ли в текущий момент у обращающегося обучающегося текущая сессия выполнения этого упражнения. Если такая сессия есть и она на текущий момент не завершена, то нет необходимости в создании нового варианта — достаточно выдать данные предыдущего варианта, не создавая новой сессии выполнения лабораторной работы. Применив также текущие ограничения по времени, среда управления виртуальными лабораториями подготавливает кадр упражнения и виртуальный стенд в том же состоянии, в каком был подготовлен и оригинальный кадр упражнения для этой сессии выполнения упражнения. Кроме того, сохранение предыдущих сессий выполнения этого упражнения позволяет ограничивать количество доступных обучающемуся попыток выполнения упражнения. Это позволяет исключить как опасность получения одним обучающимся большого количества вариантов, так и лишнюю нагрузку на RLCP-сервер, связанную с автоматическим составлением вариантов упражнений. Учет количества попыток выполнения упражнения позволяет также ограничивать их количество или ввести правила оценивания, зависящие от количества использованных попыток, стимулируя обучающегося к отказу от перебора вариантов упражнения.
В случае, если обучающийся не исчерпал попытки и у него нет текущей незавершенной сессию выполнения упражнения, следует такую сессию создать, зафиксировав в ней упражнение, данные его варианта, время начала выполнения упражнения и прочие связанные с управлением бизнес-процессом выполнения упражнения данные.
Формальное определение сложности вариантов алгоритмических упражнений с помощью автоматной модели эталонного алгоритма
Однако программный интерфейс должен быть совместим со средой управления виртуальными лабораториями. Как было сказано выше, виртуальный стенд работает под контролем кадра упражнения — специальной страницы, содержащей текст упражнения и виртуальный стенд, а также некоторые элементы управления и вспомогательные инструменты, например, кнопки для сообщения среде управления виртуальными лабораториями о завершении выполнения упражнения, таймер, показывающий, сколько времени отведено на упражнение и сколько осталось на текущий момент. Кадр упражнения является компонентом среды управления виртуальными лабораториями и отвечает за поддержку взаимодействия обучающегося, виртуального стенда и компонентов среды управления виртуальными лабораториями. Технологические решения при реализации среды управления виртуальными лабораториями определяют точные спецификации протоколов работы и программных интерфейсов виртуального стенда и кадра упражнения, однако для соблюдения порядка выполнения упражнения с помощью виртуальной лаборатории, описанного в разделе 2.1, требуется, чтобы эти программные интерфейсы содержали ряд функций, назначение которых описывается в этом разделе.
Как сказано выше, виртуальный стенд работает под контролем кадра упражнения. Более того, развертывание (отображение графического интерфейса для обучающегося) виртуальный стенд должен производить только по команде кадра упражнения, поскольку перед этим может понадобиться сообщить виртуальному стенду какие-то дополнительные данные и параметры. Таким образом для сообщения команды для развертывания виртуальный стенд должен содержать специальную функцию. Для удобства дадим ей специальное название «Развертывание».
В случае, если упражнение в виртуальной лаборатории предполагает вариативность, виртуальный стенд должен поддерживать отображение варианта упражнения. Предварительно полученный от RLCP-сервера вариант упражнения передается кадру упражнения, который подает его в виртуальный стенд при развертывании. Виртуальный стенд меняет свое состояние в соответствии с данными варианта. Например, во многих виртуальных лабораториях для упражнений по теории графов виртуальный стенд должен отобразить интерактивный граф, используемый в варианте, при этом, например, пометив некоторые вершины или ребра с помощью цвета или расставив веса, если граф является взвешенным. Таким образом, программный интерфейс виртуального стенда должен содержать функцию для установки варианта упражнения. Для удобства дадим ей специальное название «Установка варианта».
Часть виртуальных лабораторий предусматривает выполнение некоторых промежуточных вычислений на RLCP-сервере. О том, в каком случае нужно обращаться за такими вычислениями, заботится разработчик виртуальной лаборатории, поэтому именно виртуальный стенд, реагируя на определенные действия обучающегося, сообщает кадру упражнения о необходимости выполнения промежуточных вычислений на RLCP-сервере. Кадр упражнения получает условия для проведения вычислений и передает их дальше в среду управления виртуальными лабораториями. Когда среда возвращает результат, кадр упражнения возвращает его в виртуальный стенд. Весь этот процесс происходит асинхронно, без повторной инициализации кадра упражнения или развертывания виртуального стенда. В качестве примера можно привести виртуальную лабораторию «Cyber-Net», в которой обучающиеся пишут программы в соответствии с выданным упражнением. В качестве промежуточных вычислений производится компиляция и выполнение программы на RLCP-сервере виртуальной лаборатории. При этом передаются также и указание используемого языка программирования, а также входной набор данных, определяемый обучающимся. Результат выполнения или возникшие ошибки выводятся в виртуальном стенде в соответствующем окне. Поскольку источником события в данном случае служат действия обучающегося, способ, с помощью которого виртуальным стендом регистрируется необходимость проведения промежуточных вычислений на RLCP-сервере виртуальной лаборатории, не подлежит спецификации внешнего программного интерфейса виртуального стенда. С другой стороны, для выполнения вычислений виртуальный стенд должен самостоятельно обратиться к кадру упражнения с соответствующим запросом. Получив от среды управления виртуальными лабораториями результаты вычисления, кадр упражнения должен сообщить о них виртуальному стенду. Для этого придется использовать дополнительную функцию сообщения о результатах вычисления виртуальному стенду, поскольку в противном случае пропадает возможность асинхронной работы виртуального стенда и среды управления виртуальными лабораториями.
Таким образом, программный интерфейс виртуального стенда должен содержать функцию для установки результатов промежуточных вычислений. Для удобства дадим ей специальное название «Сообщение результатов вычислений». Программный интерфейс кадра упражнения также должен содержать специфицированную функцию для выполнения промежуточных вычислений. ля удобства дадим ей специальное название «Выполнение промежуточных вычислений».
Средства разработки RLCP-совместимых виртуальных лабораторий
Обобщенная характеристика такого отношения определяется как Zi, если i = j, и как Oij + Eij 10q, где q – количество десятичных разрядов количества вершин (если в графе восемь вершин, то q = 1, если 324 вершины, то q = 3). Из этих характеристик отношений для каждой упорядоченной пары и составляется обобщенная матрица связности. Строки обобщенных матриц связности представляют собой характеристические вектора соответствующих им вершин. Состав такого вектора определяет локальную характеристику вершины, которая кодируется числом. У вершин с одинаковыми векторами будет одинаковая локальная характеристика.
Если локальные характеристики для графов не совпадают, это означает, что графы не являются изоморфными – алгоритм делает соответствующую пометку в решении C при помощи команды setNoIsoGraphs и завершает работу. В противном случае возможны два варианта. Если каждой вершине в графе соответствует уникальный в рамках графа характеристический вектор, и, соответственно, уникальная локальная характеристика, то говорят, что произошла полная дифференциация. В этом случае графы являются изоморфными, и на основе локальных характеристик находится таблица соответствия (операция обозначена функцией cortab). Фиксация полной дифференциации происходит с помощью функции isMultiSet, которая определяет, является ли множество локальных характеристик графа мультимножеством.
Если полная дифференциация локальных характеристик не достигнута на первом шаге, алгоритм входит в цикл вычисления характеристических матриц (операция обозначена функцией chm). Характеристическая матрица представляют собой набор уточненных характеристических векторов. Уточнение производится на каждой итерации цикла с помощью локальных характеристик, полученных на предыдущем шаге – к обобщенной количественной характеристике отношения вершин i и j дописываются коды локальных характеристик вершин j и i. На основе характеристических матриц вычисляются новые локальные характеристики, после чего итерация завершается. Цикл продолжается до тех пор, пока не будут получены устойчивые характеристические матрицы. Понятие устойчивости характеристических матриц подразумевает, что либо достигнута полная дифференциация, либо вычисление новых матриц не приводит к появлению новых характеристических векторов. Если при этом полученные локальные характеристики графов не совпадают, то алгоритм делает соответствующую пометку о неизоморфности графов и завершает работу. В противном случае графы являются изоморфными. Если произошла полная дифференциация, то с помощью функции cortab строится таблица соответствия. Во втором случае требуется введение дополнительных локальных характеристик. Выбор вершин, для которых вводятся дополнительные характеристики, порождает коллизию, поэтому из решения обучающегося S выбирается информация о совершенном им выборе с помощью запроса getOddLCh. Если выбор совершен согласно требованиям алгоритма, автомат повторяет выбор обучающегося, в противном случае производит выбор самостоятельно. Если после введения дополнительных локальных характеристик дифференциация характеристических векторов не происходит, это означает, имеет место несвязная однородная группа, которая состоит из нейтральных вершин, либо она связана с нейтральными вершинами, поэтому соответствие вершин из этих групп может быть установлено произвольно. Это приводит к еще одной коллизии, для решения которой требуется информация о выборе соответствий вершин, совершенном обучающимся, которую можно получить с помощью запроса getUserCorTab. Если же дифференциация происходит, то автомат возвращается в цикл вычисления характеристических матриц.
В ходе работы автомат воздействует на объект управления, содержащий запись решения, с помощью команд сохранения обобщенных матриц связности (addGCMs), характеристических матриц (addChMs), локальных характеристик (addLChs), таблицы соответствия (addCorTab). На некоторых этапах работы ему требуется получать информацию о локальных характеристиках графов, найденных на предыдущем этапе, для чего используется запрос (getLCh).
Рассмотрим пример решения варианта такого упражнения.
Пусть даны два графа G и H, представленные на рисунке 3.12, для которых требуется определить, изоморфны ли они. Решение представлено на рисунке 3.13. Сначала строим обобщенные матрицы связности и определяем локальные характеристики вершин графов. Очевидно, что оба графа обладают одинаковым набором локальных характеристик, но полная дифференциация не произошла, поскольку у некоторых вершин все локальные характеристики совпадают. Строим характеристические матрицы, чтобы уточнить локальные характеристики. Теперь полная дифференциация достигнута, и можно установить однозначное соответствие вершин графов G и H.
Сложность выполнения действий, заключенных в цикл, одинакова на каждой итерации для каждого из графов, и зависит от количества ребер и дуг в обоих графах. Другим показателем сложности является количество итераций цикла, которое зависит от того, как быстро произойдет переход характеристических матриц в устойчивое состояние