Рузаева ISBN 978-5-4263-0001-9 Book 2.indb 2 20.09.2011 10:25:06 Министерство образования и науки Российской Федерации ГОУ ВПО «Московский педагогический государственный университет» В. Л. Матросов ИЗБРАННЫЕ НАУЧНЫЕ ТРУДЫ Москва 2010 Book 2.indb 3 20.09.2011 10:25:06 Book 2.indb 4 20.09.2011 10:25:06 ВИкТоР ЛЕоНИДоВИЧ МАТРосоВ Book 2.indb 5 20.09.2011 10:25:07 Book 2.indb 6 20.09.2011 10:25:07 Профессиональная, научная и общественная деятельность В. Л. Матросова Матросов Виктор Леонидович – ректор Московского педагогического государственного университета, академик РАН, академик РАО, доктор физико-математических наук, профессор, заведующий кафедрой теоретической информатики и дискретной математики МПГУ. <...> Виктор Леонидович Матросов – известный ученый-математик, автор более 350 работ, в том числе 5 монографий, 24 учебников и учебно-методических пособий по высшей математике и информатике. <...> Виктор Леонидович Матросов является руководителем ряда научных программ федерального и отраслевого значения. <...> Виктор Леонидович Матросов входит в состав редколлегий целого ряда ведущих журналов: «Проблемы информатики», «Педагогика», «Наука и школа», «Преподаватель XXI век», «Высшее образование в России», «Магистр», «Интеграция образования», «Высшее образование сегодня» и др. <...> Ларионова (3-я слева), В. Л. Матросов, студенты МПГУ, 2009 г. 19 Book 2.indb 19 20.09.2011 10:25:28 Book 2.indb 20 20.09.2011 10:25:28 РАЗДЕЛ I ТЕоРИЯ сЛоЖНосТИ ВЫЧИсЛЕНИЙ Book 2.indb 21 20.09.2011 10:25:29 ω n( ) Комментарий к работам В. Л. Матросова по теории сложности вычислений А. В. Стеценко, кандидат физико-математических наук В первом разделе книги представлены работы по теории алгоритмов, точнее сказать, той ее части, которую принято называть теорией сложности вычислений. <...> Теория сложности вычислений как раз занимается ответом на этот вопрос. <...> В этих работах были сформулированы аксиомы, перечисляющие свойства, которым должна удовлетворять мера сложности. <...> Поскольку теорема <...>
Избранные_научные_труды._Научное_издание._Твердый_переплет.pdf
УДК 517
ББК 22.16Я43
В. Л. Матросов. Избранные научные труды, М., МПГУ, Издательство «Прометей»,
2010. – 304 с.
Настоящее издание посвящено юбилею выдающегося математика, академика РАН
Виктора Леонидовича Матросова. Составляющие книгу научные работы по теории распознавания
образов и по теории сложности вычислений стали в настоящее время основополагающими
для данных областей математики.
Книга предназначена для специалистов в области дискретной математики, математической
кибернетики, теории распознавания и алгоритмической сложности.
Редакционная группа благодарит за сотрудничество:
Д. А. Мельникова
С. В. Дармодехина
Р. М. Асланова
А. Г. Дьяконова
В. А. Стеценко
А. В. Рузаева
ISBN 978-5-4263-0001-9
Book 2.indb 2
20.09.2011 10:25:06
Стр.2
Содержание
Профессиональная, научная и общественная деятельность
В. Л. Матросова ..........................................................................................................7
РАЗДЕЛ I. Теория сложности вычислений ...........................................................21
Стеценко В. А. Комментарий к работам В. Л. Матросова по теории
сложности вычислений ..............................................................................................22
Аналитическое описание классов сложности вычислимых функций ..........................26
Классы сложности вычислимых функций для сигнализирующей колебания ..............34
О сигнализирующих вычислимых функций для некоторых
уточнений меры сложности .......................................................................................40
Классы сложности и классы сигнализирующих вычислимых функций .......................50
Сложность вычислимых функций для обобщенной меры памяти ...............................56
РАЗДЕЛ II. Теория распознавания .........................................................................67
Дьяконов А. Г. Комментарий к работам В. Л. Матросова
по теории распознавания ..........................................................................................68
Корректные алгебры ограниченной емкости над множествами
некорректных алгоритмов .........................................................................................74
Корректные алгебры ограниченной емкости над множеством
алгоритмов вычисления оценок ................................................................................82
О критериях полноты модели алгоритмов вычисления оценок
и ее алгебраических замыканий .............................................................................. 100
Оптимальные алгоритмы в алгебраических замыканиях операторов
вычисления оценок ................................................................................................. 106
Изоморфизм пар допустимых объектов в задачах распознавания ........................... 112
О неполноте модели алгоритмов вычисления оценок .............................................. 120
Емкость алгебраических расширений модели алгоритмов
вычисления оценок ................................................................................................. 136
Нижние границы емкости L-мерных алгебр алгоритмов
вычисления оценок ................................................................................................. 152
Емкость полиномиальных расширений множества алгоритмов
вычисления оценок ................................................................................................. 166
Синтез оптимальных алгоритмов в алгебраических замыканиях моделей
алгоритмов распознавания ..................................................................................... 180
Synthesis of a Correct Algorithm with a Minimum Complexity ........................................ 208
Classes of Correct Algorithms with Limited Capacity .................................................... 220
Список научных трудов В. Л. Матросова ................................................................. 244
303
Book 2.indb 303
20.09.2011 10:48:11
Стр.303