Рабочая программа внеурочной деятельности. МАТЕМАТИКА. Теория графов для решения задач. 7 класс
рабочая программа по математике (6, 7 класс)

Рабочая программа внеурочной деятельности.

МАТЕМАТИКА.

Теория графов для решения задач.

7 класс.

Срок реализации: 1 год

Ф.И.О. учителя-разработчика: Григорьева О.В

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

Настоящая рабочая программа разработана в соответствии с требованиями Федерального государственного образовательного стандарта основного общего образования.

Нормативная база:

• Федеральный Закон от 29.12.2012 № 273-ФЗ «Об образовании в Российской Федерации»;
• Федеральный государственный образовательный стандарт основного общего образования, утвержденный приказом Министерства образования и науки Российской Федерации от 17.12.2010 № 1897 (далее - ФГОС основного общего образования) (для V-VIII классов образовательных организаций, а также для IX классов образовательных организаций, участвующих в апробации ФГОС основного общего образования в 2018/2019 учебном году);
• Порядок организации и осуществления образовательной деятельности по основным общеобразовательным программам - образовательным программам начального общего, основного общего и среднего общего образования, утвержденный приказом Министерства образования и науки Российской Федерации от 30.08.2013 № 1015;
• Федеральный перечень учебников, рекомендуемых к использованию при реализации имеющих государственную аккредитацию образовательных программ начального общего, основного общего, среднего общего образования, утвержденного приказом Министерства образования и науки Российской Федерации от 31.03.2014 № 253;
• Перечень организаций, осуществляющих выпуск учебных пособий, которые допускаются к использованию при реализации имеющих государственную аккредитацию образовательных программ начального общего, основного общего, среднего общего образования, утвержденного приказом Министерства образования и науки Российской Федерации от 09.06.2016 № 699;
• Санитарно-эпидемиологических требований к условиям и организации обучения в общеобразовательных учреждениях, утвержденных постановлением Главного государственного санитарного врача Российской Федерации от 29.12.2010 № 189 (далее - СанПиН 2.4.2.2821-10);
• Региональные нормативные документы
• Локальные акты образовательной организации, регламентирующие данную деятельность.

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

Задачи программы:

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

Краткая характеристика курса

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

Направление программы – общеинтеллектуальное,  программа создает условия для творческой самореализации личности ребенка.

Актуальность программы обоснована введением ФГОС ООО, а именно ориентирована на выполнение требований к содержанию внеурочной деятельности школьников, а также на интеграцию и дополнение содержания предметных программ. Программа педагогически целесообразна, ее реализация создает возможность разностороннего раскрытия индивидуальных способностей школьников, развития интереса к различным видам деятельности, желания активно участвовать в продуктивной деятельности, умения самостоятельно организовать свое свободное время.

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

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

Задачи на  занятиях подбираются с учетом рациональной последовательности их предъявления: от репродуктивных, направленных на актуализацию знаний, к  частично-поисковым, поисковым, исследовательским и проблемным, ориентированным на  овладение  обобщенными приемами познавательной деятельности. Система занятий  должна вести к формированию важных характеристик творческих способностей: беглость мысли, гибкость ума, оригинальность, любознательность, умение выдвигать и разрабатывать гипотезы.

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

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

Объем часов

В соответствии с требованиями Федерального государственного образовательного стандарта основного общего образования и Учебным планом внеурочной деятельности Государственного бюджетного общеобразовательного учреждения средней общеобразовательной школы №86 Петроградского района Санкт-Петербурга на 2018-2019 учебный год данный курс внеурочной деятельности изучается в 7 классе. Продолжительность курса 34 часа (32ч.+2 резервных) в год, по 1 часу в неделю.

Формы подведения итогов

• защита проектно-исследовательских работ, рефератов, выступление.
• участие в проектной деятельности,
• участие в различных олимпиадах, конкурсах, соревнованиях, фестивалях и конференциях математической направленности разного уровня, в том числе дистанционных.
• Коллективный выпуск математической газеты, изготовление моделей для уроков математики и т.п.

Ожидаемые результаты

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

Метапредметными результатами реализации программы станет формирование общих способов интеллектуальной деятельности, характерных для математики и являющихся основой познавательной культуры, значимой для различных сфер человеческой деятельности, а именно следующих универсальных учебных действий.

Регулятивные УУД:

• Самостоятельно формулировать цели занятия после предварительного обсуждения.
• Учиться совместно с учителем обнаруживать и формулировать учебную проблему.
• Составлять план решения проблемы (задачи).
• Работая по плану, сверять свои действия с целью и, при необходимости, исправлять ошибки.
• В диалоге с учителем учиться вырабатывать критерии оценки и определять степень успешности выполнения своей работы и работы всех, исходя из имеющихся критериев.
• Познавательные УУД:
• Ориентироваться в своей системе знаний: самостоятельно предполагать, какая информация нужна для решения той или иной задачи.
• Отбирать необходимые для решения  задачи источники информации среди предложенных учителем словарей, энциклопедий, справочников, интернет-ресурсов.
• Добывать новые знания: извлекать информацию, представленную в разных формах (текст, таблица, схема, иллюстрация и др.).
• Перерабатывать полученную информацию: сравнивать и группировать факты и явления; определять причины явлений, событий.
• Перерабатывать полученную информацию: делать выводы на основе обобщения знаний.
• Преобразовывать информацию из одной формы в другую: составлять более простой план учебно-научного текста.
• Преобразовывать информацию из одной формы в другую: представлять информацию в виде текста, таблицы, схемы.
• Коммуникативные УУД:
• Донести свою позицию до других: оформлять свои мысли в устной и письменной речи с учётом своих учебных и жизненных речевых ситуаций.
• Донести свою позицию до других: высказывать свою точку зрения и пытаться её обосновать, приводя аргументы.
• Слушать других, пытаться принимать другую точку зрения, быть готовым изменить свою точку зрения.
• Читать вслух и про себя тексты научно-популярной литературы и при этом: вести «диалог с автором» (прогнозировать будущее чтение; ставить вопросы к тексту и искать ответы; проверять себя); отделять новое от известного; выделять главное; составлять план.
• Договариваться с людьми: выполняя различные роли в группе, сотрудничать в совместном решении проблемы (задачи).
• Учиться уважительно относиться к позиции другого, учиться договариваться.

Предметными результатами реализации программы станет создание фундамента для математического развития, формирование  механизмов мышления, характерных для математической деятельности, а именно:

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

2. КАЛЕНДАРНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ

Планирование рассчитано на 34 часа (1 час в неделю)

СОДЕРЖАНИЕ ПРОГРАММЫ

Нулевой цикл «Знакомство». 

Очень многое в организации и успешности проведения внеурочной деятельности зависит от первого занятия. Возможна такая его структура:

• Руководитель освещает перспективы: что будет рассматриваться на занятиях, чем учащиеся будут заниматься, каково содержание и формы работы, как организуется самостоятельная работа и домашняя работа, подготовка докладов, рефератов, мини-проектов. Важно озвучить учащимся основные требования к участникам внеурочной деятельности.
• Учащимся предлагается несколько простых задач. Для их решения не требуется ничего, кроме здравого смысла и владения простейшими вычислительными навыками; их назначение – выявление логических и математических способностей учащихся (а в дальнейшем – в качестве эмоциональных разрядок).
• Второй час занятия целесообразно посвятить разбору и обсуждению задач домашнего задания.
• Возможно, некоторое время следует посвятить рассказу о математике, о ее значении в жизни человека, о ее связях с другими науками.

Задачи, приводящие к теории графов.

Задачи, приводящие к теории графов. Решение задач с помощью построения графовых моделей.

Задача 1. Если задуманное число умножить на 5 и к результату прибавить 1, потом сумму увеличить в 6 раз и к результату прибавить 2, затем новую сумму умножить на 7 и полученное произведение увеличить на 4, то получим число, которое в 16 раз больше числа 135. Найдите это число.

Решение: Сделаем рисунок (построим граф).

Решая, действия выполняем наоборот.

Ответ: 10.

Задача 2. В первом матче футболисты «Звездочки» забили в ворота противника половину мячей, забитых ими во втором матче, и еще один мяч. Во втором матче они забили вдвое меньше мячей, чем в третьем матче, и еще один мяч. В третьем матче они забили вдвое меньше мячей, чем в первом, и еще один мяч. Сколько всего мячей забили футболисты «Звездочки» за три матча?

Решение:

Из рисунка видно, что в каждой игре было забито одинаковое число мячей. В каждой игре забито по 2 мяча.

Ответ: 6 мячей забито в 3-х играх.

Задача 3. Колхозница принесла на базар корзину яблок. I покупателю она продала половину всех яблок и еще 1 яблоко, II – половину остатка и еще 1 яблоко, III – половину нового остатка и еще 1 яблоко и т.д. Последнему – шестому покупателю она также продала половину оставшихся яблок и еще 1 яблоко, причем оказалось, что она продала все свои яблоки. Сколько яблок принесла для продажи колхозница?

Решение: Составим граф.

Решая, действия делаем обратно.

Ответ: 126 яблок.

Задача 4. На вопрос путника: «Сколько у тебя в стаде голов скота?» - пастух ответил: «Если бы к моему стаду  добавить одну корову, то третью часть всего стада составляли бы овцы и козы. Если бы к имеющимся овцам и козам добавить одну овцу, то седьмую часть их составляли бы козы, в которых третья часть есть лишь один маленький козленок». Сколько голов скота было в стаде?

Решение: Составим граф по условию задачи.

Решаем обратно.

Ответ: в стаде 59 голов скота.

Понятие графа, его элементы., перевод условия задачи на язык графов

Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.

Задача: Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехали загород, если всего было 10 рукопожатий?

Решение: Сделаем рисунок. Точки будут изображать мальчиков, а отрезки рукопожатия.

1)  2)  3)  4)

Из рисунка видно, что на вокзале встретились 5 мальчиков.

Фигуры, которые получились при решении этих задач, состоят из точек и линий, соединяющих эти точки. Такую фигуру называют графом. Линии графа называют ребрами, а точки – вершинами. В графе не обязательно, чтобы каждая вершина была соединена со всеми остальными.

Если в графе ни одна часть не является замкнутой линией, то такой граф называется деревом.

Графы помогают решать задачи.

Виды графов (неполные, полные, нулевые). Изоморфные графы. Ориентированный, неориентированный, взвешенный графы. Угадай – какой я? (виды графов)

История графов

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук).

Он предложил изящное решение знаменитой задачи о 7 Кенигсбергских мостах в 1736 году, а также придумал общий метод решения подобных задач.

В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков - К. Берж, О. Оре, А. Зыков.

Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

Широкое развитие теория графов получила с 50-х годов 20 века в связи со становлением кибернетики и развитием вычислительной техники.

Виды графов

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом.

Графы, в которых не построены все возможные ребра, называются неполными графами.

Графы, в которых построены все возможные ребра, называются полными графами.

Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.

Степени вершин и подсчет числа ребер.

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

ТЕОРЕМА. Число нечетных вершин любого графа четно.

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

Эйлеровы графы.

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3. (вытекает из рассмотренной нами теоремы).

Невозможно начертить граф с нечетным числом нечетных вершин.

Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.

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

Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».

Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.

Связные графы

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

Граф называется несвязным, если это условие не выполняется.

Если, например, на рисунке можно провести ребро так, что граф станет связным, то такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.

ТЕОРЕМА. Граф является эйлеровым тогда и только тогда, когда он связен и имеет не более двух нечетных вершин.

Деревья.

Деревом называется любой связный граф, не имеющий циклов.

Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

Циклом называется путь, в котором совпадают начало с концом.

Циклы Элементарный и Эйлеровая линия

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.

Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией.

Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.

При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.

Висячие вершины в графах

Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

Свойство 1. Для каждой пары вершин дерева существует единственный путь, их соединяющий.

Этим свойством пользуются при нахождении всех предков в генеалогическом дереве, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов.

Свойство 2. Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

ЛЕММА (о висячей вершине). В каждом дереве есть висячая вершина.

ТЕОРЕМА. В дереве число вершин на одну больше числа ребер.

Изоморфизм. Плоские графы и теорема Эйлера.

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

Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них:

• одинаковое количество вершин
• если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром.

Граф, который можно нарисовать так, чтобы его рёбра не пересекались нигде, кроме вершин, называются плоским или планарным.

ТЕОРЕМА Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E - число рёбер, F – число кусков. (равенство V -E+F=2 обычно называют формулой Эйлера).

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

ТЕОРЕМА Понтрягина – Куратовского. Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.

(В основном используется в старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса — является ли рассматриваемый граф плоским или нет)

Ориентированные графы.

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

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

Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах - улицах рассматриваемой схемы (графа) города.

Граф, на рёбрах которого расставлены стрелки, называется ориентированным.

Логические задачи.

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

На первом этапе целесообразно  рассмотреть три  широко распространенных типа логических задач:

1. Задачи, в которых на основании серии посылок, сообщающих те или иные сведения о действующих лицах, требуется сделать определенные выводы.
2. Задачи о «мудрецах».
3. Задачи о лжецах и тех, кто всегда говорит правду.

Повторение. Математическое соревнование.

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

Итоговое занятите проводится как анкетирование и обсуждение освоенных тем программы, изуученных в результате участия во внеурочной деятельности по математике. Анкета составляется учителем. В нее включаются вопросы по заданиям, которые были предметом обсуждения на занятиях внеурочной деятельности.

ЛИТЕРАТУРА

Основная

1. Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007.
2. Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. 2009.
3. Березина Л.Ю. Графы и их применение. - М.: Просвещение,-1979.
4. Емеличев В.А. , Мельников О.И., Сарванов В.И. , Тышкевич Р.И. Лекции по теории графов. – М.: Наука,- 1990.
5. Коннов В.В., Клековкин Г.Н., Коннова Л.П. Геометрическая теория графов. – М.: Народное образование,- 1999.
6. Мельников О.И. Занимательные задачи по теории графов. Учебно методическое пособие.- Минск: Тетра Системс,-2001.
7. Уилсон Р. Введение в теорию графов. - М.: Мир, - 1977.

Дополнительная

8. Игнатьев Е.И. Хрестоматия по математике. В царстве смекалки или арифметика для всех. Книга для семьи и школы. Опыт математической хрестоматии в трех книгах. – Ростов – на – Дону. Ростовское книжное издательство,-1995Канель-Белов А.Я., Ковальджи А.К. Как решают нестандартные задачи. – М.: МЦНМО, 2015.
9. Спивак А.В. Математический праздник. – М.: МЦНМО, 1995.
10. Шарыгин И.Ф., Шевкин А.В. Математика. Задачи на смекалку. 5-6 кл. – М.: Просвещение, 2001.
11. Фарков А.В. Математические олимпиады: методика подготовки 5-8 классы. – М.: ВАКО, 2012.

Примерные темы  учебных  проектов

7 класс

1. Леонард Эйлер – основоположник теории графов
2. История графов
3. Виды графов и их примеры в природе и технике
4. Применение графов в различных областях жизни людей
5. Генеалогическое дерево – один из способов применения теории графов
6. Описание исследования и составление генеалогического дерева моей семьи
7. Применение графов при решении задач
8. Задача о Кенигсбергских мостах.
9. Графы вокруг нас