На правах рукописи

Романов Михаил Юрьевич

Построение обобщённых полиномов

минимальной степени

над алгоритмами вычисления оценок

Специальность 05.13.17 теоретические основы информатики

Автореферат

диссертации на соискание учёной степени

кандидата физико-математических наук

Москва

2008

Работа выполнена в Вычислительном центре им. А. А. Дородницына Российской Академии наук.

Научный руководитель: доктор физико-математических наук, профессор, академик РАН Журавлёв Юрий Иванович.

Официальные оппоненты: доктор физико-математических наук, профессор, чл.-корр. РАН Рудаков Константин Владимирович, кандидат физико-математических наук Кольцов Пётр Петрович.

Ведущая организация: Московский государственный университет им. М. В. Ломоносова.

Защита диссертации состоится 2008 г. в часов на заседании диссертационного совета Д002.017.02 в Вычислительном центре им. А. А. Дородницына Российской Академии Наук по адресу: 119333, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан 2008 г.

Учёный секретарь диссертационного совета Д002.017.02 при Вычислительном центре им. А. А. Дородницына РАН доктор физико-математических наук, профессор Рязанов В.В.

Общая характеристика работы

Актуальность темы. Теория распознавания является одной из очень важных и динамично развивающихся областей прикладной математики.

Её методы позволяют формулировать и успешно решать задачи из таких прикладных областей, как экономика, социология, геология, химия, биология и медицина.

К концу 50-х годов прошлого века были сформулированы многие параметрические семейства алгоритмов распознавания. Ю. И. Журавлёвым разработан класс алгоритмов вычисления оценок (АВО), который также можно использовать в качестве языка описания методов распознавания. Следующим важным этапом развития теории распознавания стало создание Ю. И. Журавлёвым алгебраического подхода, который является эффективным способом описания алгоритмических композиций. В рамках этого подхода наибольший интерес представляют полиномиальные композиции. В частности, было показано, что для любой регулярной задачи существует корректный алгоритм среди полиномов над АВО. Это привело к широкому применению полиномиальных алгоритмических структур при исследовании и решении прикладных проблем. Поэтому одной из ключевых задач стало уменьшение сложности алгебраических композиций. Значительное количество работ посвящено оценке степени и числа слагаемых корректного полинома над алгоритмами распознавания. Этой задачей занимались Ю. И. Журавлёв, И. В. Исаев, В. Л. Матросов, Т. В. Плохонина, К. В. Рудаков, А. С. Дьяконов. В настоящей диссертации продолжены эти исследования и приведён метод построения полинома минимальной степени над заданным набором алгоритмов.

Цель работы состоит в разработке метода построения обобщённого полиномиального алгоритма наименьшей степени в алгебре над множеством алгоритмов вычисления оценок.

Методика исследований. В диссертации использован аппарат алгебраического подхода к теории распознавания. Также использованы методы теории оптимизации.

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

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

Апробация работы. Результаты, изложенные в диссертации, докладывались на Всероссийской конференции Математические методы распознавания образов XIII (Москва, 2007 г.); Интеллектуализация обработки информации –2008 (Алушта, Украина, 2008 г.); а также на научных семинарах МФТИ.

Основные результаты диссертации.

1) Введено понятие обобщённого полиномиального алгоритма в алгебре над множеством алгоритмов вычисления оценок.

2) Для нахождения обобщённого полиномиального алгоритма минимальной степени сформулирована оптимизационная задача.

3) Предложен метод декомпозиции рассмотренной оптимизационная задачи на множество вспомогательных задач.

4) Построен алгоритм решения вспомогательных задач.

5) Рассмотрены два подхода повышения эффективности предложенного метода. Первый подход позволяет сократить число решаемых вспомогательных задач, второй снизить их сложность.

6) Приведено развитие этого подхода, позволяющее понизить степень обобщённого полинома за счёт уменьшения числа слагаемых (распознающих операторов).

7) Рассмотрен вопрос многопроцессорной реализации приведённых методов.

8) Проведена серия экспериментов по практической реализации предложенного метода. На рассмотренных примерах показана высокая эффективность метода.

9) Проведены практические эксперименты для сравнения эффективности со стандартными методами решения рассмотренной оптимизационной задачи. Показано существенное превосходство предложенного метода.

Практическая и теоретическая ценность. Работа носит в основном теоретический характер. Введённое понятие обобщённого полиномиального алгоритма может использоваться, как естественное расширение классических алгебраических полиномиальных алгоритмов.

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

Публикации. По теме диссертации автором опубликованы 4 работы.

Структура и объём работы. Работа состоит из введения, четырёх глав и списка литературы из 33 наименований. Общий объём работы 80 страниц, включая 4 рисунка и 27 таблиц.

Содержание диссертационной работы Во введении даётся краткий обзор полученных ранее результатов.

Приводится общая структура диссертации и краткое изложение содержания работы.

В первой главе вводятся основные понятия и определения используемые в работах Ю. И. Журавлёва, посвященных алгебраическому подходу к решению задач распознавания и классификации. Рассматриваются алгоритмы вычисления оценок (АВО). Описывается формальная постановка задачи построения распознающего алгоритма следующим образом.

Множество из M объектов разделяется на обучающую выборку Sm и контрольную выборку S.

Задача распознавания Z = (I0, S q ) определяется начальной информацией I0 о принадлежности объектов классам и контрольной выборкой S q.

Для каждого контрольного вектора необходимо найти информационный вектор Рассматривается множество алгоритмов {A} решения задачи Z = I0, S q, представленных в виде произведения операторов A = B · C.

Здесь оператор B определяет матрицу оценок B (Z) = ij ql, где ij действительные числа; а оператор C матрицу ответов Возможность представления произвольного алгоритма распознавания в таком виде показана Ю. И. Журавлёвым.

Определение 1.1. Алгоритм A называется корректным для задачи Z, если выполнено равенство A I0, S q = ij ql. Алгоритм A, не являющийся корректным для Z, называется некорректным.

Определение 1.2. Решающее правило C называется корректным на M, если для всякого конечного набора Sm M существует хотя бы одна числовая матрица aij ql такая, что C aij ql = ij ql.

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

Определение 1.3. Множества L {A}, U {A} алгоритмов A = B · · C соответственно таких, что B L {B}, B U {B}, называется соответственно линейным и алгебраическим замыканиями {A}.

Множество алгоритмов, построенное на алгебраическом замыкании k-й степени над некоторым набором РО, будем называть алгебраическим расширением k-й степени.

Для краткости степенью алгоритма A будем называть степень алгебраического расширения, в котором построен этот алгоритм. Иначе говоря, это можно понимать, как степень полинома над операторами {Bk }, который является распознающим оператором алгоритма A.

В работах Ю. И. Журавлёва получены следующие результаты.

Теорема 1.1. Пусть {A} совокупность некорректных алгоритмов, {B} соответствующее множество операторов, C фиксированное корректное решающее правило. Тогда L {A} = {L {B} · C} является корректным относительно {Z}, если {Z} состоит из задач, полных относительно {B}.

Теорема 1.2. Пусть выполнены все условия предыдущей теоремы и, кроме того, [{B}] есть замыкание {B} относительно операций умножения на константу и операторного умножения. Тогда U {A} = {U {B} · C} является корректным относительно {Z}, если {Z} состоит из задач, полных относительно [{B}].

Для алгоритмов вычисления оценок (АВО) предполагается, что элемент матрицы распознающего оператора B равен ij = j (S i ) и является оценкой объекта S i по классу Kj.

В качестве решающего правила используется стандартное корректное пороговое решающее правило: C ij ql = C (ij ) ql, Элементы матрицы ответов можно разбить на два множества ij ql = M0 M1, где Mi = (u, v) : uv = i, q число объектов, l число классов.

Оператор B с матрицей оценок B (Z) = ij ql называется допустимым для задачи Z, если существует хотя бы одна пара (u, v) M такая, что для всех (i, j) M0 выполняется uv (B) > |ij (B) |.

Такая пара (u, v) называется отмеченной в B, и множество отмеченных в B пар обозначим через M (B). Фактически, это означает, что отмеченные пары отделены от всех пар (i, j) таких, что объект S i не принадлежит классу Kj. Поэтому, при некоторых порогах c1, c2 алгоритм B · C будет давать правильные ответы для всех пар, отмеченных Допускается альтернативный способ определения отмеченных точек.

Пара (u, v) называется отмеченной в B при некоторой фиксированной величине, если для всех (i, j) M0 имеет место неравенство При таком определении все дальнейшие рассуждения остаются справедливыми.

Для оператора B можно ввести оператор B = B · B. Определив в задаче Z = I0, S q элементы матрицы оценок, как B (Z) = ij ql, получим ij B = B · ij B.

Ю. И. Журавлёвым показано следующее утверждение.

Лемма 1.3. Если (u, v) отмечена в B, то ij B 1; если (u, v) не отмечена в B, то ij B Q B < 1.

Тогда, учитывая, что матрица оценок B (Z) получается из B (Z) поэлементным умножением, получим, что пара (u, v) является отмеченной в B тогда и только тогда, когда она отмечена в B.

Пусть {Bk } произвольная конечная система распознающих операторов.

Определение 1.4. Система {Bk } является базисной для Z, если В работе Ю. И. Журавлёва приводится теорема о том, что полиномиальный алгоритм со степенями, определяемые некоторой формулой, является корректным для Z. При этом, указанные в теореме степени распознающих операторов оказываются заведомо большими, чем необходимо для выполнения условий корректности.

В работах К. В. Рудакова и А. Г. Дьяконова получена точная верхняя грань степени полинома, необходимой для корректности алгоритма.

Для любого набора операторов, если существует корректный полиномиальный алгоритм, мы можем полагать, что степень этого алгоритма не превосходит величину [log2 ql].

В главе 2 формулируется основная оптимизационная задача и описывается метод её решения.

В параграфе 2.1 рассматривается обобщение введённых полиномиальных алгоритмов. В отличие от предыдущего, степень распознающего оператора предполагается действительным числом, а не только целым.

Определение 2.1. Обобщённым алгебраическим замыканием множества распознающих операторов B = {B1, B2,..., Bn } будем называть множество Элементы этого множества назовём обобщёнными полиномами над B, а слагаемые этого полинома обобщёнными мономами.

Аналогично, множество U A алгоритмов A = B · C таких, что B U B, назовём обобщённым алгебраическим замыканием A.

Определение 2.2. Пусть задано множество РО Степенью обобщённого монома B1 1 ·B2 2 ·...·Bs s будем называть величину x1 + x2 +... + xs.

Степенью обобщённого полинома B U B будем называть максимальную из степеней входящих в него обобщённых мономов.

Степенью алгоритма A = B · C из обобщённого алгебраического замыкания будем называть степень обобщённого полинома B.

Всякий полином над распознающими операторами является также и обобщённым полиномом. При этом степень полинома совпадает со степенью, полученной при рассмотрении этого полинома, как обобщённого.

Для введённых понятий сохраняются результаты главы 1. В частности, приведённая в параграфе 1.3 точная верхняя грань степени полинома означает, что существует обобщённый полином указанной степени.

В параграфе 2.2 рассматривается построение распознающего алгоритма в обобщённом алгебраическом замыкании над множеством алгоритмов вычисления оценок. Для нахождения искомого набора степеней сформулируем некоторую оптимизационной задаче.

Пусть задан набор РО Bk, строящих матрицы оценок Bk (Z) = = uv ql, и оператор C задан стандартным пороговым решающим которое определяется параметрами c1, c2.

Замечание 2.1. Без ограничения общности будем считать, что для параметров c1, c2 выполнено условие c1 + c2 = 1. В противном случае, эти параметры следует разделить на сумму c1 + c2.

Определение 2.3. Набор распознающих операторов {Bk } будем называть правильным, если для него выполняются следующие условия.

1) Каждый оператор является допустимым, т. е. существует хотя бы одна пара (u, v) M1 отмеченная в B.

2) Каждый оператор является нормированным, т. е. по лемме 1.3 если (u, v) отмечена в B, то uv 1, иначе uv < 1.

3) Система {Bk } является базисной для Z, т. е. M1 = M (Bk ).

В противном случае набор операторов будет называть неправильным.

В дальнейшем описывается алгоритм, корректный для задачи Z, в следующем виде: A = k=1 Bk C (c1, c2 ). Сформулируем теорему, которая накладывает условия на степени обобщённых полиномов, при которых рассматриваемый алгоритм является корректным.

Теорема 2.1. Пусть задан набор операторов {Bk }, k = 1, n, дающих матрицы оценок Bk (Z) = uv ql на обучающей выборке задачи Z.

Пусть для набора степеней {xk } имеют место следующие условия:

Тогда алгоритм является корректным для Z.

Пусть также набор операторов {Bk } является правильным по определению 2.3, т. е. операторы являются допустимыми, нормированными и образуют базисную систему для Z. Тогда существует набор степеней {xk } определяющий алгоритм A, корректный для задачи Z.

Теперь сформулируем оптимизационную задачу для определения набора степеней {xk } удовлетворяющих условиям теоремы 2.1 и дающих обобщённый полином минимальной степени:

В полученной оптимизационной задаче (2) область ограничений состоит из q l неравенств, и целевая функция зависит от n переменных.

Введём замену переменных: yk = exk, k = ln uv, uv () = = k=1 yk. Тогда, учитывая результаты параграфа 1.3, оптимизационная задача (2) принимает вид В параграфе 2.3 описывается метод декомпозиции рассматриваемой оптимизационной задачи. Для каждого непустого множества индексов I = {i1,..., im } {1,..., n} рассматривается задача с множеством ограничений Таким образом, исходной задаче R ставится в соответствие 2n вспомогательных задач RI. В последующих параграфах будет показано, что задачу R с нелинейным функционалом можно решить, найдя решение более простых задач RI с линейным функционалом. В следующей главе будут приведены методы, позволяющие существенно сократить количество решаемых задач.

В параграфе 2.4 рассматривается геометрическая интерпретация предложенного метода декомпозиции.

В параграфе 2.5 приводится теорема о существовании решения оптимизационной задачи.

Теорема 2.2. Существует непустое множество индексов такое, что решение задачи RI является решением задачи R.

В параграфе 2.6 рассмотрены алгоритмы решения вспомогательных задач RI. Описан метод линеаризации, позволяющий свести задачу к последовательности задач квадратичного программирования. Так как все ограничения множества UI являются полиномиальными, то такое сведение удаётся сделать аналитически.

Далее описаны алгоритмы решения задачи квадратичного программирования методом линеаризации и обобщённым методом Ньютона.

В настоящий момент наиболее эффективным методом решения задачи нелинейной оптимизации (задача RI ) считается метод последовательного квадратичного программирования (Sequential Quadratic Programming, или SQP). Он позволяет сводить исходную нелинейную задачу к последовательности задач квадратичного программирования, на каждом шаге осуществляя аппроксимацию Гессиана функции Лагранжа с помощью обобщённого метода Ньютона.

В предложенном подходе также используется сведение нелинейной задачи RI к последовательности задач квадратичного программирования. В отличие от метода SQP для сведения применяется не квадратичная аппроксимация функции Лагранжа, а метод линеаризации.

Несмотря на высокую эффективность метода SQP на многих задачах, для рассматриваемой задачи метод линеаризации оказывается существенно эффективнее.

Подробнее вопрос сравнения эффективности на прикладных задачах рассматривается в параграфе 4.4.

В главе 3 рассматриваются способы, позволяющие существенно повысить эффективность метода, описанного в главе 2. Приводится развитие этого подхода, позволяющее понизить степень обобщённого полинома, уменьшая число слагаемых.

Для описания свойств вспомогательных оптимизационных задач вводятся некоторые специальные операторы. Пусть для некоторой оптимизационной задачи RI при наборе I = {i1,..., im } {1,..., n}, решением является вектор y (RI ) размерности n. Тогда для задачи RI введём следующие обозначения:

Для задачи R с решением y введём F (R) = F = max yk. При этом для любого набора I выполняется GI FI. Сформулируем несколько свойств для введённых операторов.

Теорема 3.1. Пусть заданы два набора индексов I 1 I 2, где Теорема 3.2. Пусть для набора I = i, i,..., i 1 {1, 2,..., n}, решение задачи RI совпадает с решением задачи R. Тогда для любого набора I = {i1, i2,..., im1 } {1, 2,..., n}, выполняется FI FI.

Замечание 3.1. В теореме 2.2 решение задачи R сводится к выбору среди решений задач RI. Таким образом, необходимо найти набор I, определяющий вспомогательную задачу, решение которой является решением задачи R. Тогда, по теореме 3.2 достаточно искать минимум величины max yk не на всём множестве U, а лишь среди всех решений задач RI. Для них эта величина равна FI, и в новых обозначениях задачу минимизации можно сформулировать следующим образом:

Лемма 3.3. Пусть для некоторых I 1 и I 2 выполняется следующее свойство: GI решение задачи RI является решением задачи R только тогда, когда задача RI 2 даёт решение задачи R.

Замечание 3.2. Из доказанной леммы 3.3 следует, что если найдены наборы I 1 и I 2, удовлетворяющие условию леммы, то все I, содержащие поднабор I 1, следует исключить из рассмотрения. Это утверждение лежит в основе рассматриваемого далее алгоритма эффективного перебора вспомогательных задач.

Описывается эффективный алгоритм поиска вспомогательной задачи RI, дающей решение задачи R.

Алгоритм.

1) Рассматриваем упорядоченное множество наборов которое упорядочено таким образом, что наборы с меньшей мощностью предшествуют наборам с большей. Присваиваем начальное значение Fmin = +.

2) Выбираем первый нерассмотренный набор I из H и решаем задачу RI.

3) Вычисляем значения GI и FI. Если FI < Fmin, то присваиваем 4) Если GI Fmin, то удаляем из H все наборы, которые содержат поднабор I (см. замечание 3.2).

5) Если в H рассмотрены не все наборы, то переходим к шагу 2.

6) Искомое решение, согласно теореме 3.2 и замечанию 3.1, определяется тем набором I, для которого FI = Fmin.

В параграфе 3.2 приводится следующий метод сокращения общего количества вычислений. Множество U (см. формулу (3)) содержит ограничения:

где полагается M = ql, согласно результатам параграфа 1.3.

В алгоритме, описанном в параграфе 3.1 на шаге 3 производится корректировка значения Fmin. При этом можно после каждого шага брать M = Fmin. Тогда на каждом шаге область ограничений не увеличивается, а в некоторых случаях уменьшается. Кроме того, при фиксированном уровне точности такой подход может позволить заметно сократить количество итераций за счет того, что, начиная с некоторого шага, линейные размеры области ограничений окажутся меньше величины ошибки.

Замечание 3.3. Во многих случаях оказывается полезным в первую очередь решить задачу RI при I = {1,..., n}, тем самым уже на первом шаге существенно уменьшив область ограничений.

В экспериментах, приведённых в параграфе 4.3, наиболее существенное уменьшение области ограничений происходило именно на таком первом шаге.

В параграфе 3.3 описана модификация приведённого алгоритма для эффективной работы на многопроцессорных системах.

В параграфе 3.4 рассматривается возможность уменьшения степени полиномиального алгоритма за счёт уменьшения количества РО.

Рассмотрим начальный набор распознающих операторов B = {Bk }, который является базисным для задачи распознавания Z. Решение задачи R(B) дает алгоритм A(B), корректный для Z, причем степень обобщённого полинома запишем, как F (B) = F (R(B)).

Определение 3.1. Пусть для набора B заданы функции uv (), y определяющие ограничения оптимизационной задачи. Будем говорить, что:

• набор B B имеет тип 1, если для некоторой пары (u, v) M выполняется uv () = c2 ;

• набор B B имеет тип 0, если для некоторой пары (u, v) M выполняется uv () = c1.

Теорема 3.4. Из распознающих операторов набора B обобщённый полином наименьшей степени может быть образован либо всем набором B, либо поднабором B B, соответствующим тупиковому покрытию множества M1. При этом B является оптимальным тогда и только тогда, когда имеет тип 1.

Из теоремы 3.4 следует, что достаточно решить задачу R для набора B и всех его тупиковых (или базисных) поднаборов.

В параграфе 3.5 приводится адаптация методов увеличения эффективности для случая минимизации числа слагаемых.

Описывается алгоритм нахождения подмножества исходного набора распознающих операторов B, дающего корректный обобщённый полином минимальной степени.

Алгоритм.

1) Решаем задачу R(B). По определению 2.3 проверяем тип набора B.

Если получен тип 1, то задача решена. Иначе, переходим на следующий шаг.

2) Для каждого оператора из набора B = {Bk } находим множество M (Bk ) множество отмеченных пар.

3) Находим все тупиковые покрытия множества M1 множествами M (Bk ), k = 1, n. Пронумеруем наборы, соответствующие покрытиям Bi, i = 1, N .

4) Последовательно решаем задачи R(Bi ), и среди полученных решений выбираем то, которое даёт наименьшую степень.

Аналогично результатам параграфа 3.2 описан метод упрощения перебора тупиковых, основанный на уменьшении ограничения M. Пусть на p-й итерации минимальным решением является Fmin = F (Bs ), s p, тогда при решении задачи R(Bp+1 ) мы можем положить M = Fmin.

Таким образом, мы на каждом шаге будем сужать область ограничения последующих задач, за исключением тех шагов, где область ограничения окажется пуста. Здесь также возможно применение приближенного подхода.

Описан подход к эффективному распараллеливанию рассматриваемого алгоритма, аналогичный приведённому в параграфе 3.3.

В главе 4 приведены результаты экспериментального исследования рассмотренных методов.

Для практических задач ограничения на набор распознающих операторов, наложенные в определении 2.3, являются очень жёсткими.

Поэтому в параграфе 4.2 описывается расширение предложенного метода, позволяющее строить обобщённые полиномиальные корректоры над более широким классом распознающих операторов.

В параграфе 4.3 приведены практические эксперименты. В качестве источника данных используются задачи из репозитория UCI.

Для практического исследования работы алгоритма нахождения обобщённого полинома минимальной степени на заданном наборе из n распознающих операторов, этот алгоритм реализован на языке MATLAB.

Каждая вспомогательная задача сводится методом линеаризации к последовательности задач квадратичного программирования (см. параграф 2.6.1). В качестве процедуры решения задачи квадратичного программирования используется метод quadprog из пакета Optimization Toolbox, который основан на обобщённом методе Ньютона (см. параграф 2.6.3). Для обработки случая, когда набор операторов не является базисом, используются результаты параграфа 4.2. В качестве первой вспомогательной задачи рассматривается задача RI при I = {1,..., n} для уменьшения величины M (см. замечание 3.3). Затем применяется алгоритм сокращения перебора вспомогательных задач (см. параграф 3.1).

При решении рассматриваемых задач используется набор алгоритмов из пакетов MatLabArsenal и WEKA.

Предложенный алгоритм сравнивается в режиме скользящего контроля с алгоритмом голосования.

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

В результате применение декомпозиции исходной задачи существенно уменьшает время её решения. Фактически, после этой операции время решения становится пригодным для практического использования.

А применение метода линеаризации для перехода к задаче квадратичного программирования и использование подходов главы 3 позволяет ещё раз заметно повысить эффективность алгоритма.

Список публикаций по теме диссертации 1. Романов М. Ю. Об одном методе построения распознающего алгоритма в алгебре над множеством вычисления оценок // Ж. вычисл.

матем. и матем. физ. 2007. Т. 47, № 8. С. 1426–1430.

2. Романов М. Ю. Построение корректного распознающего алгоритма минимальной степени в алгебре над множеством алгоритмов вычисления оценок // ММРО-13. М.: МАКС Пресс, 2007. С. 60–62.

3. Романов М. Ю. Реализация одного метода построения распозающего алгоритма в алгебре над множеством алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. 2008. Т. 48, № 9.

4. Романов М. Ю. Полиномиальный корректный распознающий алгоритм минимальной степени в алгебре над множеством алгоритмов вычисления оценок // ИОИ-2008. Симферополь, 2008.