Задачи на графах программа

Вид материала

Программа

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

Подобный материал:

• Задачи на графах. 16 Задачи на графах., 319.52kb.
• Задачи на графах. 17 Задачи на графах., 255.85kb.
• Задачи многокритериальной оптимизации; задачи исследования операций на графах; сетевое, 57.95kb.
• Требования к реализации программы оценки : все методы должны быть применимы для перебора, 53.14kb.
• Лекция 12: Алгоритмы на графах и деревьях, 395.7kb.
• Удк 681 001. 63 Эволюционные процедуры решения комбинаторных задач на графах, 135.09kb.
• Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов, 12.79kb.
• Задачи анализа топологии, 366.95kb.
• Программа дисциплины Алгоритмы на графах Семестр, 13.21kb.
• Программа дисциплины Методы оптимизации Семестры, 21.07kb.

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

Национальный институт образования


ЗАДАЧИ НА ГРАФАХ


Программа

курса по выбору для учащихся

учреждений, обеспечивающих получение

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

с 12-летним сроком обучения


Минск 2007

Авторы-составители: Пронжилло Ольга Олеговна — преподаватель кафедры прикладной математики и информатики БГПУ им. М. Танка; Мельников Олег Исидорович — доктор пед. наук, доцент кафедры уравнений математической физики БГУ; Морозов Алексей Алексеевич — старший преподаватель кафедры прикладной математики и информатики БГПУ им. М. Танка.


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


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


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

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

Курс «Задачи на графах» рекомендуется учащимся 11-12 классов. К этому времени многие из них уже имеют достаточно высокий уровень развития абстрактного мышления, умеют строить модели задач в рамках некоторой математической теории, имеют навыки алгоритмизации и сформированные познавательные интересы. Программа курса по выбору «Задачи на графах» рассчитана на 34 часа (1 час в неделю).

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

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

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

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

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

Рекомендуемые формы и методы проведения занятий


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

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

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

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

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

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

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

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

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

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

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


Содержание


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

Задачи, решаемые с помощью графов (головоломки, комбинаторные и прикладные задачи). Определение графа. Вершины и ребра. Смежность и инцидентность. Изображения графов. Степени вершин. Лемма «о рукопожатиях» и следствие из нее. Полный граф. Пустой граф. Подграф. Пути, цепи и циклы в графах. Связность. Компоненты связности. Двудольные графы. Ориентированные графы. Вершины и дуги. Степени исхода и степени захода. Матрицы: матрица порядка (m  n), квадратная матрица, симметричная матрица, бинарная матрица, сложение и умножение матриц. Основные способы задания графа: матрица смежностей, списки смежных вершин. Решение задач.


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

Массивы. Одномерные и двумерные массивы. Записи. Операции над записями. Динамические структуры: очереди, стеки, линейные списки. Определение базовых операций над очередью, стеком, линейным списком. Представление динамических структур в виде линейных массивов. Ссылки и динамические переменные. Использование ссылок для организации динамических структур. Текстовые файлы. Операции над текстовыми файлами. Оценка сложности алгоритмов.


Деревья

Задачи, приводящие к понятию дерева. Определение дерева. Лес. Корневые деревья. Свойства деревьев. Двоичные деревья. Полные двоичные деревья. Представления деревьев в памяти компьютера. Обходы двоичных деревьев: прямой, обратный (симметричный), концевой. Алгоритм симметричного обхода двоичного дерева. Двоичное дерево поиска. Вставка узла в дерево поиска. Построение дерева поиска. Применение двоичных деревьев в задачах поиска и сортировки. Оценка сложности алгоритмов, в которых используются двоичные деревья. Решение задач.


Обходы графа

Задачи, приводящие к понятию обходов графа (задача о лабиринте; задачи на шахматной доске; задача о мостах; задача о рисовании фигур одним росчерком). Поиск в ширину. Поиск в глубину. Исчерпывающий поиск с возвратом. Применение алгоритмов поиска в графе для решения задач (определение связных компонент, определение двудольности графа, нахождение кратчайшего расстояния между вершинами, построение множества всех циклов в графе). Эйлеровы графы. Эйлеров цикл. Эйлерова цепь. Критерий эйлерова графа. Алгоритм построения эйлерова цикла. Оценка сложности алгоритмов обхода графа. Решение задач.


Взвешенные графы

Взвешенные графы. Матрица весов. Остовный подграф. Минимальное остовное дерево (МОД). Алгоритм Прима построения МОД. Кратчайший путь между вершинами. Алгоритм Дейкстры нахождения кратчайшего пути между вершинами в орграфе. Дерево кратчайших путей. Оценка сложности алгоритма Дейкстры. Решение задач.


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

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

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

Учащиеся овладеют следующими способами деятельности:

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

Изучение данного курса по выбору предполагает:

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

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

1. Ахо, А. Структуры данных и алгоритмы / А. Ахо, В. Хопкрафт, Д. Ульман. — М.: Издательский дом «Вильямс», 2000. - 384 с.
   
2. Березина, Л. Ю. Графы и их применение /Л. Ю. Березина. — М.: Просвещение, 1979. — 143 с.
   
3. Иванов, Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие / Б. Н. Иванов. — М.: Лаборатория базовых знаний, 2003. — 288 с.
   
4. Кормэн, Т. Х. Алгоритмы: построение и анализ / Т. Х. Кормэн, Ч. И. Лейзерсон, Р. Л. Ривест. — М.: МЦНМО, 2000. — 960 с.
   
5. Котов, В. М. Информатика: методы алгоритмизации: 10-11 классы / В. М. Котов, О. И. Мельников. — Мн.: Народная асвета, 2000. — 221 с.
   
6. Лекции по теории графов. / В. А. Емеличев, О. И. Мельников и др. — М.: Наука, 1990. — 382 с.
   
7. Мельников, О. И. Занимательные задачи по теории графов: Учебно-метод. пособие / О. И. Мельников. — Мн.: ТетраСистемс, 2001. — 144 с.
   
8. Новиков, Ф. А. Дискретная математика для программистов. Учебник для вузов / Ф. А. Новиков. — 2-е изд. — СПб.: Питер, 2006. — 364 с.
   
9. Окулов, С. М. Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. — 341 с.
   
10. Уилсон, Р. Введение в теорию графов / Р. Уилсон. — М.: Мир, 1977. — 208 с.
    
11. Харланов, А. А. Методическое пособие для учителей и преподавателей средних учебных заведений нового типа в классах с углубленным изучением информатики: Пособие для учителей, работающих в профильных классах с углубленным изучением информатики, в форме поурочных разработок для преподавания темы «Решение задач с использованием графов» / А. А. Харланов. — Мн.: ИПКиПРРиСО, 1997. — 72 с.