Введение 12
1 Обзор литературы 14
2 Literature review 15
3 Объект и методы исследования 16
3.1 Обзор методов представления графов 18
4 Реализация информационной системы 22
4.1 Выбор инструментария 22
4.2 Интерфейс пользователя 22
4.3 Описание программной реализации 28
5 Финансовый менеджмент, ресурсоэффективность и ресурсосбережение 40
5.1 Организация и планирование работ 40
5.2 Расчет сметы затрат на выполнение проекта 44
5.3 Оценка экономической эффективности проекта 49
6 Социальная ответственность 52
6.1 Анализ возможных сбоев и их последствий 52
6.2 Методы и технологии встроенной защиты от ошибок 55
6.3 Мероприятия по защите здоровья и безопасности пользователя 56
6.4 Мероприятия по защите оборудования 59
Заключение 62
Conclusion 63
Список использованных источников 64
Приложение А 66
Приложение Б 68
Целью данной работы является разработка программы, позволяющей задавать неориентированные графы визуальным способом и выполнять следующие алгоритмические задачи над графами:
1. Поиск кратчайшего пути между двумя выбранными вершинами;
2. Решение задачи коммивояжёра любым алгоритмом.
Основные задачи:
- Спроектировать систему программных классов;
- Реализовать алгоритм Ли;
- Реализовать решение задачи коммивояжёра методом ветвей и границ;
- Спроектировать систему программных классов.
В настоящее время методы визуализации графов имеют множество применений. Графы и графовые модели используются для задач, оперирующих информацией, представленной в виде объектов и связей между ними. Например, синтаксические деревья в трансляторах, раскраска графов при конструировании электрических схем, поиск кратчайшего пути в компьютерных играх или в геоинформационных системах, так же визуализацию графов можно применять в учебных целях для наглядного изучения теории графов. Системы, где используют графическое представление, редко бывают статичными. Другими словами, в таких системах протекают некоторые процессы, которые могут изменить связи или иным способом перестраивать структуру модели. К статичным системам можно отнести большинство диаграмм, например, диаграммы, используемые в рамках визуального моделирования, и блок схемы. Для представления графа в динамической форме необходима генерация изображений для представления промежуточных состояний графовых моделей.
Несомненно, главным применением является применение в области улучшения качества преподавания обучающихся в старших классах, а также студентов.
В настоящее время преподавание осуществляется, в основном, без возможности визуализации преподаваемых прикладных механизмов, что затрудняет и замедляет обучение учащихся. Необходимость во внедрении соответствующих программных систем очевидна.
На данном этапе разработки система содержит лишь визуализацию некоторых алгоритмов, применяемых к графам. Такие функциональные рамки связаны с временными ресурсами, имеющимися в распоряжении разработчика. В дальнейшем предполагается значительно увеличить число поддержимаемых программным обеспечением функций, разрабатовав алгоритмы визуализации других часто встречающихся задач, необязательно относящихся только к дисциплине «Теории графов», но и относящихся к таким дисциплинам как «Дискретная математика», «Структура и алгоритмы обработки данных», и других, что существенно повысит успеваемость студентов и сделает процесс обучения более комфортным.
Некоторые другие возможные прикладные применения разработанной программной системы кратко перечислены ниже:
1. Возможность мгновенного воспроизведения ранее забытых алгоритмов в памяти пользователя посредством просмотра визуализальной трансляции решения типовых задач;
2. Закрепление полученных знаний;
3. Непосредственно решение типовых задач с наглядным воспроизведением результата;
4. Прокладывание маршрута от пункта отправления до пункта назначения по кратчайшему пути (алгоритм Ли);
5. Поиск наиболее выгодного маршрута для посредника, развозящего товары конечным потребителям (задача коммивояжёра).
Перечисленные выше преимущества делают данную разработку важным и полезным инструментом.
В ходе проделанной работы была спроектирована система программных классов, был выполнен ввод графа визуальным способом, реализован алгоритм Ли и решена задача коммивояжёра методом ветвей и границ, в результате чего был разработан программный продукт «Студграф».
