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