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

Содержание

• Введение
• Описание алгоритмов
• Алгоритм Дейкстры поиска кратчайшего пути между вершинами графа
• Алгоритм Прима поиска минимального остовного дерева в графе
• Реализация алгоритмов
• Тестирование алгоритмов
• Отчет 18 с., 6 рис., 3 табл., 7 источников, 1 прил
• ГРАФ, ВЕРШИНА, РЕБРО, КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ, МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО Объектом исследования являются алгоритмы решения графовых задач
• Цель работы — разработка алгоритмического и программного обеспечения для решения задач поиска кратчайшего пути между вершинами графа и минимального остовного дерева графа
• В результате исследований были рассмотрены алгоритмы решения графовых задач
• Разработан программный продукт на языке программирования высокого уровня Delphi, реализующий алгоритм Дейкстры поиска кратчайшего пути между вершинами графа
• Список использованных источников

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

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

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

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

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

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

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

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

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

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

В начале курсового проектирования требуется ознакомиться с основными определе-ниями по теме «Графы». Особое внимание следует уделить алгоритму нахождения кратчай-шего пути между 2-мя заданными вершинами гафа и алгоритму нахождения минимального остовного дерева графа. Затем, используя приведенный

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

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

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

Полный листинг реализованного ПП приводится в

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