Детальная информация

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

This work describes methods for the experimental determination of average-case time complexity, the development of a computational framework for its evaluation based on minimum spanning tree (MST) and graph coloring problems. The tasks addressed in this work include: problem formulation, development of a program for conducting experiments, analysis of obtained data to address the defined tasks. During the study, a framework was implemented to evaluate the average-case complexity of Prim’s and Kruskal’s algorithms, as well as exact, approximate, and heuristic-based approximate graph coloring algorithms.

• Экспериментальное определение трудоёмкости в среднем целочисленных алгоритмов
  • Введение
  • 1. Постановка задачи
  • 2. Описание методов и алгоритмов
  • 3. Разработка стенда для проведения эксперимента
  • 4. Результаты вычислительного эксперимента
  • Заключение
  • Список использованных источников