Семинар ДООМ: Знакомство с графами.

Текущая версия на 15:08, 10 января 2008

Раздел программы факультативного курса логики для 8-9 классов «Знакомство с графами».

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

Пояснительная записка

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

Курс «Задачи на графах» рекомендуется учащимся 8-9 классов. К этому времени они имеют достаточно высокий уровень развития абстрактного мышления, умеют строить модели задач, имеют сформированные познавательные интересы. Программа курса рассчитана на 12 часов.

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

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

Задачи курса:

1. ознакомление учащихся с понятиями и методами решения задач с помощью графов;
2. формирование умения распознавать задачи, решаемые с помощью графов, строить графовые модели;
3. развитие логического мышления школьников;

Содержание

Основные понятия теории графов

Задачи, решаемые с помощью графов (головоломки, комбинаторные и прикладные задачи). Определение графа. Вершины и ребра. Смежность. Изображения графов. Степени вершин. Лемма «о рукопожатиях» и следствие из нее. Полный граф. Пути, цепи и циклы в графах. Связность. Двудольные графы. Ориентированные графы. Решение задач.

Деревья

Задачи, приводящие к понятию дерева. Определение дерева. Лес. Корневые деревья. Свойства деревьев. Решение задач.

Обходы графа

Задачи, приводящие к понятию обходов графа (задача о лабиринте; задачи на шахматной доске; задача о мостах; задача о рисовании фигур одним росчерком Нахождение кратчайшего расстояния между вершинами, построение множества всех циклов в графе). Эйлеровы графы. Эйлеров цикл. Эйлерова цепь. Решение задач.

Ожидаемые результаты: В результате изучения курса у учащихся будут сформированы представления:

о значении теории графов как средства описания действительности;

об основных понятиях теории графов;

Учащиеся овладеют следующими способами деятельности:

использовать изученных методов для решения задач;

применять полученные знания в реальной жизни.

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

Литература

1. Березина, Л. Ю. Графы и их применение /Л. Ю. Березина. — М.: Просвещение, 1979. — 143 с.
2. Мельников, О. И. Занимательные задачи по теории графов: Учебно-метод. пособие / О. И. Мельников. — Мн.: ТетраСистемс, 2001. — 144 с.
3. Уилсон, Р. Введение в теорию графов / Р. Уилсон. — М.: Мир, 1977. — 208 с.
4. Харланов, А. А. Методическое пособие для учителей и преподавателей средних учебных заведений нового типа в классах с углубленным изучением информатики: Пособие для учителей, работающих в профильных классах с углубленным изучением информатики, в форме поурочных разработок для преподавания темы «Решение задач с использованием графов» / А. А. Харланов. — Мн.: ИПКиПРРиСО, 1997. — 72 с.

--Москевич Лариса Вячеславовна 00:16, 8 декабря 2007 (UZT) Команда 061