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

• Автор: Хошманд Асл Мохаммад Реза
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 67 с. : ил.

1 Введение

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

1.2 Различимость слов

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

2.1 Подслова, окрестности, классы эквивалентности

2.2 Описания классов эквивалентности в терминах логического

перманента

2.2.1 Классы эквивалентности

2.2.2 Классы эквивалентности ¥<к(х)

2.3 Серийное описание классов эквивалентности

2.3.1 Характеризация < 2 -эквивалентности

2.4 Восстановление слова по подсловам длины > [|] 4- 1
3 Различимость слов
3.1 Различающие слова, тестовые множество, тесты
3.2 Свойства и оценки функции Ь(х, у)
3.3 Алгоритм построения минимального теста

3.3.1 Простейший алгоритм
3.3.2 Префикс-функция, ассоциированная с образцом
3.3.3 Алгоритм Кнута - Морриса - Пратта
3.3.4 Алгоритмы нахождения t(х, у)
Литература

Глз.вЭ/ 1 Введение
1.1 Реконструкция по подсловам
Часть и целое всегда является предметом изучения науки. Основной философский вопрос при таком изучении звучит так: как устроен мир? Если при исследовании информацию принят следующий тезис:
Всякая информация может быть представлена словом в конечном алфавите, то часть проблем, связанных с понятием информация может быть сформулировано в виде изучения слова и его частей. Что понимать под частью слова зависит от контекста изучаемой проблемы и точные постановки задач могут варьироваться в достаточно широких пределах? В целом такого роде задачи имеют глубокие связи с алгеброй, топологией, теорией чисел,теорией информации и математической генетикой.
Основным объектом изучения в диссертации являются слова конечной длины над бинарным алфавитом {0,1}. Это множество обозначается через

Отсюда: <(ж, у) = 2, %, ж) = 3, «°(ж, у) = 2.
Отметим теперь следующее простое и универсальное утверждение.
Утверждение. Справедливы оценки
1 < t(х, у) < п х,у е Вп Обе границы в этом неравенстве являются достижимыми, т.к.
г(0п, 1п) = 1, г((01)"/2, (10)"/2) = п
Величине Ь°(х,у) служит мерой близости слов ж,у Е Вп. Некоторым подтверждением этого обстоятельства является следующий параграф.
3.2 Свойства и оценки функции £ (ж, у)
Рассмотрим функцию д(х,у),заданную на декартовом произведении Вп х Вп
д(х,у) = п - £°(ж,у)
Лемма 3.2.1. Функция й(х,у) является псевдометрикой.
Доказательство. В проверке нуждается лишь выполнение неравенства треугольника для с?(ж, у)
<1{х,г) + <1(г,у)><1(х,у) (3.1)
или, учитывая определение д(х, у)
*0(ж, г) + А (г, у) <п + 4°(ж, у)