Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

РАЗРАБОТКА ОБУЧАЮЩЕГО ПРИЛОЖЕНИЯ ПО АЛГОРИТМАМ ОБХОДА ГРАФОВ

Батырева А.Б. 1 Басангова Е.О. 1
1 Калмыцкий государственный университет им. Б.Б. Городовикова
1. Альберт Д., Альберт Е. Macromedia Flash 8 Professional: Справочник дизайнера. – СПб.: БХВ-Петербург, 2006.
2. Басангова Е.О. О разработке электронных пособий, визуализирующих алгоритмы // Проблемы современной науки и образования. – 2016. – №1(43).

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

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

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

Дискретная математика является одним из важных звеньев математического образования. Дискретная математика содержит в себе два аспекта: это основы математики (математическая логика, теория алгоритмов и т.д.), а также это математический аппарат информатики и вычислительной техники. Без использования дискретной математики невозможно создать разнообразные приложения по экономике, технике. Дискретная математика отличается от традиционной математики тем, что использует в работе объекты нечисловой природы: множества, логические высказывания, алгоритмы, графы. Именно это отличие и позволяет распространять математические методы дискретной математики на сферы и задачи, которые далеки от математики. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов – обязательное квалификационное требование в области информатики.

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

Современные мультимедийные технологии позволяют объединить высококачественные изображения со звуковым сопровождением. Наибольшее распространение системы мультимедиа получили в области обучения, рекламы, развлечений. Самой известной мультимедийной платформой компании Adobe Systems для создания веб-приложений или мультимедийных презентаций является Adobe Flash (ранее Macromedia Flash), или просто Flash, которая используется для создания рекламных баннеров, анимации, игр, а также воспроизведения на веб-страницах видео- и аудиозаписей.

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

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

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

bez1.jpg

Рис. 1. Начальные ключевые кадры ролика

bez2.jpg

Рис. 2. Ключевые кадры ролика

bez3.jpg

Рис. 3. Заключительные кадры ролика

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

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

В кадрах 3, 4 строятся ветви дерева.

Демонстрация алгоритма завершается помечиванием последней вершины.


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

Батырева А.Б., Басангова Е.О. РАЗРАБОТКА ОБУЧАЮЩЕГО ПРИЛОЖЕНИЯ ПО АЛГОРИТМАМ ОБХОДА ГРАФОВ // Международный студенческий научный вестник. – 2016. – № 5-2. ;
URL: https://eduherald.ru/ru/article/view?id=15567 (дата обращения: 28.09.2021).

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

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