deniskabanov / discrete_models_and_algorithms_complexity

Лабораторная работа по предмету "Дискретные модели и сложность алгоритмов" (магистратура ИАД, 1 курс).

Дискретные модели и сложность алгоритмов

Лабораторная работа по предмету "Дискретные модели и сложность алгоритмов" (магистратура ИАД, 1 курс).

Используемые языки: Python

Задание:

Написать алгоритмы для решения задачи о минимальном остовном дереве и сравнить их работу:

1. Алгоритм Прима на метках
2. Алгоритм Прима на фибоначчиевой куче

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

P.S. рёбра в создаваемых графах имеют вес типа uint8, то есть возможных диапазон их значений — [0, ..., 255], однако алгоритмы поддерживают работу и с другими типами, такими как - np.float64 ...