МНОГОУРОВНЕВЫЕ ОПИСАНИЯ КЛАССОВДЛЯ УМЕНЬШЕНИЯ ЧИСЛА ШАГОВ РЕШЕНИЯ ЗАДАЧ РАСПОЗНАВАНИЯ ОБРАЗОВ,ОПИСЫВАЕМЫХ ПРОПОЗИЦИОНАЛЬНЫМИ ФОРМУЛ

摘要

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