Скачиваний:
88
Добавлен:
04.03.2014
Размер:
344.24 Кб
Скачать

Метрические пространства: определения

Пусть 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