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

• Автор: Сметанин, Юрий Геннадиевич
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 184 с.

Содержание
Введение

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

Глава I. Комбинаторика слов и задачи реконструкции 1. Основные направления исследований в комбинаторике слов и задачи синтеза слов 2. Формулировка задач реконструкции слов 3. Алгоритмическая сложность задач реконструкции слов

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

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

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

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

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

эквивалентности

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

3. Верхняя граница длины к для полных V множеств Еп
4. Нижняя граница длины к для полных V множеств Епк
5. Реконструкция по подсловам
Глава III. Вторая модель реконструкции
1. Алгебраическое описание классов
эквивалентности
2. Полнота Умножеств Епк
3. Реконструкция слов с малым числом серий
4. Вторая модель реконструкции в случае
многозначного алфавита
5. Распознавание по подсловам
Глава IV. реконструкция в кодировании и
распознавании образов
1. Реконструкция по длинным фрагментам
2. Распознавание по коротким фрагментам
3. Двумерная Греконструкция и математическая
морфология
4 Гмножества в стеганографии
5. Нейросетевые модели для реализации
алгоритмов реконструкции слов
6. Нахождение и устранение ложных решений в
нейронных сетях
7. Повышение емкости нейронных сетей с
безошибочным обучением
Литература


Разработанные в диссертации методы представления слов с помощью К-множеств достаточно простого вида использованы в усовершенствовании методов в двух прикладных областях анализа изображений - стеганографии и математической морфологии. В стеганографии фрагментирование используется для разбиения изображения на блоки, несущие скрытую информацию, обеспечивающего улучшенные соотношения между вносимыми искажениями и объемом передаваемой информации. В математической морфологии фрагменты описывают структурирующие элементы. Для оптимизации отбора фрагментов используются генетические алгоритмы и разложения по базису с помощью нейронной сети Хэмминга. Предложены также обобщенные варианты морфологических нейронных сетей [, , 9, 0] и нейронных сетей на основе алгебр Клиффорда [] для практической реализации предложенных вариантов математической морфологии и распознавания на основе инвариантов. Нейронные сети в неархимедовых числовых полях использованы для анализа информативности К-множеств. Диссертация состоит из Введения и четырех глав. По теме диссертации опубликовано работ (4 работы - в соавторстве). Результаты, изложенные в работе, докладывались на пяти российских и международных конференциях. Перейдем к более подробному изложению содержания диссертации. Определены две основные модели реконструкции слов: по мультимножествам и по множествам. Изучены алгоритмическая сложность задачи реконструкции, связи между правилами образования фрагментов и классами, на которые при этом разбивается совокупность слов, а также зависимость классов от алфавита. В § 1 определены общие задачи комбинаторики слов и изучена их связь с задачами реконструкции слов. Приведена содержательная постановка задачи реконструкции как представления слов в виде совокупностей более простых слов. В § 2 приведена формальная постановка задачи реконструкции слов по фрагментам. Определены две модели реконструкции слов -с учетом кратности вхождения фрагментов в слово (I модель) и без учета этой кратности (II модель). Алгоритмическая сложность задачи о существовании неизвестного слова а с заданным набором фрагментов {<а, у>}, у е V, описана следующим утверждением. У= {уь . I у<| = 3, / = 1, 2, . ЬУ У|> = Ьл, / = 1,. Эта задача А является ЫР-полной. Доказательство основано на сведении задачи «3-выполнимость». Доказано также следующее непосредственное следствие предыдущего утверждения. Ь е Еп, то проверка наличия другого вектора, для которого они также являются набором фрагментов, тоже является МР-полной. В § 4 изучена зависимость сложности задач реконструкции слов от алфавита. Доказано следующее утверждение: если множество V является полным на двоичном кубе Еп, то оно является полным и на любом г-значном кубе Еп{г), г = 3, 4, . Именно этим утверждением оправдан тот факт, что в работе изучаются в основном двоичные векторы. Аналогичное утверждение верно и для неполных классов. Это оказывается полезным в изучении мощности классов эквивалентности в произвольном конечном алфавите. В § 5 изучены сжимающие классы V, расширение которых приводит к сужению классов эквивалентности и, тем самым, к увеличению информации о реконструируемом слове. Доказано, что Р-множества Е„ и Е„к и ЕпкЛ и . Е? являются конгруэнтными, то есть порождают разбиения на одни и те же классы эквивалентности. В главе II изучена I модель. Предполагается, что зафиксировано некоторое множество V подпоследовательностей последовательности 1, 2, . V. Каждая подпоследовательность V є V задана характеристическим набором (VI у2 . V, = 1, если / є У, и V/ = 0 в противном случае. В § 1 описано сведение задачи реконструкции к решению определенной системы диофантовых уравнений. Эта система зависит от конкретного вида К-множества. Построение системы уравнений основано на использовании следующего равенства для числа вхождений слова а = (ща2 . ЕГ в х = (х х2 . Ьк = 2ак-. Доказана следующая теорема о сведении К-эквивалентности к решению диофантовых уравнений. Теорема. Слова а = (а . Ь = (Д . Я определяются кратностями вхождения фрагментов при заданном К-множестве. ЬгхІ2 +а2).