Geum.ru

Рабочая учебная программа по дисциплине «Элементы теории графов» для ооп «050100. 62 -педагогическое образование» Профиль Математика по циклу б 3- дисциплины профессионального цикла

Вид материалаРабочая учебная программа

Содержание


Очная форма обучения
В области педагогической деятельности
В области профессиональной деятельности
В результате изучения дисциплины студент должен
2. Учебно-тематическое планирование
Аудиторные занятия
3. Содержание дисциплины
Плоские и планарные графы. Теорема Эйлера для плоского графа
Поиск в ширину, поиск в глубину и связанные с ними задачи
Эйлеровы графы. Уникурсальные фигуры. Лабиринты
Гамильтоновы графы. Решение задачи Эйлера о шахматном коне
Задача коммивояжера. Прямое ветвление и метод Катта–Мурти
Ориентированные графы. Транспортные сети и потоки. Теорема Гейла о насыщении.
Двудольные графы. Паросочетания. Теорема о сватовстве
Перечень тем лекционных занятий
Перечень тем занятий, реализуемых в активной и интерактивной формах
4. Самостоятельная работа и организация контрольно-оценочной деятельности
5. Учебно-методическое и информационное обеспечение дисциплины
7. Сведения об авторах программы
Подобный материал:

Министерство образования и науки РФ
Государственное образовательное учреждение
высшего профессионального образования
«Уральский государственный педагогический университет»
Факультет математический

Кафедра геометрии


РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА


по дисциплине


«Элементы теории графов»


для ООП «050100.62 –Педагогическое образование»

Профиль Математика

по циклу Б 3– Дисциплины профессионального цикла
(Курсы по выбору)


Очная форма обучения

Курс – 2

Семестр – 4

Объем в часах всего – 64

в т.ч.: лекции – 8

практические занятия – 14

самостоятельная работа – 42

Зачет – 6 семестр





Екатеринбург 2011




Рабочая учебная программа по дисциплине «Элементы теории графов»


ГОУ ВПО «Уральский государственный педагогический университет»

Екатеринбург, 2011. – 13 с.


Составители:

Унегова Т.А., к. ф.-м. н., доцент, доцент каф. геометрии УрГПУ


Рабочая учебная программа обсуждена на заседании кафедры геометрии УрГПУ

Протокол от 7 апреля 2011 г. № 8


Зав. кафедрой _________________ Н.В. Дударева


Декан математического факультета _________________ В.П. Толстопятов

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

1.1. Цели и задачи изучения дисциплины «Элементы теории графов»

Цели

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

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


1.2. Место дисциплины в структуре ПрОП

Дисциплина «Элементы теории графов» является дисциплиной цикла Б 3 – Дисциплины профессионального цикла (курсы по выбору).


Требования к входным знаниям, умениям и компетенциям студента, необходимым для изучения дисциплины «Элементы теории графов»:

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

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

Владеть:
  • навыками представления информации;
  • навыками интерпретации информации в различных формах ее представления;


Дисциплина «Элементы теории графов» является предшествующей для изучения следующих дисциплин подготовки бакалавра по направлению «Педагогическое образование» (профиль «Математика»):
  • Методика обучения и воспитания в математическом образовании.
  • Естественнонаучная картина мира.
  • Элементарная математика.
  • Практикум по решению задач по математике.
  • История математики.
  • Курсы по выбору студента.


1.3. Требования к результатам освоения дисциплины:

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

Общекультурные компетенции

ОК-1 – Владеет культурой мышления, способен к обобщению, анализу, восприятии информации, постановке цели и выбору путей её достижения.

ОК-6 – Способен осуществлять логически верно устную и письменную речь.

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

ОК-16 – Способен использовать навыки публичной речи, ведения дискуссии и полемики.

Профессиональные компетенции

Общепрофессиональные

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

ОПК-3 – Владеет основами речевой профессиональной культуры.

ОПК-6 – Способен к подготовке и редактированию текстов профессионального и социально значимого содержания.

В области педагогической деятельности

ПК-1 – Способен реализовывать учебные программы базовых и элективных курсов в различных образовательных учреждениях.

ПК-4 – Способен использовать возможности образовательной среды, в том числе информационной, для обеспечения качества учебно-воспитательного процесса.

В области профессиональной деятельности

ПК-12 – Способен демонстрировать, применять, критически оценивать и пополнять математические знания.

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

Уметь:
  • логично и последовательно демонстрировать освоенное знание;
  • приводить примеры и контрпримеры в процессе изложения теоретического материала;
  • применять простейшие алгоритмы для решения конкретных задач;

Владеть:
  • терминологией предметной области «Теории графов»;
  • различными алгоритмами «Теории графов»;
  • навыками отбора геометрического материала для выбранной темы и ее популяризации.


ПК-13 – Готов организовывать различные виды учебно-исследовательской и проектной деятельности обучающихся.

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

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

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

Владеть
  • способами организации исследования при решении задач по дисциплине.



1.4. Объем дисциплины и виды учебной работы


Общая трудоемкость дисциплины составляет 2 зачетные единицы.

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


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


2.1. Учебно-тематический план очной формы обучения

6 семестр

№

п/п
Наименование раздела, темы
Всего трудоемкость
Аудиторные занятия
Самостоятельная работа

Всего
Лекции
Практические

1.
Определение графа и его элементов. Маршруты в графе. Связные графы. Деревья
6
2
2



4

2.
Плоские и планарные графы. Теорема Эйлера для плоского графа
10
4
2
2
6

3.
Поиск в ширину, поиск в глубину и связанные с ними задачи
8
2



2
6

4.
Эйлеровы графы. Уникурсальные фигуры. Лабиринты
8
4
2
2
4

5.
Гамильтоновы графы. Решение задачи Эйлера о шахматном коне
8
2



2
6

6.
Задача коммивояжера. Прямое ветвление и метод Катта–Мурти
6
2



2
4

7.
Ориентированные графы. Транспортные сети и потоки. Теорема Гейла о насыщении.

8
4
2
2
4

8.
Двудольные графы. Паросочетания. Теорема о сватовстве
10
2



2
8




Итого
64
22
8
14
42


3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ




  1. Определение графа и его элементов. Маршруты в графе. Связные графы. Деревья

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

Определение графа порядка k. Вершины и ребра графа. Изолированные вершины. Нуль-граф и полный граф. Число ребер полного графа. Подграфы. Дополнение графа.

Определение маршрута в графе. Цепи и простые цепи. Циклические маршруты. Определение связного графа. Определение дерева. Некоторые свойства деревьев.

Определение степени вершины графа. Четные и нечетные вершины. Лемма о рукопожатиях и ее следствие о количестве нечетных вершин в графе. Теоремы о степенях вершин графа (о наличии в графе по крайней мере двух вершин одинаковой степени и др.).

  1. Плоские и планарные графы. Теорема Эйлера для плоского графа

Определения плоского и планарного графов. Теорема Эйлера для дерева и для связного плоского графа. Максимально плоские графы и их свойства. Доказательство непланарности «полного пятиугольника»

Решение занимательных задач и задач олимпиадного характера. Доказательство непланарности графа «домики и колодцы». Формула Эйлера и система прямых линий на плоскости.

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

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

Построение кратчайшего маршрута. Вес (стоимость) ребра. Графы со взвешенными ребрами. Построение циклического маршрута, соединяющего две избранные вершины, с помощью алгоритма Форда-Беллмана.

Определение остовного дерева графа. Первый жадный алгоритм (алгоритм Прима) построения остовного дерева наименьшего суммарного веса. Второй жадный алгоритм (алгоритм Дийкстры) построения остовного дерева с кратчайшими путями от корня до любой вершины.

  1. Эйлеровы графы. Уникурсальные фигуры. Лабиринты

Определение эйлерова графа. Критерий эйлеровости графа. Алгоритм построения эйлерова цикла в эйлеровом графе. Критерий существования в графе эйлеровой цепи. Уникурсальные фигуры.

Лабиринты в жизни и лабиринты в математике. Решение лабиринта. Использование структур, подобных лабиринтам, в технике.

  1. Гамильтоновы графы. Решение задачи Эйлера о шахматном коне

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

  1. Задача коммивояжера. Прямое ветвление и метод Катта–Мурти

Формулировка задачи коммивояжера. Решение задачи коммивояжера методом ветвей и границ (разбираются прямое ветвление и метод Катта-Мурти).

  1. Ориентированные графы. Транспортные сети и потоки. Теорема Гейла о насыщении.

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

Определение транспортной сети. Поток в сети и его величина. Алгоритм Форда-Фалкерсона о построении в сети максимального потока. Основная теорема теории траспортных сетей (теорема Гейла о насыщении)

  1. Двудольные графы. Паросочетания. Теорема о сватовстве

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


Перечень тем лекционных занятий

  1. Определение графа и его элементов. Маршруты в графе. Связные графы. Деревья

Лекция 1. Определение графа и его элементов. Маршруты в графе. Связные графы. Деревья.

  1. Плоские и планарные графы. Теорема Эйлера для плоского графа

Лекция 1. Плоские и планарные графы. Теорема Эйлера для плоского графа

  1. Эйлеровы графы. Уникурсальные фигуры. Лабиринты

Лекция 1. Эйлеровы графы.

  1. Ориентированные графы. Транспортные сети и потоки. Теорема Гейла о насыщении.

Лекция 1. Ориентированные графы.


Перечень тем практических занятий

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


Вопросы для контроля и самоконтроля

  1. Сформулируйте задачу о семи мостах.
  2. Дайте определение графа.
  3. Как определяется порядок графа?
  4. Что такое вершины графа и его ребра?
  5. Что называется степенью вершины графа?
  6. Какие вершины называются четными (нечетными)?
  7. Как формулируется лемма о рукопожатиях?
  8. Может ли сумма степеней всех вершин графа быть числом нечетным? Поясните, почему.
  9. Какой граф называется полным, а какой нулевым?
  10. Дайте определение подграфа и дополнения графа.
  11. Дайте определение маршрута (циклического маршрута) в графе.
  12. Какой граф называется связным?
  13. Дайте определение графа, который является деревом (лесом).
  14. Какие два графа называются изоморфными?
  15. Какой граф называется плоским, а какой планарным?
  16. Приведите примеры планарных и непланарных графов.
  17. Сформулируйте теорему Эйлера для дерева и для плоского графа.
  18. Что такое максимально плоский граф?
  19. Перечислите свойства максимально плоских графов.
  20. Опишите алгоритм поиска в ширину (поиска в глубину).
  21. Покажите, как решается задача о построении в графе кратчайшего маршрута.
  22. Дайте определение графа со взвешенными ребрами.
  23. Какая задача решается с помощью алгоритма Форда-Беллмана. Опишите этот алгоритм.
  24. Что называется остовным деревом графа?
  25. Какая задача решается с помощью алгоритма Прима (первого жадного алгоритма)? Опишите этот алгоритм.
  26. Какая задача решается с помощью алгоритма Дийкстры (второго жадного алгоритма)? Опишите этот алгоритм.
  27. Как определяется эйлеров цикл (эйлерова цепь) в графе?
  28. Какой граф называется эйлеровым?
  29. Сформулируйте критерий эйлерова графа.
  30. Сформулируйте критерий существования в графе эйлеровой цепи.
  31. Что называется лабиринтом?
  32. Опишите, как строится граф, соответствующий лабиринту.
  33. Что называется решением лабиринта?
  34. Что можно сказать о существовании решения произвольного лабиринта?
  35. Перечислите различные способы решения лабиринта.
  36. Какой цикл в графе называется гамильтоновым?
  37. Какой граф называется гамильтоновым графом?
  38. Существует ли критерий гамильтонова графа?
  39. Сформулируйте задачу Эйлера о ходе шахматного коня.
  40. Опишите алгоритм обхода ходом шахматного коня квадратной доски любого размера.
  41. Какая задача называется задачей коммивояжера?
  42. Опишите суть метода ветвей и границ решения задачи коммивояжера.
  43. Что такое орграф?
  44. Как дается понятие связности в случае орграфа?
  45. Сформулируйте признак сильносвязного графа.
  46. Опишите решение задачи об одностороннем движении транспорта.
  47. Что называется транспортной сетью?
  48. Что называется потоком в сети?
  49. Что называют величиной потока?
  50. Опишите алгоритм Форда-Фалкерсона о построении в сети максимального потока.
  51. Сформулируйте теорему Гейла о насыщении.
  52. Какие графы называются двудольными (трехдольными)? Приведите примеры.
  53. Что называется паросочетанием в двудольном графе?
  54. Опишите суть метода чередующихся цепей для построения максимального паросочетания в двудольном графе.
  55. Сформулируйте теорему о свадьбах.


Перечень тем занятий, реализуемых в активной и интерактивной формах

Все лекционные и практические занятия реализуются в активной и интерактивной формах.

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

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


4. САМОСТОЯТЕЛЬНАЯ РАБОТА И ОРГАНИЗАЦИЯ КОНТРОЛЬНО-ОЦЕНОЧНОЙ ДЕЯТЕЛЬНОСТИ

  1. Темы, вынесенные на самостоятельное изучение



  1. Перечисление графов.
  2. Регулярные графы.
  3. Деревья. Их свойства и приложения.
  4. Решение задачи о шахматном коне на прямоугольной доске произвольного размера.



  1. Примерные темы контрольных заданий
  1. Решение нестандартных задач с использованием свойств плоского графа.
  2. Построение эйлеровой цепи (цикла) в графе.
  3. Решение задач с применением алгоритмов поиска в ширину и поиска в глубину.
  4. Построение максимального потока в транспортной сети.
  5. Решение задачи коммивояжера.



  1. Материалы промежуточной аттестации

(примерные вопросы для курсового зачета)


Перечень вопросов на проверку формирования компетенций

ОК-1, ОК-6, ОК-16, ОПК-3, ПК-12
  1. Определение графа и его элементов.
  2. Маршруты, цепи, циклы.
  3. Связный граф. Деревья.
  4. Степень вершины графа. Теоремы о степенях вершин графа.
  5. Изоморфные графы.
  6. Плоские и планарные графы и их свойства.
  7. Теорема Эйлера для плоского графа.
  8. Поиск в ширину, поиск в глубину и связанные с ними задачи.
  9. Эйлеровы графы (Критерий алгоритм построения эйлерова цикла).
  10. Гамильтоновы графы. Задача коммивояжера.
  11. Орграфы и их свойства.
  12. Транспортные сети и потоки в сетях. Построние максимального потока.
  13. Двудольные графы. Паросочетания. Теорема о сватовстве.


Перечень вопросов на проверку формирования компетенций

ОК-8, ОПК-3, ОПК-4, ОПК-6, ПК-12, ПК-13

  1. В предложенном математическом тексте выделите структуру (определения понятий, примеры, свойства, формулировки теорем, доказательства теорем) и составьте планы доказательств теорем.
  2. Составьте опорный конспект предложенного математического текста; одного из изученных разделов дисциплины; вопроса, вынесенного на самостоятельное изучение.
  3. Дано доказательство некоторой геометрической теоремы. Сформулируйте эту теорему, выделите ее условие и заключение.
  4. Составьте глоссарий к материалу предложенного математического текста.
  5. Поставьте вопросы, направленные на проверку усвоения предложенного математического материала.
  6. Составьте алгоритм решения задачи по материалам предложенного математического текста.
  7. Укажите логическую последовательность изложения указанной темы.
  8. Расположите данные разрозненные фрагменты изученного курса в их логической последовательности.
  9. Составьте подробный план презентации курса «Элементы теории графов».
  10. Опишите возможности использования изученного материала для организации исследовательской (проектной) деятельности учащихся.
  11. Продумайте последовательность организации исследовательской деятельности учащихся при подготовке реферата по предложенной теме.
  12. Предложите несколько тем и планов рефератов (проектов) для учащихся разных классов по данной теме.
  13. Составьте развернутый план реферата по заданной теме, используя представленную литературу.
  14. Проанализируйте реферат (проект), подготовленный школьником, сформулируйте рекомендации по организации дальнейшей работы.
  15. Сформулируйте затруднения, которые могут возникнуть у учащегося при работе над содержанием реферата (проекта) по данной теме. Предложите пути их устранения



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



5. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ


5.1. Рекомендуемая литература


Основная

  1. Баврин И. И. Дискретная математика : учебник для студентов вузов по спец. «Физика», «Химия», «Биология» и «География». М.: Высш.шк., 2007. 200 с. (5 экз.)
  2. Гаврилов Г. П. , Сапоженко А. А. Сборник задач по дискретной математике : учеб. пособие для вузов. М. : Наука , 1977 . 368 с.. (10 экз)
  3. Мурзинова Г.С. Дискретная математика : учебное пособие [для студентов пед. вузов]. Урал. гос. пед. ун-т. Екатеринбург: [б.и.], 2008. 85 с.

(91 экз.)

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

  1. Березина Л. Ю. Графы и их применение. М.: Просвещение, 1979. (1 экз.)
  2. Генкин С. А. Ленинградские математические кружки. Киров : АСА, 1994. 272 с. (1 экз.)
  3. Гик, Е. Я. Математика и шахматы : Книга для школьников, учителей математики. М : Бюро Квантум, 2010. 176 с. (библиотечка Квант: вып 15. Приложение к журналу «Квант» №2 2010) (1 экз.)
  4. Лекции по теории графов / В.А. Емеличев и др. М.: Наука, 1990. 384с. (3 экз.)
  5. Оре О., Врублевская И. Н. , Воробьев Н. Н. Теория графов. М. : Наука , 1980 . 336 с. (7 экз)
  6. Прасолов В. В. Графы ребер многогранников // Математическое образование. – 2000. – № 1 (12), январь-март. – С. 2-12. (1 экз.)
  7. Райтер Г., Сонин И. Наглядная интерпретация некоторых алгоритмов на графах // Математическое просвещение. – 1999. – Сер. 3, вып. 3. – С. 208-212.
  8. Саркисян А. А., Колягин Ю. М. Познакомьтесь с топологией. М.: Просвещение, 1976. 80 с. (2 экз.)
  9. Уилсон, Р. Введение в теорию графов. М.: Мир, 1977. (3 экз.)
  10. Харари Ф., Палмер Э., Гаврилов Г. П. Перечисление графов М. : Мир , 1977 . 326 с. (2 экз.)



7. СВЕДЕНИЯ ОБ АВТОРАХ ПРОГРАММЫ


Унегова Татьяна Александровна

кандидат физико-математических наук

доцент

доцент кафедры геометрии УрГПУ


Раб. телефон (8-343) 371-29-10


РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА


для ООП «050100.62 –Педагогическое образование»

Профиль Математика

по циклу Б 3– Дисциплины профессионального цикла
(Курсы по выбору)


Подписано в печать Формат 60х84/16

Бумага для множительных аппаратов. Усл. печ. л. 1,5

Тираж экз. Заказ

Уральский государственный педагогический университет.

620017 Екатеринбург, пр. Космонавтов, 26