Курсовой проект, Дискретная математика, Канева, ОмГТУ.

	4

Описание алгоритмов	6

Алгоритм Дейкстры поиска кратчайшего пути между вершинами графа	6

Алгоритм Прима поиска минимального остовного дерева в графе	8

Реализация алгоритмов	9

Тестирование алгоритмов	12



Отчет 18 с., 6 рис., 3 табл., 7 источников, 1 прил.

ГРАФ, ВЕРШИНА, РЕБРО, КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ, МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО

Объектом исследования являются алгоритмы решения графовых задач.

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

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

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

Список использованных источников

ОмГТУ, Канева, 1-ый курс, актуально для Заочного отделения, возможно и для Очного подойдет.



Тема курсового проекта (КП) по дисциплине 'Дискретная математика: "Разработка алгоритмического и программного обеспечения для решения графовых задач"



Курсовой проект основывается на разработанной программе на языке программирования - Delphi и включает готовую, рабочую программу в архиве, запускать нужно Project1.exe





******************************************************

Само задание собственно:



Методические указания к выполнению курсового проекта по дисципли-не "Дискретная математика"

Тема курсового проекта (КП) по дисциплине "Дискретная математика: «Разработка алгоритмического и программного обеспечения для решения графовых задач».



Задача курсового проекта разработка и реализация на языке программирования вы-сокого уровня собственного или уже существующего алгоритма для решения следующих задач: 

1) нахождения кратчайшего пути между 2-мя заданными вершинами графа;

2) нахождения минимального остовного дерева графа. 

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

При изучении или разработке собственного алгоритма рекомендуется решить практи-ческие задачи своего варианта по теме "Графы" ( папка Практикум), а так же придумывать другие тестовые задачи, которые потом будут Вами использованы при тестировании разра-ботанного программного продукта (ПП). В разделе "Описание алгоритма" приводите вы-бранные Вами или разработанные алгоритмы в форме "по шагам" с пояснениями всех обо-значений, которые используете в описаниях алгоритмов. В этом же разделе приводите схемы алгоритмов ("блок-схема"). 

По разработанным схемам реализуете алгоритмы на любом языке программирования высокого уровня (Pascal, Delphi, C++, C# и др.). Для задания графа рекомендуется использо-вать матрицу смежности или инцидентности графа. Для тестирования правильности работы алгоритма используйте примеры, которые были прорешаны на этапе разработки алгоритма. Полученный программный продукт обязательно требуется протестировать на случаях выро-жденного графа. Так же требуется провести тестирование вашего ПП на графах большой размерности (50 и более вершин). По результатам проведенной работы оформляются разде-лы "Реализация алгоритмов" и "Тестирование алгоритмов".

Полный листинг реализованного ПП приводится в приложении, а в разделе "Реализа-ция алгоритмов" требуется указать и пояснить наиболее интересные и важные моменты кода программ. Раздел "Тестирование алгоритмов" должен содержать тестовую выборку, по кото-рой можно сделать вывод о правильности работы разработанных вами и реализованных ал-горитмов