Графы и их применпенение

16

Министерство общего и профессионального образования

Министерство общего и профессионального образования Свердловской области

Управление образования Администрации города Екатеринбурга

Муниципальное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа № 131

_____________________________________________________________________________________

620076, г. Екатеринбург, ул. Гаршина, 8 б тел. 263-48-85 email: scoola_131@mail.ru

ПРИЛОЖЕНИЕ ___К ОСНОВНОЙ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЕ СРЕДНЕГО ОБЩЕОГО ОБРАЗОВАНИЯ НА 2010-2020 Г.Г.

Утверждаю:

Директор МБОУ СОШ № 131

____________Г.А. Осадчая

Приказ № ____ от _______ 2015 г.

РАБОЧАЯ ПРОГРАММА

среднего общего образования

по элективному курсу

«Графы и их применение »

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Рабочая программа элективного курса «Графы и их применение» составлена группа учителей математики МБОУ СОШ №131.

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

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

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

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

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

Цели курса:

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

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

• научить составлять математическую модель текстовой задачи с помощью графа, переходить от одной модели задачи к другой;

• обучение учащихся некоторым методам и приемам решения математических задач, выходящих за рамки школьного учебника математики;

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

• развитие интереса и положительной мотивации изучения математики.

Место курса «Графы и их применение» в учебном плане

Базисный учебный (образовательный) план МБОУ СОШ № 131 на изучении курса отводит 1 час в неделю, всего 35 уроков.

Тематическое планирование

п\п

Тема

Количество

часов

Количество

практ./ контр. работ

Первое знакомство с графами

5

Плоские графы

6

Графы с цветными ребрами

4

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

3

Отношения

4

Деревья в работе

5

Сетевой график. Построение сетевого графика.

6

Итого

35

Содержание курса

1. Первое знакомство с графами (4ч)

Задачи, приводящие к графам. Некоторые основные понятия теории графов. Полный граф, Дополненный граф. Степень вершины. Путь графа. Цикл. Связность графа. Операция удаления ребра. Деревья, лес. Изображение графа.

2. Плоские графы (6ч)

Представление о плоском графе. Формула Эйлера. Изображение ребер графа прямолинейными отрезками. Эйлеровы графы. Лабиринты. Гамильтоновы циклы и пути в графах.

3. Графы с цветными ребрами (3ч).

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

4. Ориентированные графы (3час)

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

5. Отношения(4ч)

Квадрат множества. Свойства отношений: рефлексивность, антирефлексивность, симметричность, антисиметричность, транзитивность, антитразитивность, полное отношение, отношение эквивалентности. Отношение порядка.

6. Деревья в работе (5 ч)

Деревья и подсчет изомеров. Число деревьев с пронумерованными вершинами. Отыскание кратчайшего пути. Деревья и перестановки из n элементов. Маршрут по местности и число сочетаний С_n^m . Разбиение и композиция натуральных чисел. Деревья, вероятность генетика.

7. Сетевой график. Построение сетевого графика.(6ч)

Что такое сетевой график, когда необходимо уметь строить сетевой график? События и работа в теории графов. Построение сетевого графика. Критический путь. О резервах времени. Из истории сетевого планирования и управления.

Требования к уровню подготовки учащихся.

В результате изучения курса ученик должен

знать/понимать

• назначение математической науки для решения задач, возникающих в теории и практике;

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

• назначение практики и вопросов, возникающих в самой математике для формирования и развития математической науки;

уметь:

• строить графы, иллюстрирующие различные жизненные ситуации;

• применять построенный граф для решения логических задач, задач теории вероятностей, комбинаторики;

• применять графики для анализа условия задачи, на основе этого анализа строить математическую модель;

• использовать приобретенные знания и умения в практической деятельности и повседневной жизни;

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

владеть компетенциями: познавательной, коммуникативной, информационной и рефлексивной;

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

• воспитание культуры личности, отношения к математике как к части общечеловеческой культуры, играющей особую роль в общественном развитии.

• Математическое моделирование реальных процессов с помощью графов;

• описания зависимостей между элементами различных множеств с помощью графов;

• интерпретации графов реальных событий.

Нормы оценивания обучающихся

Для оценки учебных достижений обучающихся используется:

• текущий контроль в виде проверочных работ и самостоятельных работ;

• устный опрос, беседа,

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

Шкала оценивания:

Критерии оценивания знаний, умений и навыков обучающихся по математике. (Согласно Методическому письму «Направления работы учителей математики по исполнению единых требований преподавания предмета на современном этапе развития школы»)

Для оценки достижений учащихся применяется пятибалльная система оценивания.

Нормы оценки:

1. Оценка письменных контрольных работ обучающихся по математике.

Ответ оценивается отметкой «5», если:

1) работа выполнена полностью;

2) в логических рассуждениях и обосновании решения нет пробелов и ошибок;

3) в решении нет математических ошибок (возможна одна неточность, описка, которая не является следствием незнания или непонимания учебного материала).

Отметка «4» ставится, если:

1) работа выполнена полностью, но обоснования шагов решения недостаточны (если умение обосновывать рассуждения не являлось специальным объектом проверки);

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

Отметка «3» ставится, если:

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

Отметка «2» ставится, если:

1) допущены существенные ошибки, показавшие, что обучающийся не обладает обязательными умениями по данной теме в полной мере.

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

2.Оценка устных ответов обучающихся по математике

Ответ оценивается отметкой «5», если ученик:

полно раскрыл содержание материала в объеме, предусмотренном программой и учебником; изложил материал грамотным языком, точно используя математическую терминологию и символику, в определенной логической последовательности;

правильно выполнил рисунки, чертежи, графики, сопутствующие ответу;

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

возможны одна - две неточности при освещение второстепенных вопросов или в выкладках, которые ученик легко исправил после замечания учителя.

Ответ оценивается отметкой «4»,

если удовлетворяет в основном требованиям на оценку «5», но при этом имеет один из недостатков: в изложении допущены небольшие пробелы, не исказившее математическое содержание ответа; допущены один - два недочета при освещении основного содержания ответа, исправленные после замечания учителя; допущены ошибка или более двух недочетов при освещении второстепенных вопросов или в выкладках, легко исправленные

после замечания учителя.

Отметка «3» ставится в следующих случаях:

неполно раскрыто содержание материала (содержание изложено фрагментарно, не всегда последовательно), но показано общее понимание вопроса и продемонстрированы умения, достаточные для усвоения программного материала (определены «Требованиями к математической подготовке учащихся» в настоящей программе по математике);

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

Отметка «2» ставится в следующих случаях:

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

Список литературы

1. .Басакер р., Саати Т., Конечные графы и сети. М., Наука, 1974.

2. Березини Л. Ю. Графы и их применение. М., Просвещение 1979.

3. Берж К. Теория графов и ее применение. М. ИЛ, 1962.

4. Оре О.Теория графов. М, Наука, 1968.

5. Гарднер М. Математические досуги. М. Мир.,1972.

6. Гарднер М. Математические новеллы. М. Мир. 1973.

7. Мельников О.И. Незнайка в стране графов: пособие для учащихся . Изд.2-е, исп. Ии доп. М.:КомКнига,2006.-160с.

8. Мельников О.И. Теория графов в занимательных задачах. Изд.3-е исп. и доп. Книжный дом «Либроком»,2009.-232стр.

Интернет-ресурсы

www.tofmal.ru/projects/graphs/

https://globallab.org/ru/help/to/prepod/_bloks/pic/about_globallab.html#.V29bFmOKTct

mybiblioteka.su/8-106596.html

www.problems.ru/

Материально - техническая база

1. Мультимедийный проектор;

2. Компьютер;

3.Экран для демонстрации слайдов и презентаций;

4. Принтер для распечатки раздаточного и дидактического материала;

5. Чертежные измерительные инструменты.

Календарно-тематическое планирование по курсу «Графы и их применение»

(1 час в неделю, всего 35 уроков)

Дата планируемая

Тема

Кол-во часов

Тип урока

Практические работы (экскурсия)/ контрольные работы

Оборудование

Основные понятия

1 неделя сентября

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

1

Ку

Проектор компьютер

Некоторые основные понятия теории графов. Ребро, вершина. Полный граф, Дополненный граф.

2 неделя сентября

Степень вершины.

1

КУ

Проектор компьютер

Степень вершины. Путь графа. Цикл. Зависимость степени графа от числа вершин.

3 неделя сентября

Путь графа. Цикл.

1

КУ

Проектор компьютер

Определение пути, цикла простого цикла в графах. Решение задач

4 неделя сентября

Связность графа. Операция удаления ребра.

1

КУ

Проектор компьютер

Понятие связного и несвязного графов, Условие существования цикла. Операция удаления ребра. Мост.

1 неделя октября

Деревья, лес. Изображение графа.

1

КУ

Проектор компьютер

Понятие дерева, теорема о зависимости числа ребре в дереве от числа вершин. Построение графов по условию задачи.

2 неделя октября

Представление о плоском графе.

1

ку

Проектор компьютер

Понятие плоского графа, примеры плоских графов, Свойства плоских графов.

3 неделя октября

Формула Эйлера.

1

ку

Проектор компьютер

Формула Эйлера для плоского графа. Теорема Понтрягина- Куратовского о необходимом и достаточном условии того что граф является плоским. Триангулированный граф.

4 неделя октября

Изображение ребер графа прямолинейными отрезками

1

уп

Проектор компьютер

Изображение ребер графа прямолинейными отрезками. Теорема Фари.

1 неделя ноября

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

1

ку

Проектор компьютер

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

2 неделя ноября

Лабиринты.

1

уп

Проектор компьютер

Применение теории графов для решения задач о лабиринтах

3 неделя ноября

Гамильтоновы циклы и пути в графах

1

узз

ср

Проектор компьютер

Понятие Гамильтонова графа. Условие необходимое для того чтобы граф был гамильтоновым. Примеры задач.

4 неделя ноября

Свойства полных графов с цветными ребрами.

1

унз

ПР

Проектор компьютер

Понятие полного графа с цветными ребрами. Свойства графов с цветными ребрами. Задачи, приводящие к графам с цветными ребрами.

1 неделя декабря

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

1

уп

пр

Проектор компьютер

Свойства графов с цветными ребрами. Задачи, приводящие к графам с цветными ребрами.

2 неделя декабря

Задача о несцепленных треугольниках с одноцветными сторонами

1

ку

СР

Проектор компьютер

Задача о несцепленных треугольниках с одноцветными сторонами

3 неделя декабря

Исходные понятия. Полный ориентированный граф.

1

ку

пр

Проектор компьютер

Понятие полного ориентированного графа, построение его по условию задачи

4 неделя декабря

Круговые бескомпромиссные турниры.

1

ку

СР

Проектор компьютер

Задачи о круговых турнирах.

2 неделя января

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

1

ку

ср

Проектор компьютер

Задачи о голосовании с предпочтением. Построение ориентированных графов.

3 неделя января

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

1

уп

пр

Проектор компьютер

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

4 неделя января

Отношения.

Квадрат множества.

1

ку

ср

Проектор компьютер

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

1 неделя февраля

Свойства отношений: рефлексивность, антирефлексивность.

1

ку

пр

Проектор компьютер

Отношение рефлексивности , примеры отношений рефлексивности и антирефлексивности.

2 неделя февраля

Свойства отношений:

симметричность, антисиметричность.

1

ку

пр

Проектор компьютер

Свойства отношений:

симметричность, антисиметричность.

Примеры отношений симметричности и антисимметричности.

3 неделя февраля

Свойства отношений:

Транзитивность антитразитивность.

1

ку

пр

Проектор компьютер

Свойства отношений:

Транзитивность антитразитивность.

Примеры отношений транзитивности и антитранзитивности.

4 неделя февраля

Полное отношение. Графы полного отношения. Отношение эквивалентности.

1

ку

ср

Проектор компьютер

Полное отношение. Графы полного отношения. Примеры полных отношений. Отношение эквивалентности.

1 неделя марта

Отношение порядка.

1

ку

Проектор компьютер

Примеры отношений порядка. Графы иллюстрирующие отношения порядка.

2 неделя марта

Деревья и подсчет изомеров.

.

1

ку

СР

Проектор компьютер

Деревья и подсчет изомеров Корневая вершина графа. Расстояние между вершинами, радиус и диаметр связного графа. Двукорневое дерево.

3 неделя марта

Число деревьев с пронумерованными вершинами.

1

ку

пр

Проектор компьютер

Число деревьев с пронумерованными вершинами.

Метод Пруфера, устанавливающий взаимно однозначное соответствие между всеми возможными деревьями с n заданными пронумерованными вершинами.

1 неделя апреля

Отыскание кратчайшего пути.

1

ку

ПР

Проектор компьютер

Отыскание кратчайшего пути. Число возможных путей.

2 неделя апреля

Деревья и перестановки из n элементов. Маршрут по местности и число сочетаний С_n^m.

1

ку

пр

Проектор компьютер

Построение дерева перестановок. Построение маршрута, число путей и число сочетаний.

3 неделя апреля

Разбиение и композиция натуральных чисел. Деревья, вероятность генетика.

1

ку

Проектор компьютер

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

4 неделя апреля

Что такое сетевой график, когда необходимо уметь строить сетевой график?

1

ку

пр

Проектор компьютер

Что такое сетевой график, когда необходимо уметь строить сетевой график? Работа, событие, ожидание, фиктивная работа.

1 неделя мая

События и работа в теории графов. Построение сетевого графика.

1

ку

пр

Проектор компьютер

Правила построения сетевого графика. Построение сетевых графиков простейших проектов (комплексов работ).

2 неделя мая

Критический путь. О резервах времени.

1

ку

пр

Проектор компьютер

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

3 неделя мая

Из истории сетевого планирования и управления.

1

ку

пр

Проектор компьютер

История сетевого планирования. Сетевое планирование в наши дни.

Экономическая эффективность применения сетевого планирования.

4 неделя мая

Повторение. Построение графиков сетевого планирования

1

ку

Проектор компьютер

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

5 неделя мая

Повторение. Решение задач на построение графиков сетевого планирования

1

ку

пр

Проектор компьютер

Расшифровка аббревиатур, использованных в рабочей программе

КУ - комбинированный урок.

УП - урок практикум.

</