Программные продукты и системы

Оценка вычислительной сложности алгоритма может быть получена теоретически либо путем вычислительных экспериментов на различных по сложности входных данных.

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

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

Для проведения исследований разработана программная система «Полигон для исследования алгоритмов структурной информатики» (Полигон), входящая в состав АСНИ «Мастерская граф-моделей». Цель ее разработки – создание среды, в которой решатели задач могли бы использоваться как для решения практических и теоретических задач, так и для анализа их вычислительной эффективности.

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