Реконструкция по частичным представлениям в комбинаторике слов Сметанин Юрий Геннадиевич

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Сметанин Юрий Геннадиевич. Реконструкция по частичным представлениям в комбинаторике слов : Дис. ... д-ра физ.-мат. наук : 05.13.17 : Москва, 2003 184 c. РГБ ОД, 71:05-1/68

Содержание к диссертации

Введение

Глава I. Комбинаторика слов и задачи реконструкции 33

1. Основные направления исследований в комбинаторике слов и задачи синтеза слов 33

2. Формулировка задач реконструкции слов 38

3. Алгоритмическая сложность задач реконструкции слов 41

4. Независимость полноты множеств от алфавита 47

5. Сжимающие классы и конгруэнтность V- множеств 52

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

Глава II. Первая модель реконструкции 63

1. Алгебраическое описание классов эквивалентности 63

2. Полнота характеристических множеств 68

3. Верхняя граница длины к для полных V -множеств Е 70

4. Нижняя граница длины к для полных V -множеств Е 75

5. Реконструкция по подсловам 80

Глава III. Вторая модель реконструкции 88

1. Алгебраическое описание классов эквивалентности 91

2. Полнота V-множеств Е„к 92

3. Реконструкция слов с малым числом серий 95

4. Вторая модель реконструкции в случае многозначного алфавита 100

5. Распознавание по полсловам 102

Глава IV. К-реконструкция в кодировании и распознавании образов 104

1. Реконструкция по длинным фрагментам 104

2. Распознавание по коротким фрагментам 114

3. Двумерная -реконструкция и математическая морфология 122

4 F-множества в стеганографии 136

5. Нейросетевые модели для реализации алгоритмов реконструкции слов 141

6. Нахождение и устранение ложных решений в нейронных сетях 145

7. Повышение емкости нейронных сетей с безошибочным обучением 153

Литература 158

Алгоритмическая сложность задач реконструкции слов
Верхняя граница длины к для полных V -множеств Е
Вторая модель реконструкции в случае многозначного алфавита
Двумерная -реконструкция и математическая морфология

Введение к работе

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

Теория реконструкции слов возникла в результате интеграции алгебраической комбинаторики слов с методами теории кодирования и распознавания образов. Спецификой теории реконструкции как раздела комбинаторики слов является ее основная задача: синтез слов по частичным представлениям, впервые сформулированная в работах В.К.Леонтьева [21, 35, 36, 39].

Комбинаторика слов

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

Историю комбинаторики слов можно вести от работ А. Туэ в начале XX века [255, 256], однако становление ее как самостоятельной дисциплины относится ко второй половине 80-х гг. XX века. Главной целью разработчиков новой области [5, 190, 191] является изучение слов как самостоятельного объекта с точки зрения их внутренней структуры. Многие важные результаты по комбинаторике слов были открыты в теории чисел, теории групп, теории вероятностей, кодировании. Используемые методы определялись в первую очередь спецификой этих областей. Создание комбинаторики слов как особой области способствует взаимопроникновению различных методов и созданию новых подходов к решению возникающих задач.

В качестве примеров такого взаимопроникновения можно привести лемму о периодичности Файна - Уилфа [145], алгоритм Маканина [42] и свойство компактности свободных моноидов [83].

Фундаментальный результат Маканина о разрешимости уравнений в свободных полугруппах непосредственно применим в комбинаторике слов, но в теории групп он был осознан как чисто теоретический, фактически как теорема существования. Практическое значение он получил именно в теории слов после того, как был предложен алгоритм решения уравнений в словах, принадлежащий классу PSPACE [219].

Свойство компактности возникло уже в рамках собственно теории слов. Оно показывает, что любая независимая система над свободным моноидом с конечным числом неизвестных является конечной. Поиск верхней границы мощности независимых систем (до сих пор остающейся неизвестной [172]) является важным и интересным направлением дальнейших исследований.

Детальный обзор задач и методов комбинаторики слов представлен в [191].

Задачи комбинаторики слов, связанные с реконструкцией

Задачи реконструкции слов тесно связаны с задачами кодирования [3, 25, 29, 30, 31, 32, 44, 49, 76, 79], распознаванием образов [17, 21, 35, 88, 97, 166], символьным анализом динамических систем [84, 85, 177, 209, 210], конечными автоматами [12, 89, 157, 243], молекулярными вычислениями, анализом последовательностей протеинов и комбинаторным синтезом ДНК [82,199,213,231,264].

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

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

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

Среди результатов, непосредственно связанных с темой данного исследования, следует выделить:

- формулировку метрических задач в w-мерном булевском кубе [38] и задач восстановления слов по фрагментам, полученным с помощью фиксированных правил [36],

- оценки спектров бинарных слов [37],

- оценку максимальной длины цепи в булевом кубе и длины надпоследовательности для множества слов из заданного слоя булева кода [14, 15],

- условия реализуемости матриц расстояний в единичных кубах [1],

- методы покрытия множества слов цепями [47] и покрытия графов маршрутами [48],

- методы описания слов, содержащих все подмножества как подслова [188, 259], и слов, содержащих наименьшее число различных подслов [130],

- перечисление вполне монотонных семейств слов [211],

- меры сложности подпоследовательностей [192],

- методы восстановления объектов по минимальному числу слабо искаженных образцов [32].

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

- метрические методы в «-мерном кубе [38, 64],

- методы автоматического анализа сложности слов [241],

- различные подходы к упорядочению двоичных слов [109],

- теория Шпернера в частично упорядоченных множествах [143],

- конструкции кодов Грея [52],

- методы анализа периодичности слов с помощью нейронных сетей [16].

Место задач реконструкции в комбинаторике слов

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

Относительно простым частным случаем рассматриваемой проблемы является реконструкция по подсловам [61, 62], которой посвящено большинство известных работ по реконструкции слов. При более сложных правилах получения частичных представлений известны только методы, использующие дополнительную информацию о возможных положениях искажений и потерь информации. К ним относятся известные методы реконструкции алгебраических функций по данным с пропусками [89], реконструкции компактных многомерных многообразий по набору расстояний между парами точек из заданного набора [152], нахождения распределения случайной величины или параметров марковских случайных процессов по частичной информации [1, 2, 4], представления конечных автоматов фрагментами поведения [12].

В диссертации рассмотрены задачи реконструкции слова из конечного алфавита в случае, когда

а) задана совокупность правил, в соответствии с которыми образуются искаженные версии слова,

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

Формальная постановка задачи реконструкции

Пусть задано множество ЕР слов длины п. Предполагается, что зафиксировано некоторое множество V подпоследовательностей последовательности {1, 2, ... , «}. Для каждого слова а є ЕР рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством подпоследовательностей V = {v v ... v }. Каждую подпоследовательность из V можно считать каналом с искажениями. Подпоследовательность V є V задана характеристическим набором (/i vr2 ... v „) таким, что v, = 1, если і-й символ слова входит во фрагмент, полученный с помощью V, и v, = 0 в противном случае.

Процедура получения из слова а фрагмента с помощью характеристического вектора v= \л 1-# т описывается в виде операции фрагментирования а, v = {afah...aik). При получении фрагмента Ь є Е? неизвестно, от действия какого именно характеристического вектора на исходное слово получен этот фрагмент.

В данной формулировке задачи вся информация о слове х є ", полученная на выходе канала К, заключается в мультимножестве или множестве V(x). Требуется определить, насколько полно эта информация определяет исходное слово х є".

Сложность задачи реконструкции

Сложность рассматриваемой задачи видна из следующего доказанного результата об NP-полноте задачи о существовании реконструируемого слова уже при коротких подпоследовательностях. Даны: целое число я, характеристическое множество V = {vi, ... , vm}, v, є Еп, I v,= 3, і = 1, 2, ... , m, и набор векторов bjEE3 - 1, 2, ... , m; требуется определить, являются ли векторы bj фрагментами некоторого вектора длины п, то есть существует ли вектор Ь є Еп такой, что для некоторой перестановки ( . . "т. )выполняются равенства \J\J2---Jm! Ь,УІ = Ь;І,І= 1,..., т. Как непосредственное следствие, доказана NP-полнота задачи о единственности реконструируемого слова. Эти результаты говорят о нецелесообразности поиска универсального метода реконструкции. Поэтому далее рассмотрены конкретные виды К-множеств. Зависимость от алфавита в задачах реконструкции Множество V разбивает ЕР на классы эквивалентности; в один класс попадают те слова, у которых множества фрагментов, полученных с помощью совокупности правил К, совпадают. Если каждый класс эквивалентности состоит из одного вектора, множество V называется полным. Следующее утверждение показывает, что в задачах однозначной реконструкции можно ограничиться случаем двоичного алфавита: если множество V является полным на двоичном кубе Е„, то оно является полным и на любом г-значном кубе Еп(г), г = 3, 4, ... . Эта эквивалентность позволяет описывать классы эквивалентности при заданном правиле V определенной булевской функцией - теоретико-множественным перманентом. Две основные модели реконструкции Подробно изучены два наиболее важных и интересных класса задач реконструкции в случае, когда F-множество является к-м слоем куба ЕР. В первой модели входной информацией является мультимножество фрагментов, во второй модели - множество фрагментов (без учета кратности). Доказано, что задача реконструкции в обоих моделях сводится к решению диофантовых уравнений специального вида. В частности, К-множество является полным, если система диофантовых уравнений имеет единственное решение. Это сведение использовано для оценки длины фрагментов к, при которой V-множество Екп является полным. В первой модели получены уточнения границы величины к: C\logn k C2tl . Во второй модели получена точная оценка длины к фрагментов, при которой обеспечена однозначность восстановления произвольного слова длины п\ = Li/2j+l. Частные случаи V-множеств и их применения Получены оценки необходимого и достаточного числа фрагментов для реконструкции при (п - к) « п. Эти оценки использованы для построения алгоритмов коррекция ошибок для многих приемников. Для случая коротких фрагментов и ограниченного набора возможных слов А, \А\= q, исследована задача о минимальной мощности F-множества, обеспечивающего корректное распознавание слов из этого набора. Доказано, что мощность минимального множества - (q - 1). Доказательство основано на представлении слов элементами ультраметрического пространства. Задача о построении минимального множества сведена к построению остовного дерева в графе определенного вида. Для случая, когда отбор фрагментирующих множеств, используемых для построения признаков в данной задаче распознавания, производится по нескольким критериям, предложен псевдополиномиальный алгоритм поиска наборов, обеспечивающих приемлемое качество по каждому критерию. Алгоритм является рандомизированным и принадлежит к классу алгоритмов Монте-Карло. Рассмотрен пример применения этого алгоритма в задаче поиска приближенных соответствий с эталонами в распознавании изображений по наборам локальных геометрических признаков либо инвариантных характеристик. Для реализации восстановления по фрагментам, соответствующим известным окнам, применяется вариант нейронной сети с обучением на основе проецирования на выпуклые множества. Разработанные в диссертации методы представления слов с помощью F-множеств достаточно простого вида использованы в усовершенствовании методов в двух прикладных областях анализа изображений - стеганографии и математической морфологии. В стеганографии фрагментирование используется для разбиения изображения на блоки, несущие скрытую информацию, обеспечивающего улучшенные соотношения между вносимыми искажениями и объемом передаваемой информации. В математической морфологии фрагменты описывают структурирующие элементы. Для оптимизации отбора фрагментов используются генетические алгоритмы и разложения по базису с помощью нейронной сети Хэмминга. Предложены также обобщенные варианты морфологических нейронных сетей [90, 91, 229, 230] и нейронных сетей на основе алгебр Клиффорда [94] для практической реализации предложенных вариантов математической морфологии и распознавания на основе инвариантов. Нейронные сети в неархимедовых числовых полях использованы для анализа информативности Р-множеств. Содержание диссертации по главам Диссертация состоит из Введения и четырех глав. По теме диссертации опубликовано 17 работ (4 работы - в соавторстве). Результаты, изложенные в работе, докладывались на пяти российских и международных конференциях. Перейдем к более подробному изложению содержания диссертации. В главе I рассмотрены общие задачи реконструкции слов по фрагментарной информации и изучена их связь с другими задачами комбинаторики слов. Определены две основные модели реконструкции слов: по мультимножествам и по множествам. Изучены алгоритмическая сложность задачи реконструкции, связи между правилами образования фрагментов и классами, на которые при этом разбивается совокупность слов, а также зависимость классов от алфавита. В § 1 определены общие задачи комбинаторики слов и изучена их связь с задачами реконструкции слов. Приведена содержательная постановка задачи реконструкции как представления слов в виде совокупностей более простых слов. В § 2 приведена формальная постановка задачи реконструкции слов по фрагментам. Определены две модели реконструкции слов -с учетом кратности вхождения фрагментов в слово (I модель) и без учета этой кратности (II модель).

В § 3 изучена алгоритмическая сложность задач о существовании и единственности реконструируемого слова.

Алгоритмическая сложность задачи о существовании неизвестного слова а с заданным набором фрагментов { а, v ), v є V, описана следующим утверждением. Пусть даны целое число п, характеристическое множество V= {vi,..., vOT}, v, є E„, \ v,1 = 3, і = 1, 2, ... , m, и набор векторов bj9j = 1, 2, ... , m; требуется определить, являются ли векторы bj фрагментами некоторого вектора длины w, то есть существует ли вектор b є Еп такой, что для некоторой (??•• \JlJl перестановки ( Г"." . 1 выполняются равенства J т) b,Vi = bJhi=\,...,m. Эта задача А является NP-полной. Доказательство основано на сведении задачи «3-выполнимость». Доказано также следующее непосредственное следствие предыдущего утверждения. Если набор векторов bj,j = 1, 2, ... , т, является набором фрагментов некоторого вектора длины Ь є Еп, то проверка наличия другого вектора, для которого они также являются набором фрагментов, тоже является NP-полной.

В § 4 изучена зависимость сложности задач реконструкции слов от алфавита.

Доказано следующее утверждение: если множество V является полным на двоичном кубе Е„, то оно является полным и на любом г-значном кубе Еп{г), г = 3, 4, ... . Доказательство этого утверждения основано на анализе проекций Еп(г) на Еп(г): {і -» \,j — О при у # і}, / = 0,1,...,/--1}.

Именно этим утверждением оправдан тот факт, что в работе изучаются в основном двоичные векторы.

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

В § 5 изучены сжимающие классы V, расширение которых приводит к сужению классов эквивалентности и, тем самым, к увеличению информации о реконструируемом слове.

Доказано, что К-множества Е„к и Епк и ЕкЛ и ... и Е„° являются конгруэнтными, то есть порождают разбиения на одни и те же классы эквивалентности.

В главе II изучена I модель. Предполагается, что зафиксировано некоторое множество V подпоследовательностей последовательности 1, 2, ... , п. Для каждого слова а є ЕР рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством подпоследовательностей V. Каждая подпоследовательность v є V задана характеристическим набором (vi v2 ... v„) таким, что v, = 1, если і є V, и v,: = 0 в противном случае. На выходе получается именно мультимножество, а не мультипоследовательность, то есть при получении фрагмента Ъ є Vі(а) мы не знаем, от действия какого именно характеристического вектора на исходное слово получен этот фрагмент.

В § 1 описано сведение задачи реконструкции к решению определенной системы диофантовых уравнений. Эта система зависит от конкретного вида К-множества.

Построение системы уравнений основано на использовании следующего равенства для числа вхождений слова а = (а]СС2 ... ат) є Е" в х = (х\ хг... хп) є " в качестве фрагмента при множества F : \axa2...ajv. {і,.../м}єКт где ak=\- ак, Ьк = 2ак-\.

Доказана следующая теорема о сведении К-эквивалентности к решению диофантовых уравнений.

Теорема. Слова а = (а\ ... ап) и Ъ = (J3\ ... Д,) являются V -эквивалентными тогда и только тогда, когда выполняются соотношения V2--- » 1 2 h = I Я«;;/ ДА...Д. Щ іг...і, ,д 1 s qh 1 і т, Я определяются кратностями вхождения фрагментов при заданном F-множестве. Для случая V- Е„ параметры А, имеют вид 1 /,, ... Л и. В § 2 изучены условия полноты F-множества Епк. В этом случае словах с единичными координатами (х\, ... , хт) и у с единичными координатами (уі, ... , ут) являются V-эквивалентными тогда и только тогда, когда равенства »1=1 /2 », ij id i т т т ;,=1 іг іі i ij-x (1) выполняются при всех d 0, ру, зу 0 таких, что d + f,(Pj+qj) k. У-1 Из системы (1) выведены уточненные оценки необходимой и достаточной длины фрагментов, при которой множество V = Е„ является полным. В § 3 доказана следующая оценка нижней границы к. Пусть п(к) - длина наименьших К-эквивалентных слов при V = Екп. Тогда при к 3 выполняется рекуррентное соотношение п(к+\) п(к) + п{к- 1) + 1. Утверждение доказывается прямым построением V-эквивалентных слов для V = Екп, удовлетворяющих этому соотношению. В § 4 получено уточнение верхней границы к сп . Для ее получения использовалась чебышевская аппроксимация приведенной выше системы уравнений для моментов. В главе III изучена II модель. Предполагается, что зафиксировано некоторое множество V подпоследовательностей последовательности 1, 2, ... , п. Для каждого слова а є ЕР рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством подпоследовательностей V. Каждая подпоследовательность v є V задана характеристическим набором (vi vi ... v„) таким, что v,- = 1, если і є V, и v,- = 0 в противном случае. На выходе, в отличие от I модели, получается множество, а не мультимножество, то есть для каждого слова из Ek указано только, входит ли оно в реконструируемое слово в качестве фрагмента при множестве V, но не указано, с какой кратностью оно входит.

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

Доказано следующее утверждение о сведении V-эквивалентности к решению диофантовых уравнений.

Утверждение. Класс эквивалентности является множеством (ОД)-решений полиномиальной системы неравенств

где Wa = {U} - множество всех различных фрагментов, порожденных характеристическим множеством V из слова а и Wa = {v,} дополнение Wa (с учетом размерности соответствующих фрагментов).

В § 2 исследован вопрос о полноте V = Е„к. В отличие от I модели, во II модели этот вопрос решен полностью.

Во II модели получена следующая точная оценка длины фрагментов, при которой обеспечена однозначность восстановления произвольного слова. Пусть А — множество всех различных фрагментов длины к слова х длины п. Тогда необходимым и достаточным условием того, что слово х однозначно восстанавливается по N, является условие к п12. При выполнении этого условия восстановление осуществляется за к х Card(A) операций. Доказательство основано на построении алгоритма реконструкции.

В § 3 рассмотрены средние оценки длины реконструирующих фрагментов.

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

Для этого случая также построен эффективный алгоритм реконструкции.

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

Глава IV посвящена частным случаям F-множеств, имеющим важные практические применения в кодировании и распознавании образов.

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

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

Теорема. Пусть порождающее множество имеет вид V = {(1 2 ... к- 1 к), (2 3 ... кк+ 1), ... , (п-к + 1 п-к + 2 ... п- 1 п)},к п/1 + 1. Если слово А является периодическим с периодом т, делящим (и - к + 1), то F-эквивалентными ему словами являются те и только те слова, которые получаются из А циклическими сдвигами периода.

В случае, когда длина фрагментов к больше половины длины слова, К-множество Екп является сильно избыточным. Получены оценки необходимого и достаточного числа фрагментов для реконструкции при (п - к) « п. Эти оценки использованы для построения алгоритмов коррекции ошибок для многих приемников. Для случая коротких фрагментов и ограниченного набора возможных слов А, \А\= q, исследована задача о минимальной мощности Г-множества, обеспечивающего корректное распознавание слов из этого набора. Доказано, что мощность минимального множества - (q - 1). Доказательство основано на представлении слов элементами ультраметрического пространства. Задача о построении этого множества сведена к построению остовного дерева в графе определенного вида. Для случая, когда отбор фрагментирующих множеств, используемых для построения признаков в данной задаче распознавания, производится по нескольким критериям, предложен псевдополиномиальный алгоритм поиска наборов, обеспечивающих приемлемое качество по каждому критерию. Алгоритм является рандомизированным и принадлежит к классу алгоритмов Монте-Карло, то есть доказывает существование приемлемого решения либо отказывается от ответа. Вероятность отказа в случае существования решения - не более (1 -l/(2/z)) для одного теста; здесь h - максимум абсолютного значения элементов. Число вычислительных операций - 0(n3h(n + log h)), объем памяти должен быть достаточен для хранения п чисел длины loginh). Рассмотрен пример применения этого алгоритма в задаче поиска приближенных соответствий с эталонами в распознавании изображений по наборам локальных геометрических признаков либо инвариантных характеристик.

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

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

В стеганографии F-множества описывают кодовые блоки.

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

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

В § 5 описана модель реконструкции при ограниченном списке кандидатов и заданных положениях выпадений символов. Модель основана на методе проецирования на выпуклые множества. Показано, что эта модель сводится к модели Хопфилда и позволяет определять наилучшие значения порогов в последней.

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

В § 6 рассмотрена задача определения числа и положения стационарных точек в нейронных сетях. Предложен метод нахождения и устранения ложных решений в нейронных сетях. Метод основан на случайном выборе сравнительно небольшого числа входных векторов и проверке для них положения выхода [248]. Описанный рандомизированный алгоритм относится к классу Лас-Вегас и дает возможность за полиномиальное по числу нейронов время определить положение достаточно больших областей притяжения для нейронных сетей, если емкость последних полиномиальна.

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

Х= {хке{- \, 1)"}, к = 1, ... , Г, Г « s = 2".

Для него определяется множество выходных векторов Y={yk = limn 00[An{xk)\}.

Тогда Pr = Frothy є Q, #(nei(y),Y) = 0 & I Nei(y) \ (\/qc)s\= 9(r)(l - \lqc)r и при г = qcln{qd), d с

Fr 0(qc)\n(q)(l-qc)gCd]ng=0(qc(ilnq/qd) = 0(lnq/qd-c).

При больших q эта величина меньше 1/2 и тест можно использовать в алгоритме типа Лас-Вегас. Повторяя тестирование с другими случайными входными векторами, можно показать, что со сколь угодно близкой к единице вероятностью центрами достаточно больших областей притяжения являются только те, которые найдены в ходе испытаний. Все остальные области, если они существуют, имеют размер Nei /qcA\ можно оценить суммарные размеры всех малых областей притяжения..

В § 7 предложен метод повышения емкости нейронных сетей, основанный на предварительном кодировании входных векторов.

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

Благодарности

Автор выражает глубокую благодарность своим коллегам — специалистам в области комбинаторного анализа, распознавания образов и прогнозирования из школы академика РАН Ю. И. Журавлева, работающим в ВЦ РАН, за поддержку и благожелательную критику, способствующую осмыслению работы. Особую благодарность автор выражает тем, кого он имеет честь считать своими Учителями - академику РАН Ю. И. Журавлеву, благодаря которому автор начал работать в области комбинаторной оптимизации и распознавания образов, и В. К. Леонтьеву, без постоянного внимания и помощи которого эта работа не могла бы быть написана.

Обозначения и определения

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

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

N, Z, Q, R, C, Qp, S - множества соответственно неотрицательных целых, целых, рациональных, вещественных, комплексных, /»-адических и полиадических чисел;

\_xj - наибольшее целое число, не превосходящее х;

х \ - наименьшее целое число, превосходящее Л;; нод(т, п) - наибольший общий делитель чисел тип; logx=log2x;

к О I п\ w \ \ \— подстановка;

Card (X) - мощность множества X;

А - произвольный алфавит;

AN - множество бесконечных слов;

Az - множество слов, бесконечных в обе стороны;

1 w I - длина слова w;

F(x) - множество подслов слова JC;

F„(x) - множество подслов длины п слова JC;

F(X) - множество подслов множества слов X;

Fn(X) - множество подслов длины п множества слов X;

Е„ - «-мерный булевский куб, то есть множество двоичных векторов (слов над алфавитом из двух символов) длины и;

Е„ - k-YL слой «-мерного булевского куба, то есть множество двоичных векторов длины п с к единицами и (я - к) нулями;

Еп(Г) - и-мерный /-значный куб, то есть множество двоичных векторов длины п с компонентами из множества (0, 1, .../ - 1} (слов над алфавитом из / символов);

v є Еп - фрагментирующий вектор;

V = {vi, ... , vq} - характеристическое (фрагментирующее) множество;

V(a) - мультимножество фрагментов, полученных из слова а = (а\а2... ап) с помощью порождающего множества V;

t/V(a)) UI о) - кратность вхождения вектора /? в

мультимножество V(a);

Рь(а Ь) - расстояние между словами а и Ь в метрике Левенштейна (метрике выпадений и вставок), то есть минимальное число элементарных операций удаления символа и добавления символа, необходимое для того, чтобы преобразовать а в Ь\

VC-dim - емкость Вапника - Червоненкиса;

sgn(z) = ;

{-1, z О

fl,z 0 0(z) = \

[0,z 0

Слова

Словом в алфавите А называется произвольная последовательность символов из этого алфавита. Слово называется конечным, если эта последовательность конечна, и = (щ, иъ ••• , ««)• Слово называется бесконечным (сверхсловом), если эта последовательность бесконечна, и = (щ, иъ ... , ит ...).

Символы алфавита иначе называются буквами. Как правило, рассматриваются конечные алфавиты. Если алфавит бесконечен, это будет оговариваться особо. Слова в алфавите {0, 1, ...,/},/ 2, называются векторами. Подпоследовательность коненого слова - произвольное слово и4 = {uhuh...uik),ix i2 ...ik. Подпоследовательность бесконечного слова - произвольное слово (конечное или бесконечное) uq=(u.uh...uik(...)),ix i2 ...ik{ ...). Подслово слова и4 = {щ м(+1 ... ui+r). Очевидно, что подслова являются частным случаем подпоследовательностей. Серией слова и называется максимальное подслово (и, иі+і ••• Ui+r), состоящее из одинаковых символов, Щ = Щ+\ = ...= щ+г. Функция сложности слова х над алфавитом А - функция, определяющая для каждого натурального п число Р(х, п) подслов длины п в слове: Р{х, п) = Card{Fn{x)). Очевидно, Р(х, 0)=1, Р(х, 1) -число различных символов в х, а для бесконечных слов Р(х, п) Р(х, п+\)иР(х,п + т) Р(х, п)Р(х, т). На множестве слов определяется метрика d, заданная следующим образом: d(x, у) = 2"", где п = min{k \ хк Ук} Пространство AN с этой метрикой называется пространством Кантора. Метрика d является ультраметрикой: для любых х, у, z неравенство треугольника выполняется в усиленной форме d(x, у) тах {d(x, z), d(y, z)} (если d(x, z) = к, d(y, z) = к , к k\ то xk JtZ]0yk = zki следовательно, xk # Ук и d(x, у) к). Другими словами, метрика d является неархимедовой. В пространстве AN определена также псевдоультраметрика Л(х, у) = Inf{e: 3 -цепь, связывающая х и у), х, у є е. Эта псевдоультраметрика называется цепным расстоянием. Последовательность хп сходится в пространстве Кантора к у, у = lim х", если xnj = у І при достаточно больших п. Например, апЬа сходится к а03. Пример 1. Слово Туэ - Морзе t над алфавитом {0, 1} определяется соотношениями t- lim ип, Л-»00 Щ = 0, Vo = 1, Щ+1 = unvm vn+} = vnun. Слово t является морфическим словом морфизма р: 0 01, 1 — 10, поскольку ип = //(0), и имеет вид (пробелы соответствуют представлению в виде морфического слова) / = 0 1 10 1001 10010110 1001011001101001 10010110011010010110100110010110... Пример 2. Пусть А = {а, Ь) и морфизм р определяется соотношениями (р: а — ab, b - а. Слово Фибоначчи определяется как/= qf{a). Рекуррентное определение имеет вид fo = a,f\ = ab, fn+2 =fn+\fn Последовательность длин слов/і образует числа Фибоначчи. Начальный отрезок слова Фибоначчи имеет вид /= abaababaabaababaababaabaababaabaab...

Автоматы

Автоматом над алфавитом А называется четверка А - (Q, Е, I, Т), где Q - множество состояний, Е с: Q х А х Q - множество переходов (ребер), I czQ- множество начальных состояний, Т czQ множество терминальных состояний. Для ребра е — {р, a, q) состояние р называется входом, состояние q - выходом, а символ а — меткой ребра. Траектория автомата А - последовательность ребер (р0, а\, р\), (pi, ъ Рг) •• , (Рп-\, сіп, Рп)- Меткой траектории называется слово х = х а\аг...ап. Траектория обозначается PQ— P„. Траектория называется правильной, если она начинается в / и заканчивается в Т. Множество слов называется распознаваемым автоматом А, если оно является множеством меток правильных траекторий.

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

Автомат называется однозначным, если для любй пары вершин (р, q), р, q є Е, и любого слова х є А существует не более х одной траектории р$- рп.

Автомат называется детерминированным, если для любых р є Q и а є А существует не более одного ребра, выходящего из вершины р и имеющего метку а. Очевидно, каждый детерминированный автомат является однозначным.

Для заданного автомата А и заданного алфавита Л множеством первых возвращений в q называется множество меток путей из q в q, не проходящих через q. Если автомат однозначный, множество первых возвращений является кодом. Если автомат детерминированный, множество первых возвращений является префиксным кодом.

Для автомата золотого сечения, изображенного на рисунке 1, множество первых возвращений в состояние 1 - префиксный код Х= {Ъ,аЪ}. Рис. 1. Автомат золотого сечения

Преобразователи отличаются от автоматов тем, что метками ребер являются не слова, а пары слов.

Преобразователем над моноидом называется А х 2? называется четверка A = (Q, Е, I, 7), где Q - множество состояний, Е с Q х А х В х Q - множество переходов (ребер), 1 с Q — множество начальных состояний, Т aQ- множество терминальных состояний. Для ребра е — (р, х, у, q) состояние р называется входом, состояние q - выходом, а символы ахи у- соответственно входной и выходной меткой ребра.

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

Графом де Брейна порядка п, п 1 [70, 106], называется помеченный граф, построенный следующим образом. Множество вершин - Ап, множество ребер - Е = {{be, a, sa) \ а, Ь є A, s є АпЛ). Слово х является меткой пути из и в v тогда и только тогда, когда v является суффиксом длины п слова их. Пример графа де Брейна приведен на рисунке. Рис. 2. Граф де Брейна порядка 2 Производящие ряды Производящим рядом множества X с І называется формальный ряд п 0 где ип = Card (ХпАп). Для чисел Фибоначчи F„, определяемых соотношениями F0 = F\ = 1, Fn+2 = Fn+i + Fm l-z-z «so fx = Y,F„+Xzn . »2:0 Формальные ряды

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

Формальным рядом с коэффициентами из кольца К с единицей и переменными из алфавита А называется отображение свободного моноида Л в К. Множество формальных рядов обозначается К(А).

Для ряда т є К(А) и слова w є А величина а на w обозначается т, w є К и называется коэффициентом w в а. Для множества X с: А характеристический ряд X обозначается X и определятся соотношениями Х\ х = \ при х є X, Х\ х = О при х ex. Сложение и умножение формальных рядов определяются как сг+ х, w = а, w + т, w тт, w = 2JUV = M, J, W T, W Эти операции превращают K(A) в кольцо с единицей. Формальные ряды, у которых ненулевыми является лишь конечное число коэффициентов, называются многочленами. Многочлены образуют подкольцо К А в кольце формальных рядов. Это подкольцо называется свободной (ассоциативной) АГ-алгеброй над А.

Для каждых сг є К(А) и т є К А по определению (сг,т) = Z» j, w r, w . Этим определяется билинейное отображение К(А) х К А в К.

Сумму можно обобщить на бесконечное число элементов со следующими ограничениями. Семейство (o;),«=/ рядов называется локально конечным, если для каждого w є А от нуля отличается лишь конечное число коэффициентов. Сумма рядов из локально конечного семейства, очевидно, также принадлежит локально конечному семейству. В частности, локально конечному семейству принадлежит (yv)weA , поэтому для любого а є К(А) j= cr,w w. Это позволяет перейти к стандартному we А обозначению формальных рядов с одной переменной a =}crna", где тп = 7, сГ . Пусть а - такой формальный ряд, что ( т, є) = 0. Семейство (о%ю - локально конечно, так как J\ W = 0 при / \w\ + 1. Это Дает ВОЗМОЖНОСТЬ ОПредеЛИТЬ НОВЫЙ РЯД (7 = + 7+( +... , который называется звездой ст. Утверждение 1 [191]. Пусть а є К(А) удовлетворяет условию (а; є) = 0. Ряд о - единственный ряд, для которого о ( - о) - (є-& )о = Є. В случае, если К имеет характеристику 0, верны следующие соотношения, связывающие операции в К(А) с операциями над подмножествами А . Утверждение 2 [191]. ДляX, Y =A а) пусть Z = X и Y; тогда Z = X + Y в том и только в том случае, когда X п Y = 0, б) пусть Z = XY; тогда Z = X Y в том и только в том случае, когда для любых xh х2 єX, yh у2 є Yиз Х\у\ = хуг следует xi= хъ У\ = Уь в) пусть X сА+\ тогда (X ) = X в том и только в том случае, если Х- код.

Алгоритмическая сложность задач реконструкции слов

Лемма о периодичности возникла в другой области математики: вначале она была доказана для вещественных функций. В рамках комбинаторики слов предложена ее интерпретация как оценки степени «совпадения» конечных последовательностей, имеющих общий период. Эта интерпретация является наиболее наглядной и естественной. Фундаментальный результат Маканина о разрешимости уравнений в свободных полугруппах непосредственно применим в комбинаторике слов, но в теории групп он был осознан как чисто теоретический, фактически как теорема существования. Практическое значение он получил именно в теории слов после того, как был предложен алгоритм решения уравнений в словах, принадлежащий классу PSPACE [219].

Верхняя граница длины к для полных V -множеств Е

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

Среди результатов, непосредственно связанных с темой данного исследования, следует выделить: - формулировку метрических задач в w-мерном булевском кубе [38] и задач восстановления слов по фрагментам, полученным с помощью фиксированных правил [36], - оценки спектров бинарных слов [37], - оценку максимальной длины цепи в булевом кубе и длины надпоследовательности для множества слов из заданного слоя булева кода [14, 15], - условия реализуемости матриц расстояний в единичных кубах [1], - методы покрытия множества слов цепями [47] и покрытия графов маршрутами [48], - методы описания слов, содержащих все подмножества как подслова [188, 259], и слов, содержащих наименьшее число различных подслов [130], - перечисление вполне монотонных семейств слов [211], - меры сложности подпоследовательностей [192], - методы восстановления объектов по минимальному числу слабо искаженных образцов [32]. Для решения задач анализа слов, в различной мере связанных с реконструкцией, применялись: - метрические методы в «-мерном кубе [38, 64], - методы автоматического анализа сложности слов [241], - различные подходы к упорядочению двоичных слов [109], - теория Шпернера в частично упорядоченных множествах [143], - конструкции кодов Грея [52], - методы анализа периодичности слов с помощью нейронных сетей [16]. Место задач реконструкции в комбинаторике слов Большинство перечисленных задач и подходов к их решению связано со структурным анализом слов и описанием их классов. Задаче синтеза слов по частичным представлениям, естественно возникающей в большинстве прикладных задач, уделялось значительно меньшее внимание, и существенных результатов в этом направлении значительно меньше. Сложность задач реконструкции отмечалась многими авторами [36, 89,196].

Возникает необходимость создания методов решения задач восстановления слов при более сложных видах частичной информации, чем подслова, и при отсутствии информации о точном расположении искажений или потерь информации. В диссертации рассмотрены задачи реконструкции слова из конечного алфавита в случае, когда а) задана совокупность правил, в соответствии с которыми образуются искаженные версии слова, б) имеется набор фрагментов, каждый из которых образован в соответствии с правилом из этой совокупности. Формальная постановка задачи реконструкции Пусть задано множество ЕР слов длины п. Предполагается, что зафиксировано некоторое множество V подпоследовательностей последовательности {1, 2, ... , «}. Для каждого слова а є ЕР рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством подпоследовательностей V = {v v ... v }. Каждую подпоследовательность из V можно считать каналом с искажениями. Подпоследовательность V є V задана характеристическим набором (/i vr2 ... v „) таким, что v, = 1, если і-й символ слова входит во фрагмент, полученный с помощью V, и v, = 0 в противном случае.

Вторая модель реконструкции в случае многозначного алфавита

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

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

В первой модели получены уточнения границы величины к: Во второй модели получена точная оценка длины к фрагментов, при которой обеспечена однозначность восстановления произвольного слова длины п\ Частные случаи V-множеств и их применения Получены оценки необходимого и достаточного числа фрагментов для реконструкции при (п - к) « п. Эти оценки использованы для построения алгоритмов коррекция ошибок для многих приемников. Для случая коротких фрагментов и ограниченного набора возможных слов А, \А\= q, исследована задача о минимальной мощности F-множества, обеспечивающего корректное распознавание слов из этого набора. Доказано, что мощность минимального множества - (q - 1). Доказательство основано на представлении слов элементами ультраметрического пространства. Задача о построении минимального множества сведена к построению остовного дерева в графе определенного вида.

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

Для реализации восстановления по фрагментам, соответствующим известным окнам, применяется вариант нейронной сети с обучением на основе проецирования на выпуклые множества. Разработанные в диссертации методы представления слов с помощью F-множеств достаточно простого вида использованы в усовершенствовании методов в двух прикладных областях анализа изображений - стеганографии и математической морфологии. В стеганографии фрагментирование используется для разбиения изображения на блоки, несущие скрытую информацию, обеспечивающего улучшенные соотношения между вносимыми искажениями и объемом передаваемой информации. В математической морфологии фрагменты описывают структурирующие элементы. Для оптимизации отбора фрагментов используются генетические алгоритмы и разложения по базису с помощью нейронной сети Хэмминга. Предложены также обобщенные варианты морфологических нейронных сетей [90, 91, 229, 230] и нейронных сетей на основе алгебр Клиффорда [94] для практической реализации предложенных вариантов математической морфологии и распознавания на основе инвариантов. Нейронные сети в неархимедовых числовых полях использованы для анализа информативности Р-множеств. Диссертация состоит из Введения и четырех глав. По теме диссертации опубликовано 17 работ (4 работы - в соавторстве). Результаты, изложенные в работе, докладывались на пяти российских и международных конференциях. Перейдем к более подробному изложению содержания диссертации. В главе I рассмотрены общие задачи реконструкции слов по фрагментарной информации и изучена их связь с другими задачами комбинаторики слов. Определены две основные модели реконструкции слов: по мультимножествам и по множествам. Изучены алгоритмическая сложность задачи реконструкции, связи между правилами образования фрагментов и классами, на которые при этом разбивается совокупность слов, а также зависимость классов от алфавита. В 1 определены общие задачи комбинаторики слов и изучена их связь с задачами реконструкции слов. Приведена содержательная постановка задачи реконструкции как представления слов в виде совокупностей более простых слов. В 2 приведена формальная постановка задачи реконструкции слов по фрагментам. Определены две модели реконструкции слов -с учетом кратности вхождения фрагментов в слово (I модель) и без учета этой кратности (II модель). В 3 изучена алгоритмическая сложность задач о существовании и единственности реконструируемого слова.

Двумерная -реконструкция и математическая морфология

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

Конечные и бесконечные слова, автоматы, неизбежные множества, производящие ряды, а также применение комбинаторики слов в символьном анализе динамических систем; связь между минимальностью и равномерной рекуррентностью; энтропия ([95, 142, 185, 186, 190, 191, 232, 233]).

Мономиальные алгебры; их представления; базисы алгебр; проблема роста в словах и алгебрах; равномерно рекуррентные слова; правильные слова и алгебры Ли; редукция к автоматному и конечно порожденному случаю; формальные языки и вопросы бернсайдовского типа (5, 66,134, 189,225,226, 227).

Слова, не содержащие определенных подслов; наборы слов, включающие подслова любого бесконечного слова (неизбежные наборы); иерархия таких слов и наборов; языки образов ([22, 100, ПО, 124,129,159,235]). Теория сложности слов и слова Штурма (последовательности Бетти) как образец слов с минимальной сложностью; морфизмы, сохраняющие слова Штурма; связь этих слов с разложением иррациональных чисел в непрерывные дроби ([86, 98, 99, 104, 140,141,237,238]). Слова, у которых начальный отрезок совпадает с конечным (би-идеальные последовательности), их связь с рекуррентностью и теорема Ширшова ([67, 77, 78, 133, 134, 225]). Слова из упорядоченного алфавита и число невозрастающих подслов; плактичный моноид и его связь с квантовыми группами; функции Шура, тензорное произведение и физика элементарных частиц ([167, 174, 179, 180, 189]). Теория кодирования; ожоды и представления кодовых слов как произведений слов меньшей длины (теорема о дефекте) ([34, 107, 116,126,138,195,242]). Нумерация; позиционные системы счисления, в том числе для комплексных чисел; выполнение арифметических операций с помощью конечных автоматов; / -разложения; числа Фибоначчи ([101, 108, 153,163,215]). Локальная и глобальная периодичность конечных и бесконечных слов; периодичность дробного порядка; золотое сечение как экстремальный случай периодичности; критерии периодичности; квазипериодичность и ее распознавание с помощью автоматов ([176, 184, 204,205, 223, 262]). Некоммутативные ряды и многочлены; централизаторы; алгоритм деления Евклида в некоммутативном случае ([9, 33, 66, 227]). Преобразования слов и -исчисление ([119, 135, 148, 149, 150, 154]). Статистика перестановок и слов ([119, 120, 135, 136, 137, 148, 149]). Теорема Маканина о разрешимости уравнений в словах ([42, 43, 139,214,219]). Независимые системы уравнений и понятие размерности множества слов ([116, 164,165, 173]). Распознавание образов и прогнозирование ([18, 19, 21, 35, 53, 88, 166]). Работа с естественным языком и анализ текстов; интеллектуальный анализ данных и извлечение знаний ([96, 118, 162,166,217,218,266]). Фракталы и черепицы ([92, 170,236,257, 258]). Биоинформатика; анализ последовательностей протеинов; геном; молекулярные вычисления; ДНК-компьютеры ([82, 199, 206, 213, 231]). Новые результаты в комбинаторике слов, как правило, приводят к расширению круга применений ее методов. В качестве примеров направлений в теоретической информатике, которые можно в некотором смысле считать разделами комбинаторики слов, можно привести молекулярные вычисления и генетические алгоритмы. Методы комбинаторного анализа применяются в синтезе ДНК-кодов [199]. Позиционные системы счисления тесно связаны с нейросетевыми вычислениями в полях /7-адических чисел Qp [8, 9, 26] и полиадических чисел Е [51, 221], представленных в виде локально компактных абелевых групп [72]. Примеры применения р-адических чисел и полиадических чисел в распознавании образов для построения поверхностей, разделяющих выборки, приведены в [46]. Исследования, проведенные в данной работе, связаны с изучением структуры слов и их представлением как совокупностей более простых слов. Эти исследования тесно связаны с задачами кодирования, конечными автоматами, символьным анализом динамических систем, распознаванием и анализом последовательностей протеинов. Основное внимание уделено задачам, связанным с восстановлением слова по его подпоследовательностям разных видов, то есть восстановлением целого по частям (объекта по неполной информации). Примеры задач реконструкции по частям: восстановление функции по ее значениям в некоторых точках; восстановление группы по подгруппам; распознавание образов; декодирование; принятие решений по результатам частичных наблюдений, обрывочной информации, информации с утечкой и т. п. Часто трудно определить, насколько важна отсутствующая информация и можно ли ее восстановить по имеющимся данным. Классическим примером трудной задачи такого рода является гипотеза Улама [63, 65]: пусть для некоторого графа G - (V, U), V = {vh ... , v„) известна совокупность подграфов G \ v„ і = 1, ... , п; по этой совокупности граф G восстанавливается однозначно. Для общего случая произвольных графов гипотеза Улама не доказана и не опровергнута; этот факт является свидетельством того, что для графов уже простейшие случаи потери информации могут оказаться весьма трудными для анализа. Внесение некоторых упорядочивающих графы ограничений существенно облегчает задачу: для деревьев, например, гипотеза Улама доказана [69].