Программа элективного курса для предпрофильной подготовки учащихся 9-классов “Элементы теории графов “.
методическая разработка по алгебре (9 класс) по теме

Осипова Нина Юрьевна.

Программа элективного курса для предпрофильной подготовки учащихся     9-классов

“Элементы теории графов “.

Содержание:

1.Аннотация …………………………………………..………3

2.Пояснительная записка……………………………………..4

3.Учебно-тематическое планирование………………………6

4.Содержание программы    .…………………………………8

5.Методическое содержание программы……………………10                             5.1.Методы и формы обучения………………………………15

5.2.Описание основных форм организации учебных

занятий..………………………………………………….……15

6.Организация проведения аттестации учащихся……….…16

7.Список рекомендуемой литературы………………………17

7.1.Обязательнаялитература…………………………………17

7.2.Дополнительная литература……………………………..17

-2-

1.Аннотация.

            Настоящая работа представляет собой программу элективного курса “ Элементы теории графов “ для предпрофильной подготовки учащихся 9 классов.

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

              Курс рассчитан на 16 часов, где предусмотрены четыре самостоятельные работы и по окончании курса итоговая контрольная работа.

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

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

-3-

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

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

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

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

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

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

                     Настоящий   элективный курс должен решать следующие задачи:  

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

              Полученные знания  позволяют:

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

                                                                     -4-

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

16. учебно-организационные;
17. учебно-интеллектуальные;
18. учебно-коммуникативные;
19. учебно-информационные.

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

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

Элективный курс состоит из 8 тем:

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

- Решение логических задач с помощью графических схем;

- Решение комбинаторных задач;

- Одним росчерком пера ;

- Путешествия по лабиринтам;

- Задача о странствующем торговце;

- Задача о трех домах и трех колодцах;

- Задачи на раскраску.

              Курс рассчитан на 16 часов. Из расчета 2 часа в неделю курс будет продолжаться  примерно одну четверть. При завершении курса учащимся рекомендуется выполнить контрольную работу.

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

-5-

3. Учебно-тематическое планирование.

 Содержание    Количество      Форма      Организация     Наглядность      Образовательный    Формы   Литература  Приме-  

                          часов                прове-       самостоятель                                продукт                    контро-                         чание

                       все  лек-   др.ви- дения         ной деятель-                        

                       го    ций   ды за-  занятий     ности

                                        нятий

    -1-               -2-   -3-      -4-          -5-                -6-                      -7-                          -8-                       -9-             -10-             -11-

 1.Введение.     2      2                 Беседа,                                Модели гра-     Тезисы                                       [1] ,[2],[5]    

 Первое зна-                                лекция.                                фов.

 комство с

 графами.      

 2.Решение      2     0,5      1,5     Лекция,     Выполнение   Схемы            Тезисы, составление Письмен-  [1] ,[2],[5],    

 логических                                 практи-     дифферен-                               схем, по готовым       ный           [9]  

 задач с по-                                  кум по       цированных                            схемам составление  опрос,

 мощью гра-                                решению   заданий.                                  логических задач.      собеседо-  

 фических                                    задач.                                                                                              вание.

 схем.  

 3.Решение      2      0,5       1,5   Лекция,     Выполнение   Модель дере-   Тезисы.                      Творчес-    [1] ,[2],[3],  

 комбинатор-                              практи-     дифферен-      ва возможных                                      кая са-        [5] ,[12].    

 ных задач.                                 кум по       цированных   вариантов.                                            мостоя-    

                                                    решению   заданий.                                                                       тельная

                                                    задач.                                                                                               работа,

                                                                                                                                                            собеседо-

                                                                                                                                                            вание.  

 4.Одним         2        -         2     Беседа,       Подготовка    Подготовка    Итоги исследований  Творчес-   [1] ,[3],[5].  

 росчерком                                 практи-     творческих      моделей                                               кая са-        

 пера .                                         кум по       работ, прове-  лабиринта.                                           мостоя-    

                                                   решению  дение иссле-                                                                 тельная

                                                   задач.        дований, вы-                                                                 работа,

                                                                      полнение                                                                      оценива-

                                                                      дифференци-                                                               ние ито-

                                                                      рованных                                                                     гов иссле-

                                                                      заданий,                                                                       дований,

                                                                      работа в ми-                                                                творческих  

                                                                      крогруппах.                                                                 работ, от-

                                                                                                                                                            чет рабо-

                                                                                                                                                            ты микро-

                                                                                                                                                            групп.  

 5. Путешест-  2       -         2       Беседа,     Подготовка    Модели лаби- Итоги исследований  Творчес-   [1] ,[3],[5].  

 вия по лаби-                               практи-     рефератов,     ринта , подго-                                      кая са-  

                                                    кум по       проведение    товка моделей                                      мостоя-        

                                                    решению  дение иссле-   головоломок.                                       тельная      

                                                    задач.        дований, ра-                                                                 работа,          

                                                                      бота в микро-                                                               оценива-  

                                                                      группах.                                                                        ние ито-

                                                                                                                                                            гов иссле-

                                                                                                                                                            дований

 6.Задача о       2       -         2      Защита     Выполнение   Модели голо- Итоги исследований, Собеседо-  [1] ,[3].

 странствую-                             рефератов  дифференци-  воломок.          рефераты.                   вание,

 щем торгов-                             практикум  рованных                                                                     оценива-

 це.                                               по реше-   заданий, про-                                                               вание ре-

                                                   нию задач.  ведение ис-                                                                 фератов.

                                                        следований.    

        1.             2.     3.         4.          5.                    6.                    7.                             8.                       9.                   10.             11    

 7.Задача о      1        -       1       Беседа       Подготовка                                                                   Самосто-    [1] ,[2],[5].    

 трех домах                                практи-     рефератов.                                                                     ятельная

 и трех ко-                                  кум по                                                                                              работа.

  лодцах.                                    решению

                                                    задач.        

 8. Задачи на  2        -         2      Защита                                                        Рефераты.                  Оценива-   [1] ,[2],[5].

 раскраску.                                рефератов                                                                                       ние рефе-

                                                                                                                                                            ратов.

 9. Итоговое   1       -         1                                                                                                              Контроль-

 занятие.                                                                                                                                             ная рабо-

                                                                                                                                                            та.

 Всего за        16      3       13                                                                                                        

 Курс.

-7-

4.Содержание программы.

Тема № 1.

Введение. Первое знакомство с графами. Понятие “граф”. Элементы графа. Маршрут. Цепь (путь). Цикл. Ориентированный граф. Двудольный граф. Дерево. Полный граф. Степень вершины графа. Изолированная вершина графа. Концевая (висячая) вершина. Четные, нечетные графы. Однородные графы. Свойства графа.

Тема № 2.

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

Тема № 3.

Понятие “комбинаторная задача”. Дерево возможных вариантов. Основные правила комбинаторики.

Тема № 4.

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

Тема № 5.

Легенды, связанные с лабиринтами. Понятие “лабиринт” в математике . Существуют ли безвыходные лабиринты? Правила выхода из лабиринта.

 Тема № 6.

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

-8-

Тема № 7.

Задача о трех домах и трех колодцах . Плоский граф.  Теорема Эйлера для плоского графа.

Тема № 8.

Правильная раскраска. Проблема четырех красок. Условия возможности окраски графа (карты) двумя ,тремя цветами.  

-9-

5. Методическое содержание программы.

1. Введение. Первое знакомство с графами.

Основная цель:

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

-рассмотреть свойства графа.

В результате изучения данной единицы усвоения ученик должен:

-знать ,что граф - конкретная модель математических структур,

2. виды графов,
3. свойства графов;

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

-уметь: 

4. перекодировать информацию,
5. читать различные графические схемы и модели,
6. строить различные графические схемы и модели.

2. Решение логических задач с помощью графических схем.

Основная цель:

-ввести понятие логической задачи,

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

В результате изучения данной единицы усвоения ученик должен:

-знать ,что такое логическая задача,

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

-10-

-понимать, что  такое объект и что такое связи между объектами;

-уметь: 

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

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

3.Решение комбинаторных задач:

Основная цель:

- ввести понятие комбинаторной задачи,

- познакомить с основными правилами комбинаторики,

- ввести понятие дерева возможных вариантов.

В результате изучения данной единицы усвоения ученик должен:

-знать ,что такое комбинаторная задача,

7. основные правила комбинаторики,
8. алгоритмы, позволяющие провести упорядоченное перечисление вариантов “вручную”,

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

-уметь:  строить дерево возможных вариантов при решении задач,

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

4.Одним росчерком пера.

Основная цель:

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

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

-11-

В результате изучения данной единицы усвоения ученик должен:

-знать:

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

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

-уметь: 

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

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

5. Путешествия по лабиринтам.

Основная цель:

22. ввести понятие  лабиринта в математике,
23. рассмотреть правила выхода из лабиринта.

В результате изучения данной единицы усвоения ученик должен:

      -знать:

13. безвыходных лабиринтов нет,
14. правила выхода из лабиринта,

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

-уметь: 

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

        6. Задача о странствующем торговце.

Основная цель:

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

-12-

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

В результате изучения данной единицы усвоения ученик должен:

      -знать:

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

-понимать, что двойственная задача представляет практический интерес,

-уметь:

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

7. Задача о трех домах и трех колодцах.

Основная цель:

- рассмотреть задачу о трех домах и трех колодцах,

- ввести понятие плоского графа,

28. рассмотреть теорему Эйлера для плоского графа.

В результате изучения данной единицы усвоения ученик должен:

  -знать:

22. определение плоского графа,
23. теорему Эйлера для плоского графа,
24. схему доказательства теоремы Эйлера для плоского графа,

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

-уметь:  решать различные задачи с помощью теоремы Эйлера .

-13-

  8. Задачи на раскраску.

Основная цель:

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

В результате изучения данной единицы усвоения ученик должен:

    -знать:

25. определение правильной раскраски,
26. условия возможности раскраски графа (карты) двумя, тремя цветами,

-уметь:  определять раскрашивается ли данная карта двумя или тремя цветами,

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

-14-

5.1. Методы и формы обучения.

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

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

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

5.2. Описание основных форм организации учебных занятий.

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

-15-

 6. Организация проведения аттестации учащихся .

                  Итоговая аттестация по результатам изучения курса “Элементы теории графов” предусмотрена с учетом портфолио ученика, то есть совокупности самостоятельно выполненных работ (схемы, рефераты, отчеты об исследованиях, контрольная работа) и документально подтвержденных достижений ( грамоты и дипломы).

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

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

-16-

   7. Список рекомендуемой литературы.

7.1. Обязательная литература:

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

7.2.Дополнительная литература:

8. Гарднер М. Математические досуги. – М. : Мир, - 1972.
9. Лихтарников Л.М. Задачи мудрецов. – М. : Просвещение, - 1996.
10. Мадер В.В. Математический детектив. - М. : Просвещение, - 1979.
11. Оре О. Графы и их применение. – М. : Мир, - 1965.
12. Студенецкая В.Н. Решение задач по статистике, комбинаторике и теории вероятностей. – Волгоград : Учитель,- 2005.
13. Уилсон Р. Введение в теорию графов. - М. : Мир, - 1977.
14. Элективные курсы образовательной области “Математика”/  Информационный и  научно методический журнал “Профильная школа”, - 2004 - № 5 - стр.14.