Рабочая программа курса по выбору «Применение теории графов при решении математических задач» 9 класс.
календарно-тематическое планирование по алгебре (9 класс) на тему

Министерство образования и науки Республики Татарстан.

Муниципальное бюджетное образовательное учреждение «Большеключинская СОШ  Зеленодольского муниципального района РТ»

Рабочая программа курса по выбору «Применение теории графов при решении математических задач»

9 класс.

Разработана Юсуповой Л.А,  учителем математики первой квалификационной категории МБОУ «Большеключинская СОШ ЗМР РТ» С.Большие Ключи Зеленодольского муниципального района Республики Татарстан

2014 год

Паспорт

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

«Применение теории графов при решении математических задач»

Тип программы:  программа курса по выбору по математике в 9   классе

Статус программы: рабочая программа курса по выбору.

Назначение программы:

• для обучающихся программа обеспечивает реализацию их права на информацию об образовательных услугах, права на выбор образовательных услуг и права на гарантию качества получаемых услуг;
• для педагогических работников МБОУ «Большеключинская СОШ ЗМР РТ» программа определяет приоритеты в содержании основного общего образования и способствует интеграции и координации деятельности по реализации общего образования;
• для администрации МБОУ «Большеключинская СОШ ЗМР РТ» программа является основанием для определения качества реализации общего образования.

Категория обучающихся: учащиеся 9   класса МБОУ «Большеключинская СОШ ЗМР РТ»

Сроки освоения программы: 1 год

Объем учебного времени: 34 часа.

Форма обучения: очная.

Режим занятий: 1 час в неделю

Формы контроля: текущий контроль, (итоговый тест).

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

Рабочая программа курса по выбору составлена на основании следующих нормативно-правовых документов:

1. Федерального компонента государственного стандарта основного общего образования по математике, утвержденного приказом Минобразования России от 5.03.2004 г. № 1089.

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

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

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

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

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

Цели курса:

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

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

1. Сформировать навыки использования нетрадиционных методов решения задач; 
2. Развивать умения самостоятельно приобретать и применять знания; 
3.Сформировать у учащихся устойчивый интерес к предмету для дальнейшей самостоятельной деятельности при подготовке к ОГЭ и к олимпиадам; 

4.Сформировать представление об основных понятиях теории графов и областях её применения.

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

Виды деятельности на занятиях:

лекция учителя, беседа, практикум, консультация, ИКТ технологии.

Особенности курса:

1. Краткость изучения материала.
2. Практическая значимость.
3. Нетрадиционные формы изучения материала.

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

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

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

2. Основные теоремы теории графов, и их следствия.
3. Задачи, решаемые с помощью графов.

    Уникурскальные фигуры. Росчерки. Лабиринты.  

4. Применение графов к решению комбинаторных задач.

     Деревья. Лес.

5. Задача о кёнигсбергских мостах.

      Эйлеровы линия, граф и путь.

6. Применение теории графа в науке и жизни.

     Приложение теории графов в геометрии, в сетевом планировании и управлении, в   физике

       и электротехнике, в химии, биологии, географии, в педагогике, в играх и головоломках.       

7. Проблемные задачи теории графов.

       Задача о коммивояжере. Проблема четырёх красок. Задача о клике . Нахождение минимального стягивающего (остовного) дерева.

8. Решение логических задач. Графическое моделирование
9. Решение олимпиадных задач.

Возможные критерии оценок.

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

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

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

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

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

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

должны знать:

-понятие графа;

-алгоритм решения задач с помощью графов;

-нестандартные методы и приемы решения  задач.

должны уметь:

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

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

• уметь пользоваться математической символикой;

• применять рациональные приёмы вычислений;

• самостоятельно работать с методической литературой.

Календарно – тематический план

Литература:

1. Березина Л.Ю. «Графы и их применение», М., Просвещение, 1979г.
2. Виленкин Н.Я. «Популярная комбинаторика», М., Наука, 1975г.
3. Гамов Г. «Комбинаторные принципы в генетике», М., Мир, 1968г
4. Галкин Е.В. «Нестандартные задачи по математике: задачи логического характера», М., Просвещение, 1996г.
5. Гарднер М. «Математические досуги», М., 1972г.
6. Зайкин М.И. «Математический тренинг: развиваем комбинационные способности», М., Владос, 1996г.
7. Мудров В.И. «Задача о коммивояжере», М., Знание, 1969г.
8. Савин А.П. «Математические миниатюры», М., Детская литература, 1991г.
9. Сешу С., Рид М. «Линейные графы и электрические цепи», М., Высшая школа, 1971г.
10. Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. 2009. 232 с.

Приложение.

ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ.

     Рассмотрим некоторые задачи, при решении которых используется теория графов. Они считаются классическими. 
     Задача 1. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств: 
     1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок; 
     2. учитель литературы может дать один, либо второй, либо третий урок; 
     3. математик готов дать либо только первый, либо только второй урок; 
     4. преподаватель физкультуры согласен дать только последний урок. 
     Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы? 
     Решение. Без сомнения, эту задачу можно решить путем обыкновенного перебора всех возможных вариантов, но решение будет наиболее простым, если вычертить граф. Требуемый граф изображен на рисунке 4.1. 
     Рассмотрим еще одну задачу, решением которой также является граф. 
     Задача 2. В составе экспедиции должно быть 6 специалистов: биолог, врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, из которых и нужно выбрать участников экспедиции; условные имена претендентов: A, B, C, D, E, F, G и H. Обязанности биолога могут исполнять E и G, врача - A и D, синоптика - F и G, гидролога - B и F, радиста - С и D, механика - C и H. Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедицию, если F не может ехать без B, D - без H и C, C не может ехать вместе с G, A - вместе с B? 
     Решение. Процесс решения задачи во всех подробностях мы рассматривать не будем. Заметим только, что задать возможный вариант решения, то есть описать точный состав экспедиции, можно с помощью четного графа, в котором вершины разделены на две группы, а ребра могут соединять лишь вершины разных групп. 
     Применительно к задаче об экспедиции одна группа вершин есть группа из 8 кандидатов, а вторая - из 6 должностей.
     Решение задачи изображено на четном графе (рис 4.2). 
     Задача 3. Планета имеет форму выпуклого многогранника, причем в его вершинах расположены города, а каждое ребро является дорогой. Две дороги закрыты на ремонт. Докажите, что из любого города можно проехать в любой другой по оставшимся дорогам. 
     Решение. Пусть A и B - данные города. Докажем сначала, что из A в B можно было проехать до закрытия на ремонт двух дорог. Рассмотрим для этого проекцию многогранника на некоторую прямую,  не перпендикулярную ни одному из его ребер (при такой проекции вершины многогранника не сливаются). 
     Пусть A' и B' - проекции точек A и B, а M' и N' - крайние точки проекции многогранника (в точки M' и N' проецируются вершины M и N). Если идти из вершины A так, что в проекции движение будет происходить по направлению от M' к N' , то, в конце концов, мы обязательно попадем в вершину N. Аналогично из вершины B можно пройти в N. Таким образом, можно проехать из A в B (через N). 
     Если полученный путь из A и B проходит через закрытую дорогу, то есть еще два объезда по граням, для которых это ребро является общим. Вторая закрытая дорога не может находиться сразу на двух этих объездах. Значит, из города A в город B можно проехать, по крайней мере, одним путем. 

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ШКОЛЬНОМ КУРСЕ МАТЕМАТИКИ.

     Рассмотренные задачи, которые используются в школе на уроках математики. Условно их можно классифицировать, подразделив на несколько групп: 
     1.Задачи о мостах. 
     2.Логические задачи 
     3.Задачи о "правильном" раскрашивании карт 
     4.Задачи на построение уникурсальных графов 
     Рассмотрим несколько типичных примеров решения задач каждого вида. Одной из наиболее известных задач о мостах является эйлерова задача; все остальные сформулированы похожим образом и решаются по тому же принципу. Основой применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Это выявление логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов. 
     Задача 2.1. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял? 
     Решение: Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности. Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены. 
     Задача 2.2. Какие буквы русского алфавита можно нарисовать одним росчерком?
     Ответ: Б, В, Г, 3, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я.
     Задача 2.3. В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде? Решение: Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику. 
     Иными словами, суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа. 
     Задача 2.4. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе - каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис - с Андреем, Галиной; Виктор - с Галиной, Дмитрием, Еленой; Галина - с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?
     Решение: Построим граф (рис. 5.1). Сыграно 7 игр. На рис. 5.2. граф имеет 8 ребер, следовательно, осталось провести 8 игр.
     Ответ: проведено 7 игр, осталось провести 8 игр.
     Задача 2.5. В школьном драматическом кружке решили ставить гоголевского "Ревизора". И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.
     - Ляпкиным-Тяпкиным буду я! - решительно заявил Дима. -
     С раннего детства я мечтал воплотить этот образ на сцене.
     - Ну хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.
     - ...А мне ~ Осипа, - не уступил ему в великодушии Дима.
     - Хочу быть Земляникой или Городничим, - сказал Вова.
     - Нет, Городничим буду я, - хором закричали Алик и Боря. -
     Или Хлестаковым, - добавили они одновременно.
     Удастся ли распределить роли так, чтобы исполнители были довольны?
     Решение: Построим граф для ситуации, описанной в задаче (рис. 5.3.).
     Граф с 10 вершинами и 10 ребрами. Надо выбрать из десяти пять ребер, не имеющих общих вершин: Дима - Осип, Вова - Земляника, Гена - Ляпкин-Тяпкин. Остается два случая: Алик - Хлестаков, Боря - Городничий или Алик - Городничий, Боря - Хлестаков. Как показывает граф, других решений нет.

Задачи для самостоятельного решения.

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

1. Пообедать – 20 мин.
2. Вымыть посуду – 20 мин.
3. Сделать уроки – 2 ч.
4. Постирать бельё с помощью стиральной машины – 1,5 ч.
5. Купить в магазине продукты – 40 мин.
6. Починить стул – 30 мин.
7. Пришить пуговицу к пиджаку – 10 мин.
8. Забрать младшего брата из сада – 40 мин.
9. Рассказать брату о делах в школе – 30 мин.

  б)  «Обед в кафе». Из предложенного меню составьте обед, который был бы не дорогим   по стоимости и соответствовал бы вашему вкусу (обед должен стоить не дороже 150 рублей и состоять из трёх блюд).

Меню.

      Первые блюда:                          Вторые блюда:                                Третьи блюда:

Борщ – 40 р.                                Рыба жаренная – 60 р.                         Компот – 15 р.

Молочный суп – 30 р.                Люля-кебаб – 110 р.                             Чай – 6 р.

Окрошка – 80 р.                                                                                          Десерт – 50 р.

2. Андрей, Борис, Владимир, Григорий, Дмитрий и Евгений при встрече обменялись каждый с каждым рукопожатием. Сколько всего было сделано рукопожатий?
3. В авторалли участвовало 5 автомашин «Нива» и 6 автомашин «Лада». Сколько существует различных вариантов для занятия первого места в этом ралли?
4. Сколько различных смешанных пар для игры в теннис можно образовать из восьми юношей и девушек?
5. Путешественник из пункта А в пункт С может попасть, доехав до промежуточного пункта В по одной из трёх существующих магистралей, а из В в С доехать либо поездом, либо такси. Сколько существует различных маршрутов между пунктами А и С?
6. У Ирины пять подруг: Вера, Зоя, Марина, Полина и Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг. Сколько таких вариантов?
7. Составьте все возможные двузначные числа из указанных цифр, используя в записи числа каждую цифру не более одного раза: а) 1, 6, 8. б) 0, 3, 4.
8. Составьте все возможные двузначные числа из цифр 1, 2, 3 при условии, что: а) цифры в числе не повторяются; б) допускается повторение цифр числа.
9. Пётр решил пойти на новогодний карнавал в костюме мушкетёра. В ателье проката ему предложили на выбор различные по фасону и цвету предметы: пять видов брюк, шесть камзолов, три шляпы, две пары сапог. Сколько различных карнавальных костюмов можно составить из этих предметов?
10. Три подруги были в белом, красном и голубом  платьях. Их туфли были тех же трёх цветов. Только у Тамары цвета платья и туфель совпадали. Валя была в белых туфлях. Ни платье, ни туфли Лиды не были красными. Определите цвет платья и туфель каждой из подруг.
11. Среди офицеров А, Б, В, Г – майор, капитан и два лейтенанта. А и один из лейтенантов – танкисты, Б и капитан – артиллеристы, А младше по званию, чем В. Определите род войск и воинское звание каждого из них.
12. Три товарища – Владимир, Игорь и Сергей – окончили один и тот же педагогический университет и преподают математику, физику и литературу в школах Тулы, Рязани и Ярославля. Владимир работает не в Рязани, Игорь – не в Туле. Рязанец преподаёт не физику, Игорь – не математику, туляк преподаёт литературу. Какой предмет и в каком городе преподаёт каждый из них?
13. Можно ли 15 телефонов соединить между собой так, чтобы каждый из них был связан ровно с 11 другими?
14. Девять школьников, разъезжаясь на каникулы, договорились, что каждый из них пошлёт открытки пятерым из остальных. Может ли оказаться, что каждый из них получит открытки именно от тех друзей, которым напишет сам?
15. В шахматном турнире в одном кругу участвуют 17 шахматистов. Верно ли, что в любой момент турнира найдётся шахматист, сыгравший к этому моменту чётное число партий (может бить, ни одной)?
16. Можно ли обвести карандашом, не отрывая его от бумаги и не проходя по одной линии дважды: а) квадрат с диагоналями; б) правильный пятиугольник с диагоналями?
17. Можно ли из проволоки, длиной 12 дм изготовить каркас куба с ребром 1 дм, не ломая проволоку на части?
18. В точке А расположен гараж для снегоочистительной машины. Водителю машины было поручено убрать снег с улиц части города, изображённой на рисунке. Может ли он закончить свою работу на том перекрёстке, где находится гараж, если по каждой улице своего участка города водитель будет проезжать только один раз?

19. Голодная лиса вышла из вырытой под деревом норы и начала бродить по лесу от дерева к дереву в поисках добычи. Чёрной линией изображён путь лисы. Наконец лиса устала и легла отдохнуть под одним из деревьев (дерево загораживает лису и её не видно). Где сейчас лиса? Под каким деревом находится её нора? Сколько решений имеет задача?

20.Какие из данных фигур можно обвести одним росчерком?