Основные научные результаты Матросова В.Л.:
• установлена функциональная связь между емкостью модели алгоритмов распознавания и сложностью ее задания
• установлена конкретная функциональная зависимость емкости модели алгоритмов от размерности и степени алгоритмических полиномов
• разработан спектральный метод, позволяющий конструктивно находить корректный для регулярной задачи алгоритм из данной модели алгоритмов, имеющий ограниченную емкость
• установлены экстраполяционные возможности моделей алгоритмических полиномов ограниченной емкости. При этом доказано, что при любом ограничении на показатель степени полиномиального расширения модели алгоритмов распознавания, существуют регулярные задачи, не имеющие в данном расширении корректного алгоритма
• разработан новый метод операторных покрытий, с помощью которого получены асимптотически совпадающие верхние и нижние оценки емкости данной модели алгоритмов
• доказана инвариантность оценок емкости относительно выбора главных операций алгебраических расширений модели алгоритмов распознавания
• создан аппарат исследования, позволяющий строить подмодели алгоритмов ограниченной емкости, наследующие свойства корректности, что дало возможность создать цельную методику теоретического изучения задач синтеза решающих алгоритмов с заданным качеством.
Ключевые слова
информатика, теория алгоритмов, математическая логика