Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов»



Скачать 109.74 Kb.
Дата04.07.2013
Размер109.74 Kb.
ТипЛекции

Курс "Дискретная математика": теоретические основы и прикладные задачи для студентов-экономистов

Т.А. Панюкова, доцент кафедры
экономико-математических методов и статистики,
ГОУ ВПО Южно-Уральский государственный университет,
kwark@mail.ru


Введение

Дискретная математика всегда являлась одной из наиболее динамично развивающихся областей знаний. В настоящее время среди наиболее значимых областей применения методов дискретной математики находится область компьютерных технологий. Это объясняется необходимостью создания и эксплуатации электронных вычислительных машин, средств передачи и обработки информации, автоматизированных систем управления и проектирования. Например, практическая роль одного из важных разделов современной математики, теории графов, возросла во второй половине ХХ века в связи с проектированием различных автоматизированных систем управления и вычислительных устройств дискретного действия. Потребности программирования определяют развитие «стыка» информатики и математики (алгебры, математической логики, теории игр, общей теории систем и т.д.). Эта область знаний не исчерпывается дискретной математикой, однако она является характерной, основополагающей.

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

Дискретная математика и примыкающие к ней дисциплины изучаются во всех университетах, где осуществляется подготовка специалистов в областях программирования, математики, экономики, а также по техническим и гуманитарным дисциплинам. Лекции по теории графов читаются либо в виде отдельного курса (например, в ЮУрГУ он читается как «Комбинаторика и теория графов» для специальности 080801 «Прикладная информатика»), либо как часть более общего («Дискретная математика» для специальности 080116 «Математические методы в экономике»).

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

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

Так, курс состоит из следующих семнадцати лекций.

1. Основы элементарной теории множеств. Данный материал необходим для понимания последующих разделов курса.

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

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

8. Введение в теорию графов, основные понятия и определения.

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

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

11. Поиск эйлеровых и гамильтоновых циклов. Критерии эйлеровости графа. Задача китайского почтальона.

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

13. Укладка графов на плоскости. Приведены критерии планарности графа, а также алгоритм построения плоской укладки, если таковая существует.

14 – 16. Решение прикладных задач, в которых необходимо применить объекты теории графов: поиск кратчайшего пути, решение задач сетевого планирования и задачи о максимальном потоке.

17. Раскраски графов, жадные алгоритмы решения этой задачи.

Цели и задачи изучения дисциплины

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

Задачами курса являются следующие.

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

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

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

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

1) знать теоретические основы комбинаторики и теории графов;

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

3) уметь использовать полученные знания для решения прикладных задач;

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

Так как дискретная математика тесно связана с программированием, то контрольное задание для студентов должно учитывать этот факт. В качестве задания для самостоятельной работы студентам предлагается запрограммировать один из классических алгоритмов теории графов. Данная задача позволяет не только более глубоко изучить некоторые важные прикладные разделы теории графов, но и закрепить знания, полученные на курсах «Алгоритмизация и языки программирования» и «Объектно-ориентированное программирование».

Компьютерные технологии для задач теории графов

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

Например, существует разработка преподавателя Саратовского университета Печенкина В.В., называемая Grin [1]. Grin является простой, доступной, полезной для студентов и преподавателей университетов программой. Она может быть использована не только математиками, но и экономистами, социологами, всеми, кто так или иначе интересуется дискретными моделями. Одними из основных достоинств программы является простой и удобный интерфейс, легкость в освоении и работе (рис.1).


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

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

Следовательно, используя Grin, нет возможности с ее помощью продемонстрировать решение задач алгоритмизации с использованием инструментария теории графов.

Еще одним средством для работы с графами является библиотека GOBLIN [2]. Это библиотека классов, предоставляющая функции решения задач на графах. Данная программа является программным обеспечением с открытым исходным кодом и распространяется под лицензией GNU LGPL.

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

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

  • нахождение минимальных остовных деревьев и 1-деревьев;

  • нахождение решений задач о назначении всех типов;

  • нахождение паросочетаний, b-сочетаний и f-факторов;

  • нахождение решений многих других задач.

Библиотека также включает средства для решения некоторых NP-трудных задач, таких как симметрическая и асимметрическая задачи коммивояжера, задача о раскраске и пр.

Программа Graph Calculator, студенческий проект

Для того чтобы дать возможность студентам самостоятельно запрограммировать классические алгоритмы, был создан проект Graph Calculator.

Такая программа служит не только калькулятором для проверки правильности решения задачи, но и позволяет добиться следующих целей при преподавании теории графов [3]:

1) организация коллективной работы в группе и распределение задач между членами коллектива;

2) закрепление знаний и навыков, полученных в рамках курсов алгоритмизации и программирования;

3) закрепление материала курса «Дискретная математика», решение прикладных задач;

4) совершенствование навыков работы с литературными источниками.

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

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


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

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

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

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



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

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

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

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

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

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

Дополнительные модули программы

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

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

Модуль для решения задачи о назначениях. В качестве входных данных пользователю предлагается заполнить таблицу, соответствующую прибылям/убыткам, получаемыми организацией за занятость работника N на работе M. Число работников и работ совпадает. Пользователь самостоятельно выбирает, решается задача на минимум или на максимум. В качестве результата предоставляется список работников и назначенных им работ, а также общая сумма прибыли/убытков, полученных благодаря найденному распределению. Двудольный граф, полученный в процессе решения, отображается в окне редактирования (рис.4).



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

Специальные модули программы Graph Calculator

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

Например, для проверки работоспособности программы, в нее был подключен модуль поиска покрытия с упорядоченным охватыванием [4] и осуществлена анимация полученного результата (рис.5).

Рассмотренный в [4] алгоритм был построен для решения задачи моделирования процесса раскроя. Требовалось определить такую кратчайшую траекторию режущего инструмента, чтобы отрезанная от листа часть не требовала дополнительных разрезаний. Формально множество таких траекторий и определено как покрытие с упорядоченным охватыванием для плоского графа.

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



Рис.5. Поиск покрытия с упорядоченным охватыванием

Выводы

Создаваемый проект Graph Calculator позволяет студентам более глубоко освоить раздел теории графов. Несмотря на то, что каждый программирует только свой модуль, для отладки работы которого придется решить не одну задачу, остальные разделы тоже не остаются не рассмотренными. Во-первых, задачи теории графов имеют много общего. Во-вторых, «калькулятор» может быть использован для проверки домашних и контрольных заданий.

Литература

  1. Печенкин В.В. GRaph INterface (GRIN)

    http://www.ecsocman.edu.ru/db/msg/324869.html

  2. Тычинин С.А., Разработка программы для решения задачи MAX TSP с использованием свободной библиотеки GOBLIN. – Свободное программное обеспечение в образовании: сборник трудов Всероссийской конференции (г. Челябинск, 25–26 марта, 2009 г.) / под ред. А.В. Панюкова. – Челябинск: Изд-во ЮУрГУ, 2009. – с. 49–51.

  3. Панюкова Т.А. Программа GraphCalculator: теория и практика курса «Дискретная математика». – Современные информационные технологии и ИТ-образование. Сб.докл. научно-практической конференции: учебно-методическое пособие. Под ред. проф. В.А. Сухомлина. – М.: ИНТУИТ.РУ, 2009. – С. 346–351.

  4. Panyukova T., Savitskiy E. Optimization of Resources Usage for Technological Support of Cutting Processes. – The International Workshop on Computer Science and Information Technologies’ 2010. Proceedings of Workshop, Russia, Moscow–St.Petersburg, September 13–19, 2010. Vol.1. – Ufa State Technical University, 2010. – P. 66–70.

- -

Похожие:

Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconЛекции по теории графов. М.: Наука, 1990. Берж К. Теория графов и ее применения. М.: Изд иностр лит., 1962
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Наука, 1990
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconПрограмма вступительного экзамена в аспирантуру по специальностям 05. 13. 05 "Элементы и устройства вычислительной техники и систем управления"
Комбинаторика и Комбинаторные объекты. Методы комбинаторного анализа. Теория графов. Основные понятия и определения. Способы задания...
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconПрограмма дисциплины «избранные главы теории графов»
...
Лекции по теории графов читаются либо в виде отдельного курса например, в юургу он читается как «Комбинаторика и теория графов» iconНаучная работа по теме: 1 глава 1 4 теория графов 4 Эйлеровы графы 7 Задача о мостах, Леонард Эйлер и теория графов 8
Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org