Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходе тема диссертации и автореферата по ВАК РФ 05.13.17, доктор физико-математических наук Косовская, Татьяна Матвеевна

• Косовская, Татьяна Матвеевна
• доктор физико-математических наук
• 2009

Оглавление диссертации доктор физико-математических наук Косовская, Татьяна Матвеевна

Введение.

Глава I. Общая постановка рассматриваемых задач распознавания

1.1. Языки исчисления высказываний и исчисления предикатов как средство формализации описаний.

1.2. Оценки сложности задач и алгоритмов, классы сложности

1.3. Описания объектов как совокупность формул.

1.4. Описания классов как формулы формализованных языков

1.5. Построение описаний классов с глобальными характеристиками объектов.

1.6. Построение описаний классов с локальными характеристиками объектов.

I.7. Постановка задач распознавания как задач нахождения вывода в логических исчислениях.

Глава II. Оценки числа шагов работы алгоритмов, решающих поставленные задачи.

II. 1. Распознавание объектов при их глобальной характеризации пропозициональными переменными.

11.2. Распознавание объектов при их локальной характеризации предикатными формулами.

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

II.4. Пример распознавания объекта с локальными характеристиками и оценки числа шагов.

Глава III. Многоуровневое описание классов как средство эффективиза-ции алгоритмов, решающих различные задачи распознавания образов

III.1. Многоуровневое описание классов.

111.2. Условия уменьшения числа шагов решения задач распознавания образов, описываемых пропозициональными формулами.

111.3. Примеры построения двухуровневых описаний классов при глобальной характеризации объекта.

111.4. Условия уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов.

III.5. Пример применения двухуровневого описания при локальной характеризации объекта.

111.6. Использование многоуровневого описания классов для построения нейронных сетей.

111.7. Многоуровневое описание классов в задачах распознавания образов как средство для параллелизации вычислений.

Глава IV. Адаптация логико-предметной распознающей системы к неполной информации.

IV. 1. Построение неполного вывода как средство адаптации распознающей системы к неполной или недостоверной информации.

IV.2. Оценки числа шагов построения неполного вывода.

IV.3. Распознавание в условиях неполной информации. Построение неполного вывода.

IV.4. Пример распознавания частично заслоненного объекта.

Глава V. Адаптация логико-предметной распознающей системы к преобразованиям, не выводящим из заданного класса.

V.l. Инвариантность к заданному множеству преобразований. Инвариантные признаки и инвариантные описания классов.

V.2. Инвариантные описания классов с неинвариантными признаками

V.3. Задача инвариантного распознавания как задача поиска логического вывода.

V.4. Алгоритм инвариантного распознавания.

V.5. Оценки числа шагов работы алгоритмов инвариантной идентификации

V.6. Примеры инвариантных распознающих систем с неинвариантными признаками.

Введение диссертации (часть автореферата) на тему «Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходе»

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

Существенной чертой задач искусственного интеллекта является большая размерность как исходных данных, так и математических описаний поставленных задач. В современной научной литературе имеется достаточно мало работ, посвященных оценке числа шагов решения задач искусственного интеллекта, связанных с конкретным выбором средств их решения. Математические работы, как правило, посвящены доказательству сходимости предложенных алгоритмов [2, 29, 36] или доказательству условий применимости рассматриваемого метода решения задач [12, 13]. Работы, посвященные практической реализации имеющихся алгоритмов, решают конкретные задачи, зачастую используя те или иные эвристики, мало применимые к решению другой конкретной задачи [17].

В то же время усилия многих ученых, работающих в области математических основ информатики, посвящены доказательству не только правильности работы алгоритма, решающего поставленную задачу, но и оценок числа шагов его работы [1, 7, 41]. Это особенно актуально для алгоритмов, решающих задачи искусственного интеллекта, прежде всего в связи с огромным объемом информации, которую необходимо обработать на компьютере.

Особое место занимают задачи, относительно которых доказаны их ЫР-полнота или КР-трудность [7, 41, 42]. Широко распространено мнение, что такие задачи не предназначены для их реализации па компьютере с большим объемом исходных данных в силу огромного времени их решения. Выделение подзадач таких задач, имеющих полиномиальные верхние оценки числа шагов решения, — одно из направлений, имеющих целью выделить границы практической применимости создаваемых моделей [19, 21, 43]. Одним из способов выделения таких подзадач является не только доказательство КР-пол ноты или КР-трудности исходной задачи, но и установление достаточно точных верхних оценок числа шагов алгоритмов, решающих исходную задачу.

Неформальное описание задач распознавания. Под задачей распознавания образов в разной литературе зачастую понимают разные задачи. В частности, в [5] к ним относят, например, следующие.

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

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

Разбиение множества всех объектов на классы (образы), если это не задано в постановке задачи (кластеризация).

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

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

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

Среди задач распознавания можно выделить следующие, рассматриваемые в диссертации.

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

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

Задача анализа сложного объекта, состоящая в нахождении и классификации всех частей сложного объекта, а также в определении соотношений между этими частями.

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

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

Обзор имеющихся результатов по теме диссертации. Первое, с чем сталкивается теория распознавания образов - это выбор набора признаков, на основании которых будет производиться распознавание. В работе [5] определены четыре класса таких признаков: детерминированные (принимающие конкретные числовые значения); вероятностные (случайные значения которых распределены по всем классам объектов); логические (принимающие два значения „истина" или „ложь"); структурные (являющиеся непроизводными элементами структуры объекта).

В соответствии с тем, па языке каких признаков производится описание объектов, системы распознавания могут быть подразделены на детерминированные, вероятностные, логические, структурные и комбинированные [5]. В работах Ю.И. Журавлева [10, 11, 12, 13] и его учеников рассматриваются алгебраические распознающие системы, представляющие собой комбинацию детерминированных и логических систем распознавания.

В каждом из этих подходов описания классов являются аналогом понятия фрейм, введенного Н. Минским [26].

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

Выбор набора признаков может быть обусловлен различными причинами: наилучшее разделение классов [2], наименьшая стоимость измерения признаков (даже до определенной степени в ущерб качеству распознавания) и минимизация количества измерений [14], простота полученных решающих правил [29] и многими другими.

Методы построения рабочего набора признаков по известному исходному набору изложены, например, в [2, 5, 29].

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

В теории построения систем распознавания образов наряду с другими широкое распространение получили и логические методы [30, 13, 15]. Рассматриваемые в литературе логические методы описаний классов сводятся к представлению связей между отдельными признаками объекта в виде булевых функций или булевых уравнений. Решение булевых уравнений равносильно доказательству истинности (или выводимости) формул исчисления высказываний, перед которыми стоят кванторы существования по пропозициональным переменным. Методы получения и представления знаний, в частности, в виде продукций, хорошо приспособленных для доказательства целевых условий методом резолюций, рассмотрены, например, в [3].

Никакие потенциально бесконечные классы объектов, описание которых существенным образом задается формулами исчисления предикатов, с помощью булевых уравнений описать нельзя. В [30] на стр. 550 приведена экспоненциальная оценка числа пропозициональных переменных в пропозициональных формулах, моделирующих формулу исчисления предикатов в конечной области для задач планирования

Т х \Act\ х |0|р, где Т - количество временных этапов, \Act\ - количество схем действий, |0| - количество оюъектов в проблемной области, Р - максимальная арность (количество параметров) любой схемы действий. В диссертации для одного из предложенных алгоритмов оценка числа шагов решения задач распознавания, описанных формулами исчисления предикатов, имет в точности такой же вид. Однако используемая память существенно меньше.

Идея существенного использования исчисления предикатов и построения терма (последовательности функций, воздействующих на объект), задающего последовательность действий в задачах планирования движения, использовалась Нильсоном Н. [27], Хантом Э. [37] и многими другими. Однако применение этих идей к решению задач распознавания образов автору диссертации неизвестны.

Воздействие преобразований на распознаваемый объект может происходить в разных ситуациях: это могут быть как искажения эталонного объекта (афинные преобразования изображения, десинхронизация видеоизображения по строкам и т.п.), так и сознательное воздействие на объект с целью перевода его в другой класс (выбор метода лечения, ремонт технической системы и т. п.). Предложенные автором диссертации описания преобразований (ОП) [51] позволяют строить логико-предметную распознающую систему, инвариантную относительно заданной совокупности преобразований, а также находить последовательность преобразований, переводящую объект из одного класса в другой.

Задача построения распознающей системы, инвариантной относительно заданной совокупности преобразований в [33, 38] решалась путем построения полной системы инвариантов для множества объектов, рассматриваемого как пространство функций. При этом под инвариантами относительно группы преобразований понимаются такие функционалы, которые принимают одинаковое значение как на эталонном объекте, так и на объекте, полученном из эталонного, после воздействия на него преобразованием из заданной группы преобразований. В этих работах система полных инвариантов строится на основании преобразования Фурье.

В работах [17] рассматривается подход к распознаванию геометрических фигур, образованных конечными множествами точек на плоскости или в пространстве, существенным образом опирающийся на внутреннюю кодировку фигур, инвариантную к афинным преобразованиям. Эта кодировка основана на рассмотрении всех симплексов, образованных точками фигуры и введении меры таких симплексов.

В диссертации аналогом таких инвариантов выступают описания преобразований.

Решение всех задач, рассматриваемых в диссертации, сведено к решению задач доказательства теорем простого подмножества формул исчисления высказываний и исчисления предикатов [16]. Доказательство таких теорем может быть проведено, например, посредством применения метода резолюций [31, 27, 30] (и даже линейных стратегий метода резолюций [23], или в секвенциальных исчислениях высказываний и предикатов [16, 20]. Поскольку метод резолюций и секвенциальные исчисления хорошо приспособлены для их компьютерной реализации, то оценки числа шагов алгоритмов построения вывода в диссертации приводятся именно для этих методов доказательства.

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

В диссертации рассматривается логико-аксиоматический подход к решению задач распознавания образов, основанный на сведении некоторых задач распознавания образов к задачам поиска вывода в логических исчислениях. Термин „логико-аксиоматический метод решения задач распознавания образов" был предложен совместно автором диссертации и A.B. Тимофеевым ещё в 80-ые годы [45] в связи с тем, что описание класса представляет собой формализацию утверждений об объектах, безусловно истинные для каждого объекта из этого класса и, следовательно, могут рассматриваться как аксиомы этого класса. При этом рассматриваются задачи, в которых объекты могут быть описаны с помощью логических формул. При использовании пропозициональных формул такой подход является достаточно представительным частным случаем логико-алгебраического подхода, подробно обоснованного и развитого в работах Ю.И. Журавлева [13]и его учеников .

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

Логико-предметный подход к решению задач распознавания образов представляется удобным также в случаях, когда параметры распознаваемого объекта имеют интервальный характер или описания объекта содержат взаимоисключающие признаки, например, цвет объекта. В первом случае можно ввести предикат, зависящий дополнительно от трех аргументов х, а, Ь, истинный на тех значениях переменной х, для которых а < х < Ъ. Во втором случае можно рассматривать предикат, дополнительно зависящий от параметра г, являющегося номером соответствующего бинарного признака. Например, если рассматриваемые объекты могут иметь один из девяти цветов (черный, белый и 7 цветов радуги), то для того, чтобы указать, что объект белый, вместо набора значений (0,1,0,0,0,0,0,0,0) достаточно записать р(2).

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

В [45] рассматриваемые в диссертации задачи распознавания образов сведены к задаче проверки выводимости формул описанного ниже вида из заданного множества атомарных формул. В этой работе автору диссертации принадлежит основная идея и детальная проработка подхода, Тимофееву A.B. - общая постановка задачи и научное руководство.

Как уже было сказано, одним из важных направлений в создании алгоритмических моделей решения тех или иных задач является доказательство оценок числа шагов таких алгоритмов. В общей постановке задача проверки истинности (или выполнимости) формул вызывает значительные трудности. Так, например, для исчисления высказываний задача проверки выполнимости формулы в КНФ является МР-полной [7].

Для формул исчисления предикатов различного вида можно получить разрешимые фрагменты. В [52] сформулированы серии задач, для которых доказаны их КР-полнота, в то время как для каждой задачи этой серии имеется полиномиальный разрешающий алгоритм.

В диссертации для решения задач распознавания образов для каждого конкретного описания классов доказаны линейные (от длины записи описания распознаваемого объекта) по времени оценки числа шагов алгоритмов, решающих эти задачи для пропозиционального случая [46, 66]. Рассмотрен разрешимый фрагмент исчисления предикатов, в котором могут быть формализованы задачи распознавания образов. Доказано, что если описания классов являются исходными данными алгоритмов, то задачи распознавания образов с признаками-предикатами являются ЫР-трудными. При этом, так же как и в [52], для каждого конкретного описания классов эти задачи имеют полиномиальный (со степенью полинома, зависящей от длины записи описания классов) алгоритм решения.

В [64] предложены многоуровневые описания классов, при использовании которых в диссертации доказаны условия уменьшения числа шагов работы алгоритмов, решающих рассматриваемые задачи распознавания образов [47, 49, 69, 65]. Многоуровневые описания классов являются также удобным средством анализа составных сложных объектов.

Введение предикатов различных уровней оказалось полезным при создании искусственных нейронных сетей [48, 67].

Диссертация состоит из введения и пяти глав. Во введении изложена содержательная постановка задач распознавания образов, рассматри

Заключение диссертации по теме «Теоретические основы информатики», Косовская, Татьяна Матвеевна

ЗАКЛЮЧЕНИЕ

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

1. Доказаны оценки числа шагов алгоритмов решения задач распознавания:

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

Для случая локальной характеризации объекта признаками, задающими свойства его частей и отношений между ними, и выражаемыми предикатами, для трех предложенных алгоритмов доказаны экспоненциальные от длины записи описаний классов оценки числа их шагов. Рассмотрены две задачи о выполнимости предикатной формулы в конечной интерпретации и доказана их NP-полнота. Из NP-полноты этих задач как следствие доказана NP-трудность рассмотренных задач распознавания образов.

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

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

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

3. Построение нейронных сетей и распараллеливание вычислений, использующие многоуровневое описание классов.

Предложено применение многоуровневого описания классов к построению искусственных нейронных сетей с логическими нейронами.

Показано, что многоуровневые описания классов обеспечивают естественное распараллеливание вычислений, отличное от классического И/ИЛИ параллелизма.

4. Неполный вывод как средство адаптации распознающей системы к неполной информации и оценки числа шагов его реализации.

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

Дается алгоритм решения задачи идентификации объекта с неполной информацией (в частности решение задачи распознавания частично заслоненного объекта) с выделением той части, относительно которой с уверенностью д можно утверждать, что идентификация произведена верно. Доказываются оценки числа шагов его работы.

5. Алгоритмы и оценки числа их шагов при распознавании объектов, подвергнутых искажениями из заданной группы преобразований.

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Косовская, Татьяна Матвеевна, 2009 год

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Васильев В.И. Конструирование пространства в процессе обучения распознаванию образов // Автоматика, 1982, № 5. С. 18-27.

3. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПБ: Питер, 2000. 384 с.

4. Горелик А.Л. Об одном подходе к выбору пространства признаков, используемого при построении системы распознавания объектов и являний // Кибернетика, 1972, № 4. С. 142-146.

5. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1984. 208 с.

6. Гузман А. Декомпозиция зрительных сцен // Интегральные роботы, вып.1, М: Мир, 1973.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., "Мир 1982. 416 с.

8. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. 511 с.

9. Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1977. 128 с.

10. Журавлёв Ю.И. Алгебраический подход к проблеме распознавания // Проблемы кибернетики, 1978, вып. 33. С. 35-43.

11. Журавлёв Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов // Кибернетика: I, 1977, №4. С. 14-21; II, 1977, № 6. С. 21-27; III, 1978, № 2. С. 35-43.

12. Журавлёв Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. 1989. М.: Наука. С. 9-16.I

13. Журавлёв Ю.И. Об алгоритмах распознавания с представительными наборами (о логических алгоритмах) // Журнал вычислительной математики и математической физики, 2002, т. 42, № 9. С. 1425-1435.

14. Загоруйко Н.Г. Прикладные методы анализа данных и знаний — Новосибирск: Изд-во Ин-та математики, 1999. 270 с.

15. Закревский А.Д. Выявление импликативных закономерностей в булевом пространстве признаков и распознавание образов // Кибернетика, 1982, № 1. С. 1-6.

16. Клини С. Математическая логика. — М.: Мир, 1973. 480 с.

17. Козлов В.Н. Элементы математической теории зрительного восприятия — М.: Издательство Центра прикладных исследований при механико-математическом факультете МГУ, 2001. 128 с.

18. Комашинский В.И., Смирнов Д.А. Нейронные сети и их применение в системах управления и связи. М.: Горячая линия Телеком, 2002. 94 с.

19. Косовская Т.М., Косовский H. К. Об эффективности получения бу-левого решения у полиномиальных сравнений и у систем из них // Матер. IX Междунар.семинара «Дискретная математика и ее приложения», МГУ. 2007. С. 97 99.

20. Косовский Н.К. Элементы математической логики и её приложения к теории субрекурсивных алгоритмов. Л.: изд-во ЛГУ, 1981. 192 с.

21. Косовский Н.К., Косовская Т.М. Полиномиальность и NP-трудность задачи вычисления знака постоянного терма // Математические вопросы кибернетики. Вып.16. 2007. С. 125 128.

22. Круглов В.В. Борисов В.В. Искусственные нейронные сети. Теория и практика. М.: Горячая линия Телеком, 2002. 382 с.

23. Курьеров Ю.Н. Условия полноты тактики линейного вывода // Семантические вопросы искусственного интеллекта. Киев, 1977. С. 4445.

24. Леденева Т.М., Подвальный C.B., Васильев В.И. Системы искусственного интеллекта и принятия решений: Учебное пособие. Уфа: УГАТУ, 2005. 206 с.

25. Маслов С.Ю. Связь между тактиками обратного метода и метода резолюций // Записки научных семинаров ЛОМИ АН СССР, т. 16, 1969. С. 137-146.

26. Минский Н. Фреймы для представления знаний. М.: Энергия, 1979. 152 с.

27. Нильсон Н. Искусственный интеллект. М.: Мир, 1973. 270 с.

28. Пулатов A.M., Никифоров A.C. Справочник по семиотике нервных болезней. Ташкент: Медицина, 1983. 200 с.

29. Пшибихов В.Н., Тимофеев A.B. Полные системы логических разделяющих функций и оптимальные опознающие графы // Методы вычислений. Л., 1973, № 7. С. 36-46.

30. Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ. М.: Издательский дом "Вильяме", 2006. 1408 с.

31. Робинсон Дж. Машинно ориентированная логики, основанная на методе резолюций // Кибернетический сборник, новая серия. М., 1970, вып. 7. С. 194-218.

32. Соловьев H.A. Тесты. Новосибирск, 1979. 189 с.

33. Тимофеев A.B. Математическая модель инвариантного восприятия и опознания по группам преобразования // Кибернетика и вычислительная техника. Киев: Наукова думка, 1973. С. 48-54.

34. Тимофеев A.B. Адаптивная система логического вывода и оптимальные опознающие графы // Вопросы кибернетики. Адаптация в системах со сложной организацией. М.: Научный совет по комплексной проблеме „Кибернетика" АН СССР, 1977. С. 33-35.

35. Тимофеев A.B. Управление роботами. Л.: Изд-во Ленингр. ун-та. 1986. 240 с.

36. Фомин В.Н. Математическая теория обучаемых опознающих систем. Л., 1976. 235 с.

37. Хант Э. Искусственный интеллект. — М.: Мир, 1978. 558 с.

38. Шмидт А.А. Построение полных систем непрерывных инвариантов для некоторого класса групп преобразований изображений // Деп. в ВИНТИ, 6879-83, 1983.

39. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов. 2-е изд., перераб. и доп. - М.: Наука,-1986. 384 с.

40. Яблонский С.В. Тест // Математическая энциклопедия, т.5, М.: „Советская энциклопедия", 1985. С. 342-346.

41. Du D.-Z., Ко K.-I. Theory of Computational Complexity. A Wiley-Interscience Publication. John Wiley & Sons, Inc. 2000. 491p.

42. Johnson D. The NP-completeness column // ACM Trans. Algorithms 1(2005) No 1, 160-176.

43. Wang Lusheng, Zhao Нао, Dong Guozhu, Li Jianping. On the complexity of finding emergin patterns // Theor. comput. Sci. 2005, 335, N 1. P. 15-27.

44. РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

45. Статьи в журналах, рекомендованных ВАК,

46. Косовская Т.М., Тимофеев A.B. Об одном новом подходе к формированию логических решающих правил Вестник ЛГУ, 1985, №8. С. 22-27.

47. Косовская Т.М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестн. С.-Петербург.ун-та. Сер. 1. 2007. Вып.(4) С. 82-90.

48. Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых пропозициональными формулами // Вестн. С.-Петербург, унта. Сер. 1. 2008. Вып.1. С. 29-37.

49. Косовская Т.М., Тимофеев A.B. Иерархическое описание классов и нейросетевое распознавание сложных образов // Нейрокомпьютеры: разработка, применение. 2007. № 6. С. 30-33.

50. Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов // Вестн. С.-Петербург.ун-та. Сер. 10. 2008. Вып.1. С. 64-72.

51. Косовская Т. М. Частичная выводимость предикатных формул как средство распознавания объектов с неполной информацией // Вестн. С.-Петербург.ун-та. Сер. 10. 2009. Вып. 1. С. 74-84.

52. Косовская Т.М. Распознавание объектов из классов, замкнутых относительно группы преобразований // Вестн. С.-Петербург.ун-та. Сер. 10. 2009. Вып. 3. С. 45-55.

53. Косовская Т.М., Косовский Н. К. О числе шагов получения булевого решения у полиномиальных сравнений и у систем из них // Вестн. С.-Петербург, ун-та. Сер. 1. 2007. Вып. 3. С. 84-90.1. Другие публикации

54. Косовская Т.М., Мишин С.Н., Тимофеев A.B. Алгоритмы и программы логического анализа изображений и сцен // Всесоюзная научно-техническая конференция «Образный анализ многомерных данных» (тезисы докладов), 2-3 октября 1984г., Владимир, 1984. С.79-80.

55. Kosovskaya Т.М., Timofeev A.V. Logic-Axiomatical Method of Recognition and its Application // Proceedings of Symposium IFAC on

56. Artificial Intelligence, Leningrad, 4-6 October 1983. IFAC proceedings series No 9, Pergamon Press, 1984. P. 523-528.

57. Косовская T.M. Распознавание преобразованных и искаженных изображений // Тезисы докладов Всесоюзного симпозиума «Зрение организмов и роботов» (Вильнюс, 1-3 октября 1985 г.), т. 2, Вильнюс, 1985. С. 59-60.

58. Kossovskaya Т.М., Timopheev A.V. Logic-Axiomatical Method of Intellectual Recognition of Complex and Distributed Objects // Proceedings of Symposium IFAC « Distributed and Intellectual Systems. Methods and Applications», v. 2, Varna, Bulgaria, 1988.

59. Kossovskaya T.M., Timopheev A.V. Adaptive Logical Recognition Algorithms for Expert Systems IMS // Third International Summer Seminar on Intelligent Manufacturing Systems (August 28 September 2), Dubrovnik, Yugoslavia, 1989.

60. Kossovskaya T.M., Timopheev A.V. Methods of Adaptive Logical Recognition and its Application // International Conference «Artificial Intelligence Industrial Application» (Abstracts of papers) (Leningrad, 15-19.04.1990),1990. P. 247-249.

61. Timofeev A.V., Kosovskaya T.M. Logic-Axiomatical Method of Knowledge Representation and Recognition for Robots // Computers in Industry 15, Elsevier Science Publishers B.V., 1990. P.3-6.

62. Косовская T.M., Миронов C.H., Тимофеев A.B. Экспертные системы адаптивного логического распознавания и их применение // Адаптивные и экспертные системы в управлении. Тезисы докладов 5-го

63. Ленинградского симпозиума по теории адаптивных систем, ч. II, 1990.

64. Kossovskaya Т.М. Complexity bounds of some pattern recognition problems // Abstrscts of the Second International Conference «Mathematical Algorithms», Nizhny Novgorod, 1995. P.28.

65. Косовская Т.М. Оценки сложности решения задач распознавания при иерархическом описании классов // Тез. докл. на XI Междунар. конф. по проблемам теоретической кибернетики. Ульяновск, 1996.

66. Косовская Т.М. Многоуровневые описания классов для принятия решений в задачах распознавания образов Тр. III Междунар. конф. "Дискретные модели в теории управляющих систем". М., Диалог — МГУ, 1998.

67. Т.М.Косовская, А.В.Тимофеев. Иерархическое логическое описание и нейросетевое распознавание сложных образов // Proc. of XIII-th International Conference "Knowledge-Dialogue-Solution"(KDS-2007)(June 18-24, 2007, Varna, Bulgaria), vol. 1, pp. 22-27.

68. A.Timofeev, T.Kosovskaya. Conditions of Effectiveness of Pattern Recognition Problem Solution Using Logical Level Descriptions of

69. Classes // Proc. of XIII-th International Conference "Knowledge-Dia-logue-Solution"(KDS-2007) ( June 18-24, 2007,Varna, Bulgaria), vol. 2, pp. 572-575.