Семинар ДООМ: Знакомство с графами.
Раздел программы факультативного курса логики для 8-9 классов «Знакомство с графами».
Данный раздел позволяет сформировать у обучаемых представление о методах решения различных задач с применением графов. Изучение курса предусматривает знакомство с основными понятиями теории графов
Пояснительная записка
Зародившись при решении головоломок и занимательных задач, теория графов стала в настоящее время простым, доступным и мощным средством решения широкого круга важных практических задач. Особенно велико значение графов как универсального языка при создании математических моделей. Благодаря доступности и наглядности графы могут успешно использоваться в школьном обучении при проведении факультативных занятий. Изучение основ теории графов позволяет развивать мышление учащихся, направленное на восприятие дискретных объектов, подготавливать их к обучению в вузах. Кроме того, задачи, решаемые с помощью графов, постоянно встречаются на олимпиадах по математике и информатике.
Курс «Задачи на графах» рекомендуется учащимся 8-9 классов. К этому времени они имеют достаточно высокий уровень развития абстрактного мышления, умеют строить модели задач, имеют сформированные познавательные интересы. Программа курса рассчитана на 12 часов.
Содержание курса предполагает знакомство с понятиями и методами теории графов, освоение алгоритмов решения основных типов задач на графы и применение полученных знаний к решению прикладных задач.
Цели курса: сформировать у учащихся представление о возможностях широкого использования графов как средства моделирования реального мира, познакомить их с задачами теории графов, подготовить школьников к восприятию этих понятий при дальнейшем обучении.
Задачи курса:
- ознакомление учащихся с понятиями и методами решения задач с помощью графов;
- формирование умения распознавать задачи, решаемые с помощью графов, строить графовые модели;
- развитие логического мышления школьников;
Содержание
Основные понятия теории графов
Задачи, решаемые с помощью графов (головоломки, комбинаторные и прикладные задачи). Определение графа. Вершины и ребра. Смежность. Изображения графов. Степени вершин. Лемма «о рукопожатиях» и следствие из нее. Полный граф. Пути, цепи и циклы в графах. Связность. Двудольные графы. Ориентированные графы. Решение задач.
Деревья
Задачи, приводящие к понятию дерева. Определение дерева. Лес. Корневые деревья. Свойства деревьев. Решение задач.
Обходы графа
Задачи, приводящие к понятию обходов графа (задача о лабиринте; задачи на шахматной доске; задача о мостах; задача о рисовании фигур одним росчерком Нахождение кратчайшего расстояния между вершинами, построение множества всех циклов в графе). Эйлеровы графы. Эйлеров цикл. Эйлерова цепь. Решение задач.
Ожидаемые результаты: В результате изучения курса у учащихся будут сформированы представления:
о значении теории графов как средства описания действительности;
об основных понятиях теории графов;
Учащиеся овладеют следующими способами деятельности:
использовать изученных методов для решения задач;
применять полученные знания в реальной жизни.
Изучение данного раздела предполагает: повышение интереса учащихся к теории графов посредством решения задач; формирование логико-алгоритмического и системно-комбинаторного мышления; развитие познавательных способностей учащихся; формирование опыта исследовательской деятельности; подготовку учащихся к дальнейшему изучению математики.
Литература
- Березина, Л. Ю. Графы и их применение /Л. Ю. Березина. — М.: Просвещение, 1979. — 143 с.
- Мельников, О. И. Занимательные задачи по теории графов: Учебно-метод. пособие / О. И. Мельников. — Мн.: ТетраСистемс, 2001. — 144 с.
- Уилсон, Р. Введение в теорию графов / Р. Уилсон. — М.: Мир, 1977. — 208 с.
- Харланов, А. А. Методическое пособие для учителей и преподавателей средних учебных заведений нового типа в классах с углубленным изучением информатики: Пособие для учителей, работающих в профильных классах с углубленным изучением информатики, в форме поурочных разработок для преподавания темы «Решение задач с использованием графов» / А. А. Харланов. — Мн.: ИПКиПРРиСО, 1997. — 72 с.
--Москевич Лариса Вячеславовна 00:16, 8 декабря 2007 (UZT) Команда 061
