АНАЛИЗ ПИРАМИД ОПТИМАЛЬНОЙ СЛОЖНОСТИ
Объект исследования: пирамида Бродала, её основные операции и принципы работы.
Результаты, полученные лично автором: собраны материалы в английском сегменте интернета, разработана программа, проанализированы результаты тестирования.
Пирамида Бродала - это структура данных, позволяющая выполнять операции decrease_key, insert и meld (merge) со сложностью О(1) и delete_min со сложностью O(log n). Данная структура была разработана Г. Бродалом в 1995 году. Её создание было призвано решить проблему поиска структуры данных, обладающей оптимальной сложностью выполнения операций. Вопрос оптимизации процессов обработки данных и сейчас остаётся одним из важнейших вопросов IT-индустрии. Применение пирамиды Бродала может способствовать более эффективному решению отдельных задач оптимизации, многих сетевых задач и усовершенствованию пирамидальных сортировок. Пирамида Бродала считается достаточно сложной структурой данных, русскоязычных публикаций, рассматривающих данную пирамиду, на данный момент нет, что затрудняет знакомство со структурой на ранних этапах. Поэтому детальный анализ и систематизация имеющейся информации, проделанные в рамках данной работы, должны помочь желающим разобраться с этой структурой данных.
Пирамида строится в строгом соответствии со следующими правилами:
• Каждый узел имеет ключ меньший, чем у его потомков (пирамидально упорядоченное дерево).
|
|
|
• Каждый узел имеет не более одного специального потомка, который может быть произвольного ранга, а также ряд нормальных потомков, ранг которых меньше, чем ранг узла. (Под рангом здесь и далее понимается расстояние от узла до ближайшего конечного списка нормальных потомков)
• Нормальные потомки расположены в порядке возрастания ранга в двусвязном списке. Ранги нормальных потомков узла n удовлетворяют следующим свойствам:
1. Каждый ранг меньше ранга n появляется, по крайней мере один раз, и не более трех раз.
2. Между двумя рангами, которые появляются по три раза, есть ранг, который появляется только один раз.
3. Перед первым рангом, который появляется три раза, есть ранг, который появляется только один раз.
• Для каждого узла первые потомки каждого ранга, который появляется три раза, расположены в связанном списке в порядке возрастания.
• Корень имеет ранг 0.
Реализованная на программном уровне на основе этих, а так же некоторых специальных для операций merge и delete_min требований структура данных позволила провести ряд сравнительных экспериментов. В результате этих экспериментов были подтверждены заявленные временные показатели. Кроме того, сравнение с показателями некоторых других пирамид продемонстрировало оптимальность применения пирамиды Бродала в ряде тестов.
|
|
|
В результате анализа пирамиды Бродала были выявлены её характерные черты и особенности выполнения операций, позволяющие достичь оптимальных показателей. Это легло в основу первой открытой русскоязычной публикации, рассматривающей данную структуру данных.
Таким образом, было выяснено, что пирамида Бродала обладает оптимальной сложностью выполнения операций в сравнении с рядом схожих структур. В дальнейшем планируется провести более глубокий анализ с целью выявления областей применения данной пирамиды и составления рекомендаций к взаимодействию с ней.
Материал поступил в редколлегию 03.04.2017
УДК 004.75
Е.В. Нешков
Научный руководитель: заведующий кафедрой «Информатика и программное обеспечение», к.т.н., доцент А.Г. Подвесовский
djakson32@mail.ru
ИССЛЕДОВАНИЕ МЕХАНИЗМОВ ВЗАИМОДЕЙСТВИЯ КЛИЕНТСКОЙ И СЕРВЕРНОЙ ЧАСТЕЙ В СИСТЕМЕ РАСПРЕДЕЛЕННОГО УПРАВЛЕНИЯ ОБЪЕКТАМИ АВТОМАТИЗАЦИИ
Объект исследования: механизмы удаленного управления технологическим процессами.
Результаты, полученные лично автором: разработано приложение, позволяющее осуществлять удаленный мониторинг технологического процесса с возможностью его корректировки (программная реализация).
|
|
|
Активное развитие информационных технологий в современном обществе постепенно приводит к тому, что любой технологический процесс, с точки зрения рационализации, нуждается в автоматизации. Различное устаревшее по сегодняшним меркам оборудование заменяется на более современное. Более того, любая автоматизация, которая хотя бы частично исключает участие человека в технологическом процессе, приводит к снижению травматичности, уменьшению вероятности аварии или отказа техники в связи с человеческим фактором.
Одна из задач, возникающих в рамках автоматизации технологических процессов, заключается в удаленном мониторинге и внесении корректировок в действующий на предприятии процесс. С этой целью необходимо разработать автоматизированную систему управления, которая должна обеспечивать понятность и открытость предоставляемых данных, простоту конфигурирования, а также отказоустойчивость и безопасность. Данная система должна поддерживать свою работоспособность вне зависимости от количества единиц обслуживаемого оборудования, а также должна быть независимой от выхода из строя взаимодействующего с ней любого стороннего аппаратного комплекса. Систему, отвечающую данным меркам, можно отнести к так называемым распределенным системам управления.
|
|
|
Распределенные системы управления представляют из себя набор программного обеспечения, где его составляющие имеют свою четко детерминированную роль. Каждая единица программного комплекса выполняет различную вычислительную деятельность, позволяющую производить мониторинг и возможные манипуляции над аппаратным оснащением удаленной станции, подвергнувшейся автоматизации. Чтобы связать указанные сущности, можно рассмотреть общую модель взаимодействия «клиент-сервер», однако, в данную модель также необходимо добавить дополнительную сущность – источник/приемник данных (рис. 1), в роли которого будет выступать оборудование, управляющее технологическим процессом.
Рис. 1. Модель клиент-сервер (дополненная)
Обобщенная архитектура предлагаемого программного комплекса представлена на рис. 2.
Рис. 2. Обобщенная архитектура программного комплекса
Программный комплекс представляет собой объединение трех серверных приложений, взаимодействующих как единое целое с клиентским программным обеспечением. Клиентское приложение представляет собой графическое приложение, обеспечивающее мониторинг и корректировку технологического процесса. Сервер верификации отвечает за аутентификацию пользователей, а также обеспечивает шифрование дешифрование данных. Сервер обработки обеспечивает формирование пакетов данных, запрошенных клиентом. Наконец, сервер по работе с удаленным оборудованием отвечает за взаимодействие со встроенными регистрами данного оборудования.
Помимо управления технологическими процессами, одним из возможных вариантов применения программного комплекса является его использование в условиях стационарного лечебного учреждения, когда о состоянии больных можно наблюдать на экране монитора, и, в случае экстренной ситуации, оперативно принимать решение, чтобы оказать помощь пациенту.
Материал поступил в редколлегию 20.04.2017
УДК 004.4
Е.В. Николаенко
Научный руководитель: доцент кафедры «Информатика и программное обеспечение», к.т.н., Д.И. Булатицкий
bulatizkydi@mail.ru
РАЗРАБОТКА МОДУЛЯ ОПОВЕЩЕНИЙ В СИСТЕМЕ МОНИТОРИНГА УСПЕВАЕМОСТИ СТУДЕНТОВ И ПОСЕЩАЕМОСТИ ЗАНЯТИЙ "СУП"
Объект исследования: процесс учета успеваемости и посещаемости студентов.
Результаты, полученные лично автором: модуль оповещений для системы мониторинга успеваемости студентов и посещаемости занятий "СУП".
В Брянском Государственном Техническом Университете ведется разработка программного комплекса мониторинга посещаемости занятий и успеваемости студентов (СУП). Основным интерфейсом СУП является веб-приложение, которое позволяет просматривать сведения о посещаемости занятий и успеваемости студентов.
Чтобы пропуск занятий студентом или задолженности по практическим занятиям не несли за собой серьезных последствий, необходимо вовремя уведомить об этом родителей. Во многих случаях эта мера позволяет предотвратить дальнейшие прогулы и нормализовать успеваемость студента. Чем быстрее произойдет уведомление, тем быстрее ситуация начнет исправляться. По ряду очевидных причин, родители не могут контролировать ребёнка ежеминутно, проверять все выполненные задания, а также следить за посещением занятий. Родителям крайне сложно проявлять ежедневную инициативу, по проверке посещаемости и успеваемости студентов, что может повлиять на итоговый результат.
В предыдущих работах автора предложено сместить точку инициативы на сторону электронной системы мониторинга успеваемости и посещаемости. Система будет оповещать о значимых событиях, останется лишь подписаться на интересующие события. В качестве таких событий выделим следующие:
• пропуск занятия по неуважительной причине;
• не сдача лабораторной работы в срок;
• получение неудовлетворительной оценки (оценки ниже заданного порога);
• выставление аттестации.
Для отправки оповещений о пропуске занятия, если ведомость подписали в этот же день, целесообразно использовать SMS или push-уведомления. Email-уведомления предпочтительнее использовать для оповещений, которые связанны с оценками. Например, в течении занятия студент может улучшить оценку по лабораторной. О таких событиях лучше уведомлять в конце дня. Пользователю предоставляется выбор способа рассылки уведомлений, для каждого типа событий. В данной работе более подробно рассматривается реализация отправки данных сообщений.
Отправка сообщений будет происходить путем обращения к API SMS-интегратора. В качестве основных альтернатив для выбора SMS-интегратора на данный момент являются sms.ru и smsc.ru. Отправка оповещений через SMS позволяет доставить их максимально оперативно, а также охватить практически всю аудиторию заинтересованных лиц. Вместе с тем, для функционирования данной модели оповещений необходимы денежные затраты.
Не меньшую оперативность доставки обеспечивают push-уведомления, их отправка не связана с дополнительными расходами, но к минусам данного способа можно отнести сокращение аудитории, ведь для приема push-уведомлений необходим смартфон и установленное на него приложение, которое планируется к разработке в рамках комплекса СУП. Первая версия данного приложения будет способна лишь демонстрировать уведомления. В приложении предлагается использовать Firebase Cloud Messaging (FCM). FCM – кроссплатформенное API от Google, с помощью которого можно рассылать уведомления на различные платформы. Просмотр данных и взаимодействие с ними, будет реализовано в последующих версиях.
Наиболее простым в реализации каналом отправки уведомлений является email-уведомления. Данный канал отправки будет реализован первым, им можно дублировать, либо полностью заменить, каналы уведомлений, о которых упоминалось ранее. Почтой удобно отправлять не только короткие сообщения, о конкретных событиях, но также ежедневные, еженедельные и другие отчеты, которые могут содержать гораздо больше данных.
Для отправки сообщений в ASP.NET удобно использовать класс SmtpClient и вспомогательные классы MailAdress и MailMessage.
Оповещения, которые должны рассылаться после определенных событий в системе, будут реализованы посредством фильтров действий в MVC. Фильтры действий – это механизм в ASP.NET MVC, который позволяет не добавлять код в метод контроллера, а добавить дополнительный функционал методу. Методами, для которых нужно будет применять данный фильтр, являются:
• подписание ведомости посещения занятия преподавателем или куратором;
• подписание аттестационной или сессионной ведомости куратором;
• подписание экзаменационной ведомости преподавателем или куратором.
Другой тип оповещений, который рассылается по времени, будет реализован с помощью сервиса Windows. Данный сервис запускается в фоновом режиме и может выполнять периодические действия. В конце дня, такой сервис может отправлять уведомления, связанные с событиями требующие окончания дня. Например, срок лабораторной работы истекает в конце дня.
Материал поступил в редколлегию 13.04.2017
УДК 004.4
А.В. Осипенкова
Научный руководитель: ассистент кафедры «Информатика и программное обеспечение», Е.В. Коптенок
osipenkova@yandex.ru
Дата добавления: 2018-10-27; просмотров: 258; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!