IV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
ТЕОРИЯ ГРАФОВ В УЧЁБЕ И ЖИЗНИ
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Наш мир полон не только букв и цифр, но и самых разнообразных изображений. Это и картины, и всевозможные фотографии, а также многочисленные схемы. Схемы встречаются на логотипах компаний и автомобилей, дорожных знаках и картах. Если посмотреть на схему метро или автобусного маршрута, это всего лишь линии с точками. Подобные схемы из линий (ребер) и точек (вершин) называются графами.
Теория графов появилась благодаря одной занимательной задаче, которую решил Леонард Эйлер. История гласит, что в 1736 году этот блестящий математик остановился в Кенигсберге. Город был разделен рекой на 4 части, соединенные семью мостами. Нужно было определить, можно ли обойти все мосты, пройдя по каждому ровно один раз. Эйлер определил, что решить задачу невозможно [4]. Кенигсбергские мосты были разрушены во время Второй мировой войны, но эта история дала начало красивой математической теории – теории графов.
В XX веке теория графов получила невероятное развитие, она нашла многочисленные применения в задачах планирования, архитектуры, инженерии [5, 6], а особенно в информатике и телекоммуникациях. Графы связаны с комбинаторикой, дискретной математикой, топологией, теорией алгоритмов и другими разделами математики.
Какие же возможности получает ученик, владеющий этой теорией? Сможет ли он достичь каких-то успехов в своей учебе или обычной жизни? Такому исследованию и посвящен данный проект.
Цель проекта: Показать, что методы теории графов дают школьнику инструмент, позволяющий решать сложные олимпиадные задачи, а в жизни – организовывать передачу срочной информации между людьми.
Гипотезы:
С помощью графов можно легко решать многие олимпиадные задачи
Теория графов помогает создать систему срочного оповещения коллектива
Задачи:
Разобраться с методами решения задач при помощи графов
Разработать сайт для тестирования олимпиадных задач
Спроектировать систему Срочного Оповещения Класса при помощи графа
Объекты исследования: олимпиадные задачи, системы оповещения
Предмет исследования: теория графов, web-программирование.
Методы исследований:
методы теории графов
методы web-программирования
План исследований:
Ознакомиться с историей возникновения теории графов
Изучить правила решения олимпиадных задач при помощи графов
Пройти курс «Web-программирование» Школы Информационных Технологий «REAL-IT»
Разработать сайт для тестирования олимпиадных задач по теории графов и опробовать его на друзьях
Спроектировать систему Срочного Оповещения Класса (СОК)
Провести эксперимент с целью тестирования системы СОК
Глава 1. Теория графов в нашей жизни
1.1. Применение теории графов в разных областях
Графы применяются в самых разных областях: при проектировании электрических цепей, телефонных сетей, при поиске маршрутов между населенными пунктами, в экономике [6].
В химии графы используются для представления различных соединений. С помощью графов можно изобразить как простые молекулы, так и довольно сложные органические соединения.
Теория графов играет ключевую роль в различных этапах архитектурных проектов. После того как определены части проекта и перед тем как перейти от эскизов к чертежам, будет полезно построить граф взаимосвязей элементов проекта. Анализ графов в общественных зданиях поможет определить степень доступности различных отделов, расположение помещений (буфета, библиотеки и др.), а также пожарных лестниц. Графы позволяют существенно упростить анализ сложных ситуаций [10].
В наше время благодаря интернету – «сети сетей», связывающей компьютеры по всему миру, стала возможной цифровая революция. Мощность компьютеров неуклонно возрастала, но совершить гигантский скачок к цифровому миру удалось именно благодаря сетям. Графы и телекоммуникации всегда шли рука об руку.
На рисунке 1.1 изображены различные схемы соединения компьютеров между собой. Чаще всего встречаются три способа объединения компьютеров в локальную сеть: "общая шина", "звезда", и "кольцо". Каждой схеме соответствует граф, поэтому применяется термин «Сетевая топология». Сетевая топология - это конфигурация графа, вершины которого: компьютеры и маршрутизаторы, а рёбра – линии связи (кабель) между ними [10]. На рисунке 1.2 все топологии изображены в виде графов.
Дерево – это очень простой граф, в котором между любыми двумя вершинами существует единственный путь. Деревья используются в генетике для иллюстрации родственных связей (генеалогические деревья), а также при анализе вероятностей различных событий.
а б в
Рисунок.1.1. Варианты построения локальных компьютерных сетей
а - общая шина, б - звезда, в – кольцо
а б в
Рисунок 1.2. Варианты построения локальных компьютерных сетей
а - общая шина, б - звезда, в - кольцо
Существует множество игр, в которых нужно построить определенный граф (игры-лабиринты [1, 7]) или с помощью графа определить, существует ли выигрышная стратегия.
GPS, карты и автомобильные маршруты, представленные в интернете, - еще один прекрасный пример использования графов. Ребрами в них являются улицы и автодороги, а вершинами – населенные пункты. Вершины таких графов имеют названия, а ребрам соответствуют числа, обозначающие расстояние в километрах. Таким образом, такой граф является помеченным и взвешенным. Графы помогают наглядно представить себе схемы общественного транспорта, что облегчает планирование поездки.
Графы также применяются в нефтегазовой отрасли в системах транспортировки нефти и газа. С помощью графоаналитических методов газотранспортных систем возможно выбрать из всех возможных путей обхода трубопровода наикратчайший вариант [13].
Развитие информатики привело к тому, что многие математические модели стали использоваться в автоматических процессах. Машина легко справляется с вычислениями, но выбрать наилучший вариант из множества в условиях неопределенности – задача намного более сложная. Появились новые алгоритмы, в которых используются механизмы, напоминающие биологическую революцию. Графы в них используют как способ визуализации процессов. Моделирование нейронов человеческого мозга и принципа их действия легло в основу новой теории – теории нейронных сетей.
1.2. Выводы по главе.
Теория графов нашла свое применение во многих областях науки, техники и повседневной жизни. Однако, несмотря на ее широкое применение в разных областях, в школьном курсе математики ей уделяется лишь поверхностное внимание. В то же время различные эксперименты в сфере образования [10] показывают, что элементы теории графов имеют высокую образовательную ценность, поэтому должны быть включены в школьную программу.
Действительно, школьникам среднего звена весьма полезно будет изучить основы теории графов, поскольку они помогут им в освоении базового курса математики, и особенно – в решении олимпиадных задач по комбинаторике и теории вероятностей [3, 11].
Глава 2. Теория графов в помощь школьнику
2.1. Теория графов в олимпиадных задачах
Различные математические олимпиады, такие как «Кенгуру», «Дино-олимпиада Учи.ру», Международная эвристическая олимпиада «Совёнок», также часто включают задачи по теории графов в разных формулировках [11].
Как известно, дети очень любят все, что связано с компьютерами и интернетом, и их не так просто усадить за стол с книжкой по математике. Для того, чтобы вызвать интерес у школьников к теории графов, авторами статьи на основе пройденных курсов по Web-программированию в Школе информационных технологий «REAL-IT» [9] разработан онлайн-тренажер, включающий тестирование по теории графов, расположенный на странице Тюменской частной школы «Эвольвента»: evolventa-tmn.github.io [2]. Школьникам предлагается решить шесть задач различного уровня сложности, он вводит ответы в окошки, а затем по нажатию кнопки «Готово» выдается результат: количество правильно решенных им задач (Рисунок 2.1).
Рисунок 2.1. Фрагмент экрана сайта с вариантами тестирования
Естественно, хитрый ребенок немедленно начнет искать ответы на поисковых серверах, но точно таких формулировок он не найдет, только подобные, например, на сайте научно-методического электронного журнала «Концепт» [11]. Поэтому для получения вожделенного результата: 6 из 6 задач ученику придется разобраться в общих принципах решения задач с помощью теории графов. А в дальнейшем полученные знания помогут ему успешно решать как школьные, так и олимпиадные задачи.
Когда сайт был полностью готов, протестирован и выложен в Интернет, наши одноклассники получили ссылку на него. Интерес к сайту был велик: судя по счетчику посещений, за первую неделю его посетили больше 150 раз! Многие ребята пытались решить задачи, но они показались им сложными. Даже некоторых родителей, имеющих высшее техническое образование, ряд задач поставил в тупик, это говорит о том, что теория графов изучается даже не во всех высших учебных заведениях. Значит, подготовленное нами тестирование будет полезно не только школьникам, но и взрослым!
2.2. Теория графов при проектировании системы оповещения класса
В настоящее время сфере системы срочного управления персоналом в организациях уделяется большое внимание, в связи с тем, что такие системы играют существенную роль в организации всей деятельности сотрудников [14].
Первоначально системы оповещения и управления эвакуацией были задуманы для срочного информирования работников, персонала и гостей о возгорании в здании, предоставления информации и трансляции важных сведений для быстрой и успешной эвакуации людей [12]. На сегодняшний день такие системы можно наблюдать не только в рамках одной организации или предприятия, но в масштабах всей нашей страны, применяемые в целях повышения безопасности людей.
Необходимо отметить, что большинство используемых систем оповещения ориентировано на взрослых людей. Но самый опасный возраст – это детский. Детям тоже нужны свои системы, позволяющие в кратчайшие сроки оповещать большую часть своих сверстников о надвигающейся опасности или об изменении обстановки.
В школе каждый ребенок проводит значительную часть своего времени: пять - шесть дней в неделю по несколько часов. Поэтому создание системы оповещения детей позволило бы организовать каждого ребенка на быструю и грамотную реакцию на изменившуюся обстановку.
Например, данная система была бы очень полезна при передаче сообщения об опасности, информации о срочном сборе или об изменении обстановки, когда они находятся в разных частях школы или вообще в лесу на отдыхе (Рисунок 2.2)
Рисунок 2.2. Наш класс на экскурсии в ГАУ ДО ТО "Региональный центр допризывной подготовки и патриотического воспитания "Аванпост"
В данной работе предпринята попытка создания Системы Оповещения Коллектива [8] на примере одного класса образовательного учреждения: МАОУ СОШ № 89.
Поскольку дети должны сами распространять информацию, им следует пользоваться только доступными им всем видами связи - мобильной связью. Должен быть оповещен весь списочный состав класса, поэтому для анализа, кто из детей кого из своих друзей готов оповестить, было проведено анкетирование класса. В анкетах изначально было задано ограничение: каждый ребенок успевает позвонить максимум четырем друзьям, а если останется время – еще двоим.
Анкетирование показало довольно высокую активность ребят: в целом по классу будет сделано около 118 звонков. Проанализировать такой объем информации в уме практически невозможно, поэтому было решено воспользоваться информационными технологиями. Модель оповещения коллектива лучше всего представить в виде графа [3, 8]. Ребрами в нем являются звонки (или смс), а вершинами – дети. Поскольку вершины графа имеют названия, а ребрам соответствуют числа, обозначающие вероятность звонка (1 или 0,5), то такой граф является помеченным и взвешенным [10]. Граф помогает наглядно представить себе схему оповещения коллектива, что облегчает моделирование.
Визуализацию графа было решено осуществлять с помощью CASE-средства RAMUS, поскольку он позволяет работать с цветом вершин и ребер, а также позволяет перемещать вершины графа с привязанными к ней ребрами для наглядности. На рисунке 2.3 показан граф системы СОК.
19 ноября 2017 года было проведено тестирование спроектированной системы СОК. Изначально мы планировали, что оповещение пройдет за три круга. Для первого круга (начала оповещения) мы выбрали двух детей, которым никто не хочет звонить, но они звонить готовы, а также самих авторов Проекта (Рис. 2.3, розовые блоки). Дальше информация передается ко второму кругу оповещения (Рис. 2.4, желтые блоки). И на третьем круге оповещения (Рис. 2.4, зеленые блоки) весь класс будет проинформирован. Но в ходе эксперимента мы увидели, что некоторые дети по 1,5-2 часа на тренировке и не смотрят на телефон, другие с отрицательным балансом, поэтому не могут звонить.
Рисунок 2.3. Граф системы оповещения класса
Рисунок 2.4. Круги оповещения системы СОК
Поэтому в реальности наш класс оказался оповещен только за 490 минут [8] - это 8 часов 10 минут. Но зато это были все 100%. Здесь важно то, что наша система имеет структуру не дерева, а графа. А в нем из одной вершины в другую ведут несколько путей, поэтому в любом случае, оповещены будут все!
На рисунке 2.6 показан график оповещенности класса (количество оповещенных человек) в зависимости от времени (в минутах).
Рисунок 2.6. График оповещенности класса
Чтобы было легче следить за оповещенностью, в процессе тестирования дети должны были сообщить авторам Проекта свой любимый предмет, а они вели протокол, когда и кто сообщает информацию.
Еще один результат тестирования – опрос любимых предметов (Рисунок 2.7), показал, что дети нашего класса больше всего любят математику, информатику и подвижные игры! А это значит, что теория графов может им полюбиться так же, как и нам.
Рисунок 2.7. Круговая диаграмма любимых предметов класса
2.3. Выводы по главе.
Нами были проверены обе гипотезы. Разработанный нами сайт для тестирования олимпиадных задач по теории графов помог установить, что ряд олимпиадных задач просто невозможно решить без знаний теории графов, причем, даже взрослым-инженерам. Первая гипотеза получила подтверждение.
Вторая гипотеза также оказалась верной. Спроектированная и протестированная система оповещения коллектива на примере одного класса позволила за 8 часов 10 минут оповестить целый детский коллектив. Путем оптимизации графа можно добиться и более быстрых результатов.
Заключение.
Надеемся, что после знакомства с теорий графов и ее многочисленными применениями в разных областях, в школьниках пробудится интерес к теории графов, и они продолжат изучать этот раздел математики самостоятельно. Результатом изучения будут более высокие результаты на олимпиадах.
Что касается применения теории графов в реальной жизни, актуальность рассматриваемой темы подчеркивает то, что создание системы оповещения детей позволит увеличить скорость передачи срочной информации, охватить большую часть детского коллектива, для которого будет использоваться эта система, сократить время отклика детей, а также обеспечить максимальную безопасность для детского коллектива. Все это указывает на очевидные плюсы внедрения спроектированной системы.
Список литературы
Белобородова А.А. Развитие пространственного мышления при помощи игр-лабиринтов / А.А. Белобородова // «Студенческий научный форум» : материалы VIII Международной студенческой электронной научной конференции.- 2017. https://www.school-science.ru/2017/7/26746
Белобородова, А.А. Разработка web-тренажера для изучения теории графов / А.А. Белобородова, С.В. Пахотин, А.А. Фролов // Новые информационные технологии в нефтегазовой отрасли и образовании: материалы VII Международной научно-технической конференции ; отв. ред. О.Н. Кузяков. – Тюмень : ТИУ, 2017. - С. 156-159.
Белобородова А.А. С математикой не заблудишься! / А.А. Белобородова // XVIII Всероссийский детский конкурс научн.-иссл. и творческих работ «Первые шаги в науке» : сборник тезисов.- М.: НС Интеграция, Государственная Дума ФС РФ, Минобрнауки России.- 2016.- С. 110-111.
Генденштейн, Л.Э. Алиса в стране математики. Повесть-сказка / Для младш. и сред. школьного возраста.- Харьков: Изд.– коммер. предприятие "Паритет" ЛТД, 1994.-288 с., илл.
Давлетшин, М.И. Исследование эффективности методов удаления шумов на изображении / М. И. Давлетшин, К.В. Сызранцева // Энергосбережение и инновационные технологии в топливно-энергетическом комплексе: материалы Межд. науч.-практ. конф. студ., аспир., молодых ученых и спец. Т.1 / отв. редактор А.Н. Халин. - Тюмень: ТИУ, 2016. - С. 25- 29.
Карнаухова, А.А. Использование теории графов при решении задач в экономике / А.А. Карнаухова, А.Ф. Долгополова // Материалы VII Международной студенческой электронной научной конференции «Студенческий научный форум». http://www.scienceforum.ru/2015/991.
Керн, Г. Лабиринты мира. СПб.: Изд-во "Азбука-классика", 2007, 448с.
Краузе, М.В. Применение информационных технологий для проектирования системы оповещения коллектива / М.В. Краузе, А.А. Белобородова, Е.И. Арбузова // Новые информационные технологии в нефтегазовой отрасли и образовании: материалы VII Международной научно-технической конференции ; отв. ред. О.Н. Кузяков. – Тюмень : ТИУ, 2017. - С. 153-156.
Курс «Создание сайтов» Школы Информационных Технологий «REAL-IT» http://it-schools.org/faculties/web/
Мир математики: в 40 т. Т.11: Клауди Альсина. Карты метро и тейронные сети. Теория графов./ Пер. с исп.- М.: Де Агостини, 2014.- 144 с.
Москевич Л. В. Обучающая олимпиада – одна из форм внеурочных занятий математикой / Л.В. Москевич // Научно-методический электронный журнал «Концепт». – 2015. – Т. 6. – С. 166–170. – URL: http://e-koncept.ru/2015/65234.htm.
Памятка населению "Оповещение населения в случае угрозы и возникновении чрезвычайной ситуации" http://47.mchs.gov.ru/document/1306125
Румянцев, В.О. Математическое моделирование газотранспортной системы с помощью теории графов / В. О. Румянцев // Проблемы геологии и освоения недр: сб. науч. тр. / ТПУ. - Томск, 2017. – С. 340 – 342.
Сайт МЧС Российской Федерацииhttp://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves