02 семестр / Книги и методические указания / Методичка по информатике для ИУ-8 / Метрики
.pdfМетрические пространства: определения
Пусть X некоторое множество
и ρ : X × X 7→R действительнозначная функция.
Определение
Пара (X , ρ) называется метрическим пространством, а функция ρ метрикой на X , если для всех a, b, c X выполняются свойства:
Метрические пространства: определения
Пусть X некоторое множество
и ρ : X × X 7→R действительнозначная функция.
Определение
Пара (X , ρ) называется метрическим пространством, а функция ρ метрикой на X , если для всех a, b, c X выполняются свойства:
1 Симметричность: ρ(a, b) = ρ(b, a);
Метрические пространства: определения
Пусть X некоторое множество
и ρ : X × X 7→R действительнозначная функция.
Определение
Пара (X , ρ) называется метрическим пространством, а функция ρ метрикой на X , если для всех a, b, c X выполняются свойства:
1 Симметричность: ρ(a, b) = ρ(b, a);
2 Неотрицательность: ρ(a, b) > 0 и ρ(a, b) = 0 a = b;
Метрические пространства: определения
Пусть X некоторое множество
и ρ : X × X 7→R действительнозначная функция.
Определение
Пара (X , ρ) называется метрическим пространством, а функция ρ метрикой на X , если для всех a, b, c X выполняются свойства:
1 Симметричность: ρ(a, b) = ρ(b, a);
2 Неотрицательность: ρ(a, b) > 0 и ρ(a, b) = 0 a = b;
3 Неравенство треугольника: ρ(a, b) + ρ(b, c) > ρ(a, c).
Метрические пространства: определения
Пусть X некоторое множество
и ρ : X × X 7→R действительнозначная функция.
Определение
Пара (X , ρ) называется метрическим пространством, а функция ρ метрикой на X , если для всех a, b, c X выполняются свойства:
1 Симметричность: ρ(a, b) = ρ(b, a);
2 Неотрицательность: ρ(a, b) > 0 и ρ(a, b) = 0 a = b;
3 Неравенство треугольника: ρ(a, b) + ρ(b, c) > ρ(a, c).
Определение
В метрическом пространстве (X , ρ) определены множества: Br (a) = {b X : ρ(a, b) 6 r} шар радиуса r с центром a. Sr (a) = {b X : ρ(a, b) = r} сфера радиуса r с центром a.
Метрические пространства: примеры
1 Плоскость R2 = {x = (x1, x2) : xi R} с евклидовым расстоянием
p
ρ(a, b) = (a1 − b1)2 + (a2 − b2)2.
2 Плоскость R2 с метрикой манхэттэнского типа d(a, b) = |a1 − b1| + |a2 − b2|.
3 Плоскость R2 с метрикой
ρ(a, b) = max(|a1 − b1|, |a2 − b2|).
4 Произвольное множество U с метрикой
ρ(a, b) = |
0, a = b. |
|
1, a 6= b |
5Множество 2U = {X : X U} всевозможных подмножеств конечного множества U с метрикой ρ(X , Y ) = |X 4 Y |.
Основное метрическое пространство этого семестра
Обозначим Fq поле из q элементов, Fnq множество векторов длины n с разрядами из Fq.
Определение |
|
|
|
˜ |
n |
˜ |
, . . . , βn). |
Пусть α,˜ β |
Fq, α˜ = (α1, . . . , αn), |
β = (β1 |
|
|
˜ |
|
˜ |
Расстоянием Хемминга d(α,˜ β) между наборами α,˜ β |
|||
|
|
|
˜ |
называется число разрядов, в которых различаются α˜ и β. |
|||
|
|
˜ |
˜ |
При простом q расстоянием Ли ρ(α,˜ β) между наборами α,˜ β |
|||
называется величина |
|
|
|
|
n |
|
|
|
Xi |
|
|
|
˜ |
|αi − βi |. |
|
|
ρ(α,˜ β) = |
||
|
=1 |
|
|
Упражнение
Доказать, что (Fnq, d) и (Fnq, ρ) метрические пространства.
Вес и номер набора
Определение
Наборы, различающиеся в единственном разряде, называются соседними, а во всех разрядах противоположными.
Пусть α˜ = (α1, . . . , αn) произвольный набор из Fnq. Тогда величина kα˜k, равная числу ненулевых координат в наборе α˜, называется его весом.
Величина |
|
α˜ |
|
= |
n |
α |
qn |
|
i называется номером |
|
| |
| |
Pi=1 |
− |
|||||||
набора α˜. |
|
|
i |
|
|
Пример
q = 2: k1001k = 2, |1001| = 9.
q = 3: k102k = 2, |102| = 1 · 32 + 0 · 31 + 2 · 30 = 11. Наборы 100, 101 F32 соседние,
а наборы 100, 011 противоположные.
Простейшие факты
В случае q = 2 расстояния по Хеммингу и по Ли совпадают: d = ρ, но вообще говоря это не так.
Например, при q = 3: |
|
|
|
d(101, 221) = 2, |
|
|
|
ρ(101, 221) = |1 − 2| + |0 − 2| + |1 − 1| = 3. |
|
||
˜ |
˜ |
для всех α,˜ |
˜ |
Легко видеть, что d(α,˜ β) 6 |
ρ(α,˜ β) |
β. |
Дальше под расстоянием между наборами, если не указано иное, будем понимать расстояние Хемминга.
α˜ = (α1, . . . , αn) Fnq
r
G
Br (α˜) = Sr (α˜)
i=0
Простейшие факты
В случае q = 2 расстояния по Хеммингу и по Ли совпадают: d = ρ, но вообще говоря это не так.
Например, при q = 3: |
|
|
|
d(101, 221) = 2, |
|
|
|
ρ(101, 221) = |1 − 2| + |0 − 2| + |1 − 1| = 3. |
|
||
˜ |
˜ |
для всех α,˜ |
˜ |
Легко видеть, что d(α,˜ β) 6 |
ρ(α,˜ β) |
β. |
Дальше под расстоянием между наборами, если не указано иное, будем понимать расстояние Хемминга.
α˜ = (α1, . . . , αn) Fnq
r
G
Br (α˜) = Sr (α˜)
i=0
|Sr (α˜)| = Crn(q − 1)r