Графы в школьном курсе информатики и ИКТ.

Заключение
Графы позволяют сделать весьма доступным для учащихся вопрос о свойствах отношений. Глядя на графическое изображение того или иного отношения, они научатся проверять, обладает или не обладает данное отношение указанным свойством; полученный опыт позволит им выделить из известных отношений те, которые обладают общими свойствами. Применение графов позволяет выявить такие свойства отношений, которые помогут учащимся овладеть способами решения широкого круга практических задач. Так, используя графы и свойства отношений, учащихся можно легко научить решать простейшие уравнения, которые при традиционном подходе вызывают большие трудности, а также текстовые задачи, содержащие отношения типа «меньше на», «больше на».
В среднем звене понятие «граф» находиться в рубрике «Интересно знать». ...

Оглавление
Введение 2
Глава 1.Теоритиечксие основы изучение графов в школьном куре информатики 4
1.1.Понятие «Графа» 4
1.2. Графы в информатике 10
Глава 2.Особенности изучения графов в школьном курсе информатики и ИКТ 12
2.1.Место графов в школьном куре информатики 12
2.2.Анализ элективов и курсов по графам 13
Заключение 20
Список использованных источников 21
Приложения 23

Введение
Очень интересной темой в школьном курсе информатики и ИКТ является тема "Графы».
Почему теория графов так важна?
Во-первых, графы могут рассматриваться как модели самих программ, данных и процессов. Э. Дейкстра высказал однажды такую мысль: при грамотном программировании на тысячу строк программного текста нужно написать в десять раз больше рассуждений и доказательств, гарантирующих применимость программы.
Во-вторых, графы служат удобной структурой данных для представления объектов обработки информации. Расширение традиционного круга задач, решаемых на ЭВМ (перевод текста, распознавание речи, составление расписаний, игровые программы, экспертные и информационные системы и т.д.), за последние несколько десятков лет превратили комбинаторику и теорию графов в основной инструмент ре шения огромного числа задач.
Графы - это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используют при составлении карт и генеалогических древ. Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.
Цель исследования: рассмотреть особенности изучения графов в школьном курсе информатике и ИКТ.
Объект исследования: особенности изучения графов в школьном курсе информатике и ИКТ.
Предмет исследования: курс информатики и ИКТ в школе.
Задачи:
1. Освоить основные понятия теории графов.
2. Изучить графы в информатике.
3. Выделить и проанализировать особенности изучения графов в школьном курсе информатики и ИКТ.
Методы исследования: на данном этапе исследования нами применялся теоретический анализ литературы.

Значительные дидактические возможности для повышения познавательной активности при изучении элементов теории графов имеют новые информационные технологии обучения. В процессе исследования установлено наиболее значимые особенности и тенденции применения средств новых информационных технологий при изучении теории графов:
автоматическое построения различных типов графов, определение свойств и числовых характеристик графа позволяют усложнить примеры, увеличить их количество, ускорить получение информации о свойствах графа, что довольно удобно при объяснении нового материала, понятий, теорем;
компьютерные средства визуализации графов обеспечивают такие необходимые инструментальные средства и методы удобной манипуляции графами, как построение и удаление элементов графа, задание их взаимного расположения, изменение атрибутов элементов графа и т.п.;
использование компьютерной анимации, динамического изображения для представления учебного материала по теории графов;
наглядное исполнение алгоритмов с помощью специализированной компьютерной поддержки позволяет воссоздать алгоритм во всей его сложности  и разнообразие вариантов выполнения;
использование вычислительных, информационных и моделирующих возможностей компьютера для решения задач прикладного характера.
2.2.Анализ элективов и курсов по графам
Более подробно нами был проведен анализ школьных учебников по Информатике и ИКТ для учащихся с 3 по 11 классы, а также задания ЕГЭ на предмет содержания в них элементов из теории графов. В результате чего было выявлено, что в школьных учебниках, таких как «Информатика и ИКТ» 3-4 класс авторов Н.А.Нуровой, Н.В. Матвеевой, Е.Н. Челак, Н.К. Конопатовой, Л.П. Панкратовой, не рассматриваются «Элементы теории графов».
В школьных учебниках Н.Д. Угриновича за 7-9 классы тема «Элементы теории графов» рассмотрены в рамках темы «Основы логики».
Авторы А.Г. Гейн, А.Б. Ливчак, А.И.Сенокосов учебника «Информатика и ИКТ» за 10-11 класс в базовом и профильном уровнях за 10 класс данную тему не рассматривают в рамках изучения школьного курса информатики, а за 11 класс данная тема представлена в следующих параграфах: «Простейшие свойства графов», где дается понятие графа, ребра графа, его вершина, маршрут, цепь, цикл, а также какой граф называется кратным и связным; «Способы представления графа», здесь описывается один из способов задания структуры графа- таблица смежности.
Следующий параграф рассматривает применение алгоритма поиска в длину и в ширину, раскрывая понятия точки сочленения, моста, дерева, корня дерева, каркас.
А в учебнике за 10-11 класс авторов И.Г.Семакина и Е.К. Хеннера тема рассмотрена с помощью структур данных: деревья, сети, графы и таблицы в которых даются простейшие понятия и рассмотрены примеры.
Проанализировав задания из ЕГЭ с 2009 по 2013 год по Информатике и ИКТ, в которых затронута тема «Элементы теории графов», было выявлено, что в тестовых заданиях данная тема представлена в заданиях уровня А, уровня В и С.
Задания уровня А по теме «Элементы теории графов»:
А10. Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Найдите путь, при котором стоимость проезда из А в Е будет минимальной. Какова эта минимальная стоимость? Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
А
B
C
D
E
A
1
9
B
2
1
C
2
3
4
D
1
3
E
9
1
4

1) 6 2) 7 3) 8 4) 9
Для того чтобы решить задания уровня А из ЕГЭ по Информатике и ИКТ нужно, чтобы в учебном процессе по информатике использовались учебник авторов А.Г. Гейн, А.Б. Ливчак, А.И.Сенокосов «Информатика и ИКТ» за 10-11 класс или учебник И.Г.Семакина и Е.К. Хеннера за 10-11 класс. В противном случае, использовав, например, учебник Н.Д. Угриновича данное задание решить невозможно.
Задания уровня B по теме «Элементы теории графов»:
B9. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Ответ:_________________________
В данном случае, для решения задания уровня B нужно включить логическое мышление, воспользоваться теорией в школьных учебниках о понятиях в данном задании, а также изучить дополнительный материал, который, не затронут в школьных учебниках по Информатике и ИКТ.
Задания уровня C по теме «Элементы теории графов»:
С3. Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых – 4, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или утраивает число камней в какой-либо куче, или добавляет 2 камня в какую-либо кучу. Игра завершается в тот момент, когда количество камней в одной из куч становится не менее 19. Если в момент завершения игры общее число камней в двух кучах не менее 35, то выиграл Ваня, в противном случае – Петя. Кто выигрывает при безошибочной игре обоих игроков? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
А для решения данного задания из уровня С, высокого уровня сложности, ни один из школьных учебников по Информатике и ИКТ не представляет нужного материала.
Для того чтобы решить задания уровня В и С нужно разработать необходимые методики, позволяющие в полной мере подготовить учащихся к сдаче ЕГЭ в условиях ограниченного времени школьного курса информатики.6
«Добро пожаловать в страну Графов!»
План проведения
I этап – Орг. момент 
II этап – Новая тема. Понятие  графа
Графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки.
Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Многие алгоритмические задачи дискретной математики могут быть сформулированы как задачи, так или иначе связанные с графами, например задачи, в которых требуется выяснить какие-либо особенности устройства графа, или найти в графе часть, удовлетворяющую некоторым требованиям, или построить граф с заданными свойствами.
Легко найти примеры графов в самых разных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту. Многие математические доказательства также упрощаются, приобретают убедительность, если пользоваться графами.Для решения логических задач удобно использовать графы.
Теперь вернемся к основному термину «Граф» и познакомимся с его основными понятиями.
Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками.
Точки называются вершинами графа, а линиями рёбрами.
Ребро может иметь направление, которое указывается стрелочкой.
У графа обязательно есть вершины.
Граф без рёбер называется пустым.
Примеры различных графов приведены на рисунке.
Дерево (граф) – это способ организации информации об отношениях между объектами.
Слово «дерево» в теории  графов  означает  граф , в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину.
Первая работа по теории графов принадлежит Леонардо Эйлеру (1736г).
Показ презентации «Город – мечта»
Термин граф впервые ввёл 1936г Венгерский математик Денеш Кениг. Графами были названы схемы состоящие из точек и соединяющие эти точки отрезков прямых или кривых.
Графы, в которых не построены все возможные рёбра называется неполными графами.
Путь графа – последовательность дуг, где конец одной дуги является началом другой дуги.
Показ презентации «Золушка».
III этап. Представление информации в виде дерева.
Особым видом графа является дерево. Данная форма модели применяется тогда, когда элементы моделируемого объекта находятся в состоянии какого-либо подчинения и соподчинения, когда есть отношение иерархичности. Модель управления предприятием (школой, театральным коллективом и т. д.) очень удобно представлять в виде дерева.
Вам хорошо известно понятие «родословное дерево» и вы можете изобразить в такой форме ваши родственные отношения. Каталог файлов на диске, также как и библиотечный каталог — примеры информационных моделей в форме дерева.
IV этап. Применение знаний и закрепление изученного. 
Задача1. Ранним утром машинисты Михаил, Иван, Алексей обменялись приветствиями каждый с каждым. Сколько всего было приветствий. Решите задачу с помощью графа. Нарисуй граф в рабочей тетради.
Задача2. В поезде ехали три друга: Коля, Андрей и Саша. Известно, что в купе №1 и 2 ехал не Коля. Андрей ехал не в купе №1. В каком купе ехал каждый из друзей.
Задача3. Из города А в город Б ведут две железные дороги, из города Б в городок В -тоже две железные дороги и из города А в город В – тоже две дороги. Нарисуй схему и сосчитай все возможные пути из города А в город В.
V этап. Знакомство с компьютерной игрой «Паучки»
Игра «Паучки» помогает детям более полно представить новую тему и вносит в урок атмосферу игры.
Вывод к главе 2.
Таким образом, анализ школьных учебников по Информатике и ИКТ и заданий ЕГЭ показал, что для их решения недостаточно знаний курса школьной программы информатики. Следовательно, необходимо расширить и углубить свои знания по темам в рамках различных спецкурсов, элективных курсов или других форм и способов обучения.
Заключение