Применение инструментальных программных средств при изучении алгоритма Форда-Фалкерсона

Размещено на http://www.allbest.ru/

ФГБОУ ВО «Орловский государственный университет имени И.С. Тургенева»

Применение инструментальных программных средств при изучении алгоритма Форда-Фалкерсона

Донцова Юлия Андреевна

магистрант, физико-математический факультет

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

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

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

Дискретная математика занимается изучением дискретных структур. Одним из основных предметов ее изучения являются графы - абстрактные математические модели, представляющие собой совокупность связанных объектов [1, с. 267].

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

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

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

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

Наиболее эффективным алгоритмом для решения данной задачи является алгоритм Форда-Фалкерсона. Основная его идея заключается в итерационном построении максимального потока путем поиска на каждом шаге увеличивающей цепи, то есть последовательности дуг, поток по которым можно увеличить. Данный алгоритм применим к любой транспортной сети [3, с.346].

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

На рисунке 1 представлен вид стартового окна приложения.

Рисунок 1. Стартовое окно приложения

Здесь пользователю предлагается ввести количество вершин исходного графа. После нажатия кнопки «ОК», приложение построит матрицу nЧn, где n - значение введенное пользователем (Рисунок 2).

Рисунок 2. Пустая матрица исходных данных

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

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

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

Рисунок 3. Кнопка «Open»

Для того чтобы ввод данных происходил корректно, необходимо чтобы файл имел определенную структуру. Она достаточно проста - необходимо, чтобы элементы столбцов были разделены пробелами, а строки кодом переводы строки (однократным enter) и файл имел расширение *.txt* (Рис. 4).

Рисунок 4. Вид файла исходных данных

После выбора файла и нажатия кнопки «Открыть», матрица интегрируется в приложение (Рис. 5).

Рисунок 5. Загруженная матрица исходных данных

Для того чтобы запустить процесс решения задачи, пользователю необходимо нажать кнопку «Count up». Сначала приложение осуществляет обрисовку исходного графа. Исходный граф сохраняется в файл «digraph.png» (Рис. 6).

Рисунок 6. Исходный граф (“digraph.png”)

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

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

Рисунок 7. Пошаговое решение задачи

Конечный граф, с найденным максимальным потоком сохраняется в файл «maxdigraph.png». Помимо визуализации решения пользователю так же выводится значение найденного максимального потока (Рисунок 8).

Рисунок 8. Вывод результатов для пользователя

Как можно заметить из рисунка 8, значения в таблице изменились - теперь это матрица распределения максимального потока в сети. Внизу так же указывается значение найденного максимального потока.

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

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

Библиографический список

инструментальный программный дискретный пользователь

1. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Расширенный курс. - М: Известия, 2011. - 512 с.

2. Окулов С.М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие / С.М. Окулов. - 2 - е изд. - М.: БИНОМ. Лаборатория знаний, 2012. - 422 с.

3. Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. 2-е изд. - СПб.: Питер, 2007. - 364 с.

Размещено на Allbest.ru