ВВЕДЕНИЕ 3
1 АНАЛИТИЧЕСКИЙ ОБЗОР 5
1.1 Этапы развития графов 5
1.2 Основные понятия теории графов 12
2 ПОДБОР ЗАДАЧНОГО МАТЕРИАЛЛА, ОПИСАНИЕ МОДЕЛИ ПРИЛОЖЕНИЯ 22
2.1 Анализ учебно-методической литературы курса «Информатика и ИКТ» 22
2.2 Алгоритмы поиска пути в графах 33
2.3 Описание интерфейса 40
3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПРИЛОЖЕНИЯ 51
3.1 Использование теории графов на уроках информатики 51
3.2 Описание программной реализации 54
ЗАКЛЮЧЕНИЕ 59
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 60
ПРИЛОЖЕНИЕ А
Современный этап развития общества характеризуется сильным влиянием на него компьютерных и информационных технологий, которые проникают во все сферы человеческой деятельности.
Теория графов, начало которой было положено Эйлером в его знаменитом рассуждении о Кёнигсбергских мостах (1736 г.), сегодня понятия и утверждения теории графов широко применяется в математике, физике, электронике, экономике, программировании и других научных и прикладных областях. В виде графов можно представлять дороги между населенными пунктами, электрические схемы, строение химических молекул, отношения между людьми и решать разнообразные задачи и головоломки; задания на использование графов содержатся в материалах международных исследований образовательных достижений учащихся PISA [1].
В целом, анализируя учебные программы университетов, можно с уверенностью говорить, что учащиеся физико-математических, механико-математических и других факультетов связанных с изучением математики, активно изучают теорию графов как отдельный курс. Данные курсы помогают освоить многочисленную теорию, связанную с графами, но самое главное они показывают все разнообразие применения графов при решении конкретных задач из реальной жизни. Не смотря на то, что в школьной программе изучение теории графов явно не предусмотрено, некоторые положения теории графов включены в обязательный минимум содержания основных образовательных программ по предмету «Информатике и ИКТ» [3].
Актуальность темы выпускной квалификационной работы определяется тем, что отдельный пласт предлагаемых в школьных учебниках и сборниках задач, заданий из ОГЭ и ЕГЭ можно красиво и доступно решать с учащимися, используя графы, некоторые из них «требуют» применения графов [30]. Это позволяет расширить спектр средств, используемых при решении задач, упростить поиск решения и в некоторых случаях существенно сократить время на поиск правильного ответа. Именно это и вызывает интерес у учащихся к практическим задачам. Данный интерес и стал основой для дальнейшего продвижения графов на уроках информатики.
Объектом исследования выпускной квалификационной работы является применение теории графов в информатике.
Предметом исследования выпускной квалификационной работы является программа для обучения решению задач по информатике с использованием теории графов.
Цель выпускной квалификационной работы состоит в особенности использования теории графов на уроках информатики в школе.
Для решения поставленной цели необходимо решить ряд задач:
• изучить и проанализировать учебную, методическую литературу по данной теме;
• сравнить подходы к решению задач без использования и с использованием графов;
• подобрать задачный материал по данной теме;
• разработать приложение для решения задач с использованием теории графов.
Практическая значимость - предложенные исследования и программа может быть использована в учебном процессе при изучении темы «Теория графов»; при подготовке к ОГЭ и ЕГЭ.
Выпускная квалификационная работа состоит из введения, заключения, трех разделов, списка использованных источников и приложения.
Введение содержит общие сведения о работе, актуальность выбранной темы, объект, цель и задачи. В первой главе демонстрируется аналитический обзор этапов развития теории графов. Вторая глава включает в себя анализ учебно-методической литературы, описание алгоритмов и их применение.
Третья глава содержит код программы с детальным описанием функций и формул, которые были использованы.
Моделирование с помощью графов реализует одну из важнейших потребностей - потребность наглядности. Визуализация модели явления в сочетании с вычислительными, информационными и моделирующими возможностями компьютера лучше всего объясняет сущность изучаемого явления. Рисунок графа является знаком, материальным предметом, который чувственно воспринимается и выступает в качестве посредника между реальной действительностью и математической моделью. Использование рисунков графов неразрывно связано с процессами абстрагирования и детализации, с помощью которых происходит отделение тех признаков моделируемого объекта, и которые затем отображаются в модели. Графу модели обеспечивают связь мышления с реальными ситуациями.
В рамках выполнения выпускной квалификационной работы была собрана информация об использовании теории графов в школьном курсе «Информатика и ИКТ».
Были рассмотрены теоретические основы, необходимые для изучения теории графов. Нами были рассмотрены следующие аспекты: возникновение теории графов как отдельной науки, основные виды графов, связность, графы - деревья, способы задания и операции на графах.
Проведен анализ учебной и методической литературы по теме исследования. Выяснены цель, задачи содержание обучения учащихся основной школы по теме: «Теория графов» было выявлено, что наиболее полно раскрывается данная тема в учебно-методическом комплексе под редакцией Быкадоров Ю.А., «Информатика и ИКТ».
Разработан программный продукт, который может быть внедрен и использован для изучения теории графов на уроках информатики .
