Лабораторна робота №1

Дана лабораторна робота присвячена реалізації та аналізу алгоритмів для роботи з графами, а також дослідженню моделі дерева рішень. У рамках роботи було реалізовано та досліджено ефективність наступних алгоритмів:

• Алгоритм Прима
• Алгоритм Крускала
• Алгоритм Беллмана-Форда
• Алгоритм Флойда-Воршелла

Реалізовані алгоритми були порівняні з вбудованими імплементаціями бібліотеки networkx. Проведено експерименти на графах різних розмірів та щільності для оцінки часу виконання алгоритмів та їхньої ефективності.

Крім того, у межах роботи було розглянуто застосування дерев у машинному навчанні шляхом реалізації класифікатора на основі Decision Tree.

Порівняння алгоритмів

Тестування продилося на графах з 5, 10, 20, 50, 100, 200 вершинах та ймовірністю зв'язку між двома вершинами - 0.4. Кількість ітерацій для кожної кількості вершин - 1000

Алгоритм Прима

reality - наша реалізація etalon - реалізація з бібліотеки networkx

Алгоритм Крускала

reality - наша реалізація etalon - реалізація з бібліотеки networkx

Алгоритм Беллмана-Форда

reality - наша реалізація standard - реалізація з бібліотеки networkx

Алгоритм Флойда-Воршелла

reality - наша реалізація standard - реалізація з бібліотеки networkx