МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ Государственное автономНОЕ образовательное
учреждение высшего образования
«Новосибирский НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ государственный университет»
(нОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ)
Факультет Механико-математический
Кафедра Программирования
Направление подготовки Математика и компьютерные науки
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА МАГИСТРА
Васильева Оксана Вадимовна
(Фамилия, Имя, Отчество автора)
Тема работы: Встраивание системы расписания университета в образовательный процесс
«К защите допущена» Научный руководитель
Заведующий кафедрой, к.ф.-м.н., с.н.с.,
д.ф.-м.н., профессор зав. лаб. ИСИ СО РАН
.
Марчук А.Г /________ Бульонков М.А. /__________
(фамилия , И., О.) (подпись, МП) (фамилия , И., О.) (подпись, МП)
«…»………………20…г. «…»………………20…г.
Дата защиты: «…» ……………20…г.
Новосибирск, 2017
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ………………………………………………………….………….…4
ГЛАВА 1. Структура расписания…………………………….………….…….…6
1.1. Планирование расписания занятий………………….…….………...……6
1.1.1. Учебный план и назначения…………………..…………………........7
1.1.2. Критические разделяемые ресурсы………………..……….………...7
1.1.3. Время………………………………………………..…...……......……8
1.2. Структура учебного заведения…………………………...…………….....9
1.2.1. Учебные корпуса и аудитории…………………………….……...…..9
1.2.2. Факультеты и студенческие группы………………………..…...….10
1.2.3. Кафедры, преподаватели и учебные дисциплины………….….…..10
ГЛАВА 2. Используемые методы и сравнение с аналогами …………………..12
2.1. Постановка задачи………………………………………………..…..…..12
2.2. Технологическая цепочка и описание принципа работы…….…………14
2.3. Сравнение с аналогами………………………………………………...…16
ГЛАВА 3. Реализация поиска …………………………………………..……….22
3.1. Лексический этап реализации…………………………...……………….23
3.1.1. Расстояние Дамерау-Левенштейна……………………………….…23
3.1.2. Метод триграмм………………………………………….......………25
3.2. Семантический этап реализации……………………………………..….26
3.2.1. Граф объектов расписания…………………………………….…….26
3.2.2. Уравнение теплопроводности………………………………….……29
3.2.3. Разностная схема для уравнения теплопроводности…….......……30
3.2.4. Алгоритм распространения приоритетов по графу………….……33
Заключение……………………………………………………………...….…….35
Публикации………………………………………………………………………36
Список литературы……………………...…………………….………...……….37
ВВЕДЕНИЕ
Система высшего образования и организация научных исследований является основой процесса развития экономики любого государства, а это, в свою очередь, определяет цивилизационный уровень, политическую и национальную независимость. По этой причине любой стране, претендующей на достойное место в современном мире, необходима национальная система высшего образования.
Качество подготовки специалистов в значительной степени зависит от методически правильно составленного расписания учебных занятий. Одним из критериев организации учебного процесса является доступность к расписанию преподавателей, студентов, учебно-вспомогательного состава и специалистов учебно-методического отдела.
Поскольку мы живем в веке информационных технологий, последняя задача может быть решена путём создания клиент-серверного приложения, реализующего удобный пользовательский интерфейс, а также которое будет предоставлять средства функционального поиска и представления информации о расписании занятий в удобном для пользователя виде. Ключевым моментом здесь является направленность данного приложения
на мобильные устройства.
Основное внимание уделяется методам поиска информации. Главная задача - реализация нечеткого поиска, т.е. поиска, допускающего некоторое количество ошибок в исходном запросе. При этом результаты поиска должны наиболее точно отвечать запросу пользователя в семантическом смысле.
Таким образом, реализация поиска разбивается на 2 этапа: лексический и семантический. Первый этап реализует возможность допущения некоторого количества ошибок в исходном запросе, используя алгоритм, основанный на полном переборе (подсчет расстояния Дамерау-Левенштейна между словами), и алгоритм индексированного нечеткого поиска (метод триграмм). На втором этапе используется алгоритм распространения информации по графу, тем самым обеспечивается адекватность и релевантность поисковому запросу пользователя.
Данная работа подробно описывает вышеизложенные этапы поиска, а также средства, используемые в работе, и структуру веб-приложения.
ГЛАВА 1. Структура расписания
В любом учебном заведении существует набор логических понятий, которые используются для организации учебного процесса. Для описания этих понятий должна быть создана специальная модель, с которой в дальнейшем будет удобно работать при составлении расписания занятий.
В данной выпускной квалификационной работе за основу была взята модель учебного заведения, подробно описанная в статье [1].
Все объекты данной модели можно разбить на две группы:
объекты планирования, которые непосредственно участвуют в составлении расписания;
объекты описания структуры учебного заведения.
Планирование расписания занятий
Объекты планирования являются наиболее важными с точки зрения составления расписания. К ним относятся:
учебный план и назначения;
критические разделяемые ресурсы;
время.
Далее эти понятия описываются более подробно.
1.1.1. Учебный план и назначения
Учебный план определяет состав учебных дисциплин, которые изучаются в данном учебном заведении в рамках определенного направления подготовки, а также их распределение по годам в течение всего срока обучения. Исходя из учебного плана, строится расписание занятий. Расписание занятий представляется в виде назначений. Назначением называется объединение студентов-слушателей, преподавателя (одного или несколько) и аудитории (одной или несколько) для проведения занятия, описанного в учебном плане, на определённый промежуток времени.
При этом на назначения могут быть наложены следующие виды ограничений:
временные ограничения (могут быть связаны либо с заданной учебным планом периодичностью, либо с санитарными требованиями к организации учебного процесса, либо с ограниченностью разделяемых ресурсов);
пространственные ограничения (указывается либо перечень желаемых мест (зданий или аудиторий), либо наоборот – недопустимых).
1.1.2. Критические разделяемые ресурсы
Критический разделяемый ресурс – это ресурс, который может быть назначен только одному событию в конкретный момент времени.
В описываемой модели выделены три основных вида ресурсов:
Преподаватели. Поскольку преподаватели могут вести занятия на разных факультетах или совмещать работу в исследовательском институте и преподавание в учебном заведении, то данный вид ресурсов, как правило, имеет большое количество ограничений.
Аудитории. Аудитории различаются по вместимости и функциональной принадлежности (лекционные, семинарские), а также наличию специального оборудования (компьютеров, проекторов и пр.) и закрепленности за кафедрами и факультетами.
Студенты. Студенты объединяются в студенческие группы. Студенческие группы, в свою очередь, могут быть объединены или разбиты на подгруппы. Такие подгруппы называются коллекциями слушателей. Коллекция слушателей является удобным инструментом описания аудиторного состава для каждого занятия.
1.1.3. Время
Время занятия описывается посредством задания дня недели, номера пары, учебной недели, с которой начинается данный предмет, периодичности и общего количества занятий за семестр.
Следует отметить, что в современных системах составления расписания ключевым моментом является наличие возможности гибкого указания продолжительности и периодичности занятий. Это связано с тем, что в современном учебном процессе возможны занятия с относительно небольшим общим количеством часов (специальные лабораторные занятия, выступления приглашенных лекторов и т.д.), а также присутствует блочная организация учебных курсов с произвольными временными интервалами.
1.2. Структура учебного заведения
В учебно-административную структуру учебного заведения входят:
Учебные корпуса;
Кафедры;
Факультеты.
1.2.1. Учебные корпуса и аудитории
Каждый учебный корпус состоит из набора аудиторий. Каждая аудитория характеризуются вместимостью и типом. Вместимость аудитории играет важную роль во время принятия решения о назначении занятия в данную аудиторию. Достаточность мест для проведения занятия определяется с учетом численности коллекции слушателей. Тип аудитории определяет возможные виды занятий (лекционные, семинарские и т.д.), проводимых в ней, а также наличие специального оборудования (компьютеры, проектор, специальные установки для опытов).
1.2.2. Факультеты и студенческие группы
Учебное заведение подразделяется на факультеты, которые осуществляют подготовку студентов по одному или нескольким направлениям подготовки, а также руководят деятельностью выпускающих кафедр.
В рамках факультета студенты объединяются в студенческие группы. Каждая группа характеризуются понятием численности, т.е. количеством человек, входящих в неё формально. Также группа может обладать набором ограничений, которые свидетельствуют об отсутствии возможности у студентов группы находиться в заданное время в заданном месте по некоторым причинам. На этапе назначения занятий данный фактор учитывается.
1.2.3. Кафедры, преподаватели и учебные дисциплины
Основу каждой кафедры составляет её преподавательский состав и набор преподаваемых учебных дисциплин. Причем преподаватель может работать как с одной кафедрой, так и совмещать работу на нескольких кафедрах. Еще может случиться, что дисциплину, закрепленную за конкретной кафедрой, ведет преподаватель с другой кафедры, не являясь при этом внутренним совместителем. Данная модель подразумевает возможность описания подобных случаев.
Для администрирования учебного процесса и составления отчётов может потребоваться довольно большое количество информации о преподаватели различного рода (полное имя, инициалы, контактная информация, учёная степень и т.д.), поэтому эти данные тоже следует учитывать при проектировании расписания занятий.
Представленная модель может быть реализована, например, в виде XML-файла, где в качестве элементов выступают объекты, описанные в данной модели (факультеты, кафедры, преподаватели, группы, аудитории, предметы и др.), а атрибутами являются их характеристики, зависящие от вида самого объекта (например, имя, id, день недели, периодичность и др.). Формат XML обеспечивает удобство обмена данными между компонентами модели и предоставляет широкий набор средств манипулирования данными.
ГЛАВА 2. Используемые методы и сравнение с аналогами
2.1. Постановка задачи
Расписание занятий любого учебного заведения является важной составляющей его образовательного процесса. Согласно положению о государственной аккредитации образовательной деятельности, любое высшее учебное заведение обязано обеспечить представление расписания своих учебных занятий в некотором виде. По этой причине визуализация расписания учебных дисциплин и обеспечение доступа к нему являются актуальными проблемами.
У каждого вуза имеется свой подход к представлению своего расписания. Например, оно может быть организовано в виде документов Microsoft Excel, Microsoft Word, XML-файла, также может иметь вид всевозможных таблиц, представленных на сайте конкретного вуза, и др. Может существовать возможность посмотреть расписание занятий на соответствующем сайте или же скачать его в некотором доступном формате.
Все эти подходы имеют право на существование, но всегда следует помнить, что какое-то представление расписания занятий может оказаться более удобным, нежели другое.
В условиях современного мира расписание может подвергаться многочисленным изменениям и, вообще говоря, представляет собой динамическую структуру. Ввиду этого факта, оно должно быть максимально доступно для студентов, преподавателей, а также людей, по какой-либо причине им интересующихся.
Решением данной проблемы может стать создание клиент-серверного приложения, предоставляющего доступ к расписанию занятий конкретного вуза.
Требования, предъявляемые к этому приложению, следующие:
оно должно быть ориентировано на мобильные устройства;
быть максимально удобным и простым в использовании;
предоставлять точное расписание занятий студентов и преподавателей в соответствии с учебным планом;
включать в себя средства функционального нечёткого поиска;
выдавать результаты поиска, релевантные поисковому запросу (схожие с ним по смыслу);
предоставлять возможности подписки на новости студенческих групп и создания уведомлений для них;
иметь возможность предоставления дополнительной информации о студентах и преподавателях.
Данное веб-приложение должно решить проблему доступности и стать наиболее удобным в использовании для студентов, преподавателей и других пользователей.
2.2. Технологическая цепочка и описание принципа работы
Одной из задач диспетчера высшего учебного заведения является составление расписания занятий студентов и преподавателей этого вуза. Диспетчер формирует расписание с учетом личных пожеланий преподавателя, графика учебного процесса, учебной нагрузки групп, аудиторного фонда данного учебного заведения.
После того, как расписание занятий составлено, его нужно конвертировать в XML-формат в рамках модели, описанной в первой главе.
Это требуется для дальнейшего эффективного обращения к его логическим понятиям, которые будут использованы в ходе работы программы. Здесь следует отметить, что работа диспетчера по составлению расписания и создание вышеупомянутого XML-файла являются автономными единицами в данном процессе, то есть диспетчеру не нужно иметь представление о структуре данного файла и, тем более, не нужно подстраивать свою работу под его ограничения и формат. Более того, диспетчер может даже не знать о существовании самого файла.
Далее, XML-файл подается на вход программе, которая заполняет соответствующие таблицы в существующей базе данных. В данной работе для взаимодействия с базой данных используется СУРБД Microsoft SQL Server 2012, а программа, заполняющая таблицы, написана на языке программирования C#. Наличие базы данных облегчает восприятие исходных элементов, а также требуется для организации поиска по ним. Объекты таблиц связаны между собой отношениями и, таким образом, образуют некую онтологию как набор объектов и связей между ними. Структура таблиц очень схожа со структурой исходного XML-файла, где в качестве названий столбцов выступают названия атрибутов этого файла.
После того, как все требуемые таблицы построены, начинает работу программа, написанная на языке программирования C# и использующая технологию ASP.NET, основная задача которой заключается непосредственно в формировании требуемого веб-приложения.
Программа подключается к базе данных и на основе информации, содержащейся в ее таблицах, выводит расписание занятий на экран, а также дополнительную информацию о студентах и преподавателях.
Рис.1. Технологическая цепочка
На рис.1 представлена полная схема взаимодействия функционирующих элементов по созданию требуемого веб-приложения.
2.3. Сравнение с аналогами
Основным ориентиром при создании веб-приложения служило электронное расписание Новосибирского государственного университета, представленное на сайте http://www.nsu.ru/education/sched/. Следует отметить, что на указанном сайте отсутствуют какие-либо средства поиска информации, что усложняет работу с данными, а подача самого расписания ориентирована на настольные компьютеры. Просматривать расписание с мобильного устройства весьма неудобно, поскольку на экране телефона все таблицы становятся маленькими из-за их горизонтальной структуры, вследствие чего необходимо приближать интересующую информацию (рис. 2). Для мобильной версии предлагается вертикальная структура таблиц с расписанием, что облегчает наглядность и восприятие информации (рис. 3).
Рис. 2. «Старое» расписание НГУ
Рис. 3. Мобильное расписание НГУ
Второй ориентир - другой сайт с расписанием НГУ: http://table.nsu.ru/. Он имеет более современный вид и предоставляет необходимые средства для поиска. Но поиск не допускает наличия ошибок в исходном запросе, а ищет слова на основе полных совпадений подстрок. И, аналогично предыдущему сайту, с ним неудобно работать с экрана мобильного телефона по той же причине (рис. 4).
Рис. 4. Альтернативное расписание НГУ
Ещё существует мобильное приложение «Расписание вузов» для студентов, преподавателей и университетов. Оно послужило третьим ориентиром и, в некотором роде, примером в создании описываемого в данной работе мобильного приложения.
Особенностью данного приложения является то, что оно реализует расписание не для одного конкретного вуза, а предоставляет возможность выбирать вуз самостоятельно (рис. 5). Также в нем имеются некоторые функциональные возможности в виде добавления заданий, установки напоминаний, добавления в избранное и др. (рис. 6). Расписание занятий групп представлено в удобном формате и расписано по неделям (рис. 7).
 
Рис. 5. Выбор университета Рис. 6. Функции приложения
Рис. 7. Расписание группы
Недостатками данного приложения являются несвоевременное обновление данных и полное отсутствие информации о студентах. Поиск в приложении присутствует, но тоже, как и в предыдущем приложении, не допускает ошибок и присутствует только на отдельных страницах (например, на странице выбора факультета).
Особенностью описываемого в данной работе мобильного приложения является наличие поиска, предоставляющего возможность искать информацию сразу по нескольким сущностям, присутствующим в высшем учебном заведении. Например, по запросу «Иванов» поиск будет выдавать в качестве результата и студента Иванова и преподавателя с такой же фамилией.
Главная страница мобильного приложения выглядит следующим образом:
Рис. 8. Главная страница
Здесь существует возможность переходить по кнопкам «Преподаватели», «Группы» или «Кафедры» и искать интересующий объект вручную, либо можно воспользоваться поиском, об описании и реализации которого речь пойдет в следующей главе.
ГЛАВА 3. Реализация поиска
Как уже отмечалось ранее, в качестве поисковой информации выступают объекты типа «Студент», «Преподаватель», «Кафедра» и «Группа». При этом поиск является нечётким, т.е. допускает некоторое количество ошибок в исходном запросе.
Реализация поиска разбивается на лексический и семантический этапы.
Лексический этап заключается в нахождении множества слов, наиболее похожих на слова из поискового запроса в лексическом плане. Реализуется посредством применения двух алгоритмов:
алгоритм, основанный на подсчёте расстояния Дамерау-Левенштейна между словами;
метод разбиения слов на триграммы.
Под семантическим этапом подразумевается построение графа, отражающего связи между объектами расписания, и дальнейшее распространение информации по заданному графу с целью нахождения объекта, наиболее точно отвечающего исходному запросу пользователя по смысловой нагрузке. При этом распространение происходит согласно закону распространения тепла в заданной области. Для этого строится явная разностная схема для уравнения теплопроводности в случае произвольного графа.
Рассмотрим приведенные этапы более подробно.
3.1. Лексический этап реализации поиска.
3.1.1. Расстояние Дамерау-Левенштейна
Расстоянием Дамерау-Левенштейна называется мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и транспозиции (перестановки двух соседних символов), необходимых для перевода одной строки в другую. Является модификацией расстояния Левенштейна: к операциям вставки, удаления и замены символов, определенных в расстоянии Левенштейна, добавлена операция транспозиции (перестановки) символов. Также расстояние Дамерау-Левенштейна иногда называют редакционным расстоянием.
Для подсчета расстояния между двумя словами заполняется таблица, представленная на рис. 9.
Рис. 9. Таблица для подсчета расстояния Дамерау-Левенштейна
Сначала заполняются первая строка и первый столбец (от 0 до числа, характеризующего длину слова). Такое заполнение соответствует количеству операций вставки по сравнению с пустым словом. Далее, заполняем оставшиеся ячейки, согласно следующему правилу:
Рис. 10. Правило заполнения ячеек
В итоге, нас интересует только значение правой нижней ячейки в таблице, которое и является расстоянием Дамерау-Левенштейна между исходными словами. Чем меньше это число, тем больше сходство между словами. Соответственно, «ноль» характеризует полное совпадение слов.
Этот алгоритм довольно активно применяется для исправления ошибок в словах, но и обладает довольно существенным недостатком: для выборки наиболее похожих слов с исходным словом приходится перебирать все слова в словаре и считать расстояние для каждого из них. Это весьма неэффективно, и занимает порядочный промежуток времени.
Для решения данной проблемы предлагается сначала сузить объем слов, а потом к суженному набору применять алгоритм, основанный на вычислении расстояния Дамерау-Левенштейна. Сделать это можно, например, посредством применения метода триграмм.
3.1.2. Метод триграмм
Последовательность из трёх элементов называется триграммой.
Опишем принцип этого метода.
Все слова, содержащиеся в словаре, разбиваются на триграммы следующим образом: слово разбивается на последовательность подстрок, состоящих из трёх символов, начинающихся с каждой буквы слова, по порядку. Например, для слова «ветка» такой последовательностью триграмм является « **в *ве вет етк тка ка* а** ».
В итоге, получаем конечное число всевозможных триграмм, поскольку слов в словаре тоже конечное число.
Далее, индексируем слова полученными триграммами, т.е. для каждой триграммы составляем список слов, в которых она содержится. Таким образом, разбив поисковый запрос на триграммы, мы будем иметь и список всевозможных слов, в которых эти триграммы присутствуют. Причем, не перебирая все слова в словаре. Такой подход значительно сокращает время работы программы и позволяет значительно сузить объем слов, по которым производится сравнение с исходным поисковым запросом.
Рис. 11. Сужение словаря при исходном запросе «Петров»
3.2. Семантический этап реализации поиска.
3.2.1. Граф объектов расписания.
Семантический этап заключается в нахождении объектов, наиболее адекватно отвечающих поисковому запросу пользователя по смысловой нагрузке.
Например, если пользователь ввёл запрос «Петров ММФ», то программа должна в списке результатов первыми выдать всех Петровых, которые учатся на механико-математическом факультете, а следом выдавать всех остальных.
На лексическом этапе этот вопрос не решается, так как все слова в базе данных на этом этапе равнозначны, и связи между объектами не учитываются. Поэтому ответом на приведенный запрос могли бы стать любые Петровы, вне зависимости от того, на каком факультете они учатся; и слова, схожие со словом «ММФ». И такой результат на лексическом этапе являлся бы корректным.
Семантический этап решает данную проблему посредством построения графа объектов расписания, где в качестве вершин выступают объекты поиска, а в качестве рёбер – отношения между этими объектами. Отношения бывают двух типов:
прямое отношение или принадлежность одного объекта другому (например, студент принадлежит данной группе);
косвенное отношение или отношение закрепления за объектом (например, преподаватель ведёт занятие у данной группы)
Рис. 12. Граф объектов расписания
На рис.12 прямые отношения обозначены сплошными линиями, косвенные – пунктирными линиями.
Каждой вершине графа зададим свой приоритет. Это свойство будет обозначать адекватность поисковому запросу по смысловой нагрузке, то есть насколько высоко в списке результатов расположится тот или иной объект. Причем, чем больше данный показатель, тем объект будет находиться выше.
Значение приоритета для i-ой вершины высчитывается по следующей формуле:
 – слово, соответствующее i-ой вершине. Заметим, что у вершины может быть несколько слов (например, если вершина является объектом типа «Студент», то она сдержит в себе 3 слова: фамилию, имя и отчество);
 – длина слова;
 – расстояние Дамерау-Левенштейна, которое уже было посчитано на лексическом этапе.
Таким образом, после вычисления приоритетов, получим граф с «подогретыми» вершинами, т.е. вершинами, у которых приоритет больше нуля.
Далее, будем трактовать полученный граф как некий физический объект, распределяя значения приоритетов «подогретых» вершин между их ближайшими соседями. В качестве алгоритма распространения будем использовать уравнение теплопроводности.
3.2.2. Уравнение теплопроводности
Уравнение теплопроводности описывает распределение температуры в заданной области пространства и ее изменение во времени.
В пространстве с произвольной системой координат  r = ( r 1 , … , r n ) {\displaystyle \mathbf {r} =(r_{1},\ldots ,r_{n})} уравнение теплопроводности следующий вид:
где функция  задает температуру в точке с координатами x в момент времени t;
 – коэффициент температуропроводности, характеризующий скорость изменения температуры вещества;
 - оператор Лапласа;
 - функция тепловых источников.
В пространстве с декартовыми координатами  уравнение теплопроводности принимает вид:
Стоит отметить, что если от внешних источников не поступает тепла, т.е.  , то такая система называется теплоизолированной, а уравнение теплопроводности – однородным.
3.2.3. Разностная схема для уравнения теплопроводности
Основной пункт построения разностной схемы - замена области непрерывного аргумента некоторым конечным множеством точек, покрывающим эту область. Это множество является областью определения функции дискретного аргумента и называется разностной сеткой.
При этом функции дискретного аргумента называются сеточными функциями, сами точки – узлами сетки, а расстояние между ними - шагом сетки.
Рис.13. Разностная сетка для одномерного случая
На рис.13 можно увидеть пример разностной сетки для одномерного случая с шагом  по времени и h – по пространству. Данная сетка является прямоугольной при  , равномерной по x и t (поскольку  ,  ) и регулярной, так как при любом значении n (или i) число узлов по i (или n) одинаково.
Таким образом, если  - точное решение в исходной области, то  - приближенное решение, причем в узлах сетки эти значения совпадают.
При построении разностной схемы частные производные аппроксимируются конечными разностями для сеточных функций, которые строятся в соответствии с формулами численного дифференцирования.
Тогда явная разностная схема для уравнения теплопроводности в одномерном случае будет выглядеть следующим образом:
Рис.14. Шаблон явной разностной схемы для уравнения теплопроводности в одномерном случае
Причем для того, чтобы при малых изменениях шага сетки решение не сильно изменялось, нужно потребовать выполнения условия устойчивости схемы:
В случае графа, вообще говоря, разностная сетка не обязана быть равномерной и регулярной. В общем случае, у разных вершин может быть разное количество соседних вершин.
Введём следующие обозначения:
 - значение приоритета i-ой вершины на n-ом слое;
 - значения приоритетов всех соседей i-ой вершины на n-ом слое.
Рис.15. Обозначения вершины графа и её соседей
Тогда разностная схема для уравнения теплопроводности в случае произвольного графа будет иметь следующий вид:
где – коэффициент температуропроводности;  - шаги по времени и по пространству соответственно.
3.2.4. Алгоритм распространения приоритетов по графу
Опишем работу алгоритма распространения приоритетов по графу.
На вход алгоритму подаётся построенный граф объектов расписания со значениями приоритетов каждой вершины. Причем заметим, что объекты, в которых встречаются слова, отобранные на лексическом этапе, имеют ненулевой приоритет; приоритеты всех остальных объектов инициализированы нулём.
Далее, алгоритм начинает итеративно распространять приоритеты «подогретых» вершин по их ближайшим соседям посредством использования разностной схемы для уравнения теплопроводности в случае произвольного графа. Таким образом, исходный приоритет заданной вершины меняется, изменяя при этом приоритеты соседей.
На завершающем этапе, после того как было проделано определённое количество итераций, происходит сортировка всех объектов по убыванию приоритета. Отсортированное множество отдаётся пользователю в качестве результата его поискового запроса.
Таким образом, если вернуться к примеру с запросом «Петров ММФ», можно заметить, что на семантическом этапе реализации поиска наиболее «нагретые» изначально вершины «Петров» и «ММФ» будут подогревать друг друга при распространении приоритетов, не оставляя возможности Петровым с других факультетов появиться в результирующем списке выше первых, так как значения приоритета у последних будет меньше.
Заключение
В ходе выпускной квалификационной работы была разработана общая структура веб-приложения и схема его взаимодействия с существующим программным обеспечением. Также был спроектирован и реализован пользовательский интерфейс, ориентированный на мобильные устройства, и реализованы средства нечёткого поиска, позволяющие искать информацию по смыслу.
Помимо этого, были реализованы возможности подписки студентов на новости конкретной группы и создания преподавателями оповещений для студентов. При создании оповещений преподаватель должен ввести текст оповещения и выбрать список групп, которых он хотел бы оповестить. При этом оповещение отправляется на почту тем студентам, которые подписались на новости хотя бы одной из выбранных преподавателем групп. Более того, предполагается, что создавать оповещения могут только те преподаватели, которые заранее занесены в базу данных. Сделано это для избегания рассылки спама недобросовестными пользователями.
Также была написана программа, визуализирующая распространение приоритетов по графу.
Данная работа была представлена на международной научной студенческой конференции 17 апреля 2017 года.
Публикации
Материалы 55-й Международной научной студенческой конференции
МНСК-2017: Математика / Новосиб. гос. ун-т. – Новосибирск: ИПЦ НГУ,
2017. – 216 с.
Список литературы
[1] Бульонков М.А., Емельянов П.Г., Пак Е.В., Харенко А.А. Моделирование данных в задаче составления расписаний в высших учебных заведениях. // Программная инженерия. 2013. № 1. С. 33-41.
[2] Бульонков М.А., Емельянов П.Г., Пак Е.В. К стандартизации описания учебного процесса в учебных заведениях. // Открытое образование. – № 3, 2010. – С. 45-57.
[3] Донецков А.М. Автоматизированное проектирование на примере программы «Расписание». // «Вопросы радиоэлектроники» сер.ЭВТ, вып.4, М., 2010
[4] Нечёткий поиск в тексте и словаре. // URL: http://habrahabr.ru/post/114997/
[5] Реализация нечеткого поиска. // URL: http://habrahabr.ru/post/123320/
[6] Метод динамического программирования Вагнера и Фишера. //
URL: http://algolist.manual.ru/search/lcs/vagner.php
[7] Официальный сайт Microsoft MSDN. //
URL: https://msdn.microsoft.com/ru-ru/
[8] Электронный учебник по HTML и CSS. // URL: http://htmlbook.ru/
[9] Официальный сайт НГУ. // URL: http://www.nsu.ru/
[10] Разностные методы решения уравнений в частных производных. //
URL: http://csc.sibsutis.ru/sites/default/files/courses/pvt/Section5.pdf
[11] Численные методы. В. Г. Пименов, А. Б. Ложников. //
URL: http://elar.urfu.ru/bitstream/10995/31219/1/978-5-7996-1342-6_2014.pdf
|
