Введение 3
1. Метрика и ультраметрика 5
2. Расстояние между строками 8
2.1. Расстояние Хэмминга 8
2.2. Расстояние Левенштейна 8
3. Понятие p-адического расстояния 12
4. Описание работы проекта 13
5. Эксперименты 20
5.1. Исследование степени метричности расстояния Хэмминга 20
5.2. Исследование степени ультраметричности расстояния Хэмминга 26
5.3. Исследование степени метричности редакционного расстояния 33
5.4. Исследование степени ультраметричности редакционного расстояния 39
5.5. Исследование корреляции между расстоянием Хэмминга и
редакционным расстоянием 46
5.6. Исследование степени метричности и ультраметричности радического расстояния 49
Заключение 52
Список использованной литературы 54
Приложение 55
В математике часто рассматриваются множества, между элементами («точками») которых определено расстояние (метрика). Такие множества называют метрическими пространствами, если выполнены соответствующие аксиомы. Существует много разных способов определить расстояние в различных множествах.
Существует также ультраметрические пространства и ультраметрика. Ультраметрическое пространство — особый случай метрического пространства, в котором метрика удовлетворяет усиленному неравенству треугольника:
d(x, у) < max{d(x, z), d(z, у)}
Ультраметрики используются при изучении алгоритмов агломеративной иерархической кластеризации, филогенетических деревьев, радических чисел, определенных физических систем и т. д. [4]
Ультраметрики и ультраметрические пространства также используются в различных задачах современной физики, вычислительной биологии, анализа данных и других областях науки. Основными и наиболее изученными примерами ультраметричных пространств являются радические пространства.
Интересен вопрос о том, в какой степени ультраметрично то или иное метрическое пространство.
Целью данной работы является:
• Вычисление коэффициента корреляции между расстояниями Хэмминга и редакционным расстоянием для строк одинаковой
длины
• Статистическое оценивание коэффициента метричности и
ультраметричности для расстояния Хэмминга
• Статистическое оценивание коэффициента метричности и
ультраметричности для редакционного расстояния
• Исследование свойств расстояний на d-мерных целочисленных строках
В ходе данной работы в полном объеме были достигнуты поставленные цели:
• Вычислены коэффициента корреляции между расстояниями Хэмминга и редакционным расстоянием для строк одинаковой длины
• Проведено статистическое оценивание коэффициента метричности и ультраметричности для расстояния Хэмминга
• Проведено статистическое оценивание коэффициента метричности и ультраметричности для редакционного расстояния
• Проведено исследование свойств расстояний на d-мерных целочисленных строках
По результатам проведенных экспериментов можно сделать следующие выводы:
• коэффициент метричности для расстояний Хэмминга и редакционного расстояния убывает с ростом длины строки и асимптотически стремится к константе, близкой к 0.5, которая зависит от параметра m - размера алфавита, при этом стандартное отклонение убывает с ростом длины строки;
• коэффициент ультраметричности для расстояний Хэмминга и редакционного расстояния растет с ростом длины строки и асимптотически стремится к константе, близкой к 1, которая зависит от параметра m - размера алфавита, при этом стандартное отклонение убывает с ростом длины строки;
• коэффициент корреляции между расстоянием Хэмминга и редакционным расстоянием растет с увеличением размера алфавита.
• расстояние на целочисленных строках, вычисленное по формуле
при значениях d = *-ур =J |£f=i(*i -У;)21р = 2, для p = 2, p = 3 удовлетворяет ультраметрическому неравенству.
• расстояние на целочисленных строках, вычисленное по формуле
x-yp = Jstik-yilp2
удовлетворяет неравенству треугольника, но не удовлетворяет ультраметрическому неравенству. .
