Программа Graph Calculator: теория и практика курса \"Дискретная математика\" icon

Программа Graph Calculator: теория и практика курса "Дискретная математика"



НазваниеПрограмма Graph Calculator: теория и практика курса "Дискретная математика"
Дата17.10.2016
Размер
ТипПрограмма

Программа Graph Calculator: теория
и практика курса "Дискретная математика"

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


Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

^ Основные задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Закрепление материала курса «Дискретная математика». Решение прикладных задач.

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

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

^ Описание программы

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




^ Рис1. Окно для создания и редактирования графа.


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

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

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

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

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

^ Подсчет числа компонент связности и сохранение матрицы инцидентности в блочном виде.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

Таким образом, создаваемый проект 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. Панюкова Т.А., Савицкий Е.А. Композиция интерфейсов при технологической подготовке процессов раскроя. – Труды 40-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики». Екатеринбург: УрО РАН, 2009. – С. 367-372.

  4. Panyukova T. Routing problems for cutting processes. – The International Workshop on Computer Science and Information Technologies’ 2008. Proceedings of Workshop, Turkey, Antalya, September 15–17, 2008. Volume 2, Ufa State Technical University, 2008. – P. 100–106.




Похожие:

Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconПрограмма курса «История английской литературы конца ХIХ начала ХХ века» для студентов романо-германского отделения (английская филология)
Теория и практика реалистического романа в конце XIX – начале ХХ века. Критика «классического реализма» Диккенса и Теккерея
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconДискретная математика
Аналогично, здесь мы будем изучать основы дискретной математики, с тем, чтобы вы могли ими пользоваться при изучении других специальных...
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconПояснительная записка Программа основного курса по математике 6 класса составлена в соответствии с федеральным компонентом государственного стандарта основного общего образования, на основе примерной программы по предмету «Математика»
«Математика», утвержденной Министерством образования рф, программы Н. Я. Виленкина и рассчитана на 170 часов(5 часов в неделю)
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconЦель и задачи практики летняя практика по зоологии для студентов 1-го курса по специальности «Зоотехния»
Летняя практика по зоологии для студентов 1-го курса по специальности «Зоотехния» является составной частью предмета, читаемого в...
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconПрограмма курса «Дифференциальные уравнения» для специальности «Прикладная математика»
Искать черную кошку в темной комнате – не особо приятное дело, но уж как карты легли
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconДискретная математика
Само название «граф» подразумевает наличие графической ин­терпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном...
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconПрограмма курса «Дифференциальные уравнения» для специальности «Прикладная математика»
Что такое: дифур? решение? задача Коши? симметричная форма дифура? Разве можно константу превратить в переменную?
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconПрограмма элективного курса, 68 часов в год (2 ч/нед.). 10-й класс
Основная функция данного элективного курса – это поддержка профиля обучения. В данном курсе углублённо изучаются отдельные разделы...
Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconТематическое планирование 1 год обучения № Название темы Всего: Практика Теория 1

Программа Graph Calculator: теория и практика курса \"Дискретная математика\" iconПрограмма учебного курса "Сравнительный анализ постсоветских трансформационных процессов"
Программа учебного курса "Сравнительный анализ постсоветских трансформационных процессов" для магистров и студентов 4-5 курса социологического...
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами