Метрики (Методичка по информатике для ИУ-8)

Метрические пространства: определенияПусть 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.Метрические пространства: примеры12345Плоскость R2 = {x = (x1 , x2 ) : xi ∈ R}с евклидовымp расстояниемρ(a, b) = (a1 − b1 )2 + (a2 − b2 )2 .Плоскость R2 с метрикой манхэттэнского типаd(a, b) = |a1 − b1 | + |a2 − b2 |.Плоскость R2 с метрикойρ(a, b) = max(|a1 − b1 |, |a2 − b2 |).Произвольноемножество U с метрикой0, a = bρ(a, b) =.1, a 6= bМножество 2U = {X : X ⊆ U} всевозможных подмножествконечного множества U с метрикой ρ(X , Y ) = |X 4 Y |.Основное метрическое пространство этого семестраОбозначим Fq — поле из q элементов, Fnq — множествовекторов длины n с разрядами из Fq .ОпределениеПусть α̃, β̃ ∈ Fnq , α̃ = (α1 , .

. . , αn ), β̃ = (β1 , . . . , βn ).Расстоянием Хемминга d(α̃, β̃) между наборами α̃, β̃называется число разрядов, в которых различаются α̃ и β̃.При простом q расстоянием Ли ρ(α̃, β̃) между наборами α̃, β̃называется величинаρ(α̃, β̃) =nX|αi − βi |.i=1УпражнениеДоказать, что (Fnq , d) и (Fnq , ρ) — метрические пространства.Вес и номер набораОпределениеНаборы, различающиеся в единственном разряде,называются соседними, а во всех разрядах —противоположными.Пусть α̃ = (α1 , . . . , αn ) — произвольный набор из Fnq .Тогда величина kα̃k, равная числу ненулевых координат внаборе α̃, называется его весом.PВеличина |α̃| = ni=1 αi q n−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 ⇒rGBr (α̃) =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 ⇒rGBr (α̃) =Sr (α̃)i=0|Sr (α̃)| = C rn (q − 1)rПростейшие фактыВ случае q = 2 расстояния по Хеммингу и по Лисовпадают: d = ρ, но вообще говоря это не так.Например, при q = 3:d(101, 221) = 2,ρ(101, 221) = |1 − 2| + |0 − 2| + |1 − 1| = 3.Легко видеть, что d(α̃, β̃) 6 ρ(α̃, β̃) для всех α̃, β̃.Дальше под расстоянием между наборами, если не указаноиное, будем понимать расстояние Хемминга.α̃ = (α1 , . . . , αn ) ∈ Fnq ⇒rGBr (α̃) =Sr (α̃)i=0|Sr (α̃)| = C rn (q − 1)r|Br (α̃)| = 1 + C 1n (q − 1) + C 2n (q − 1)2 + .

. . + C rn (q − 1)r .Случай q = 2ОпределениеМножество Fn2 = {0, 1}n называется булевым кубомразмерности n.Множество {0, 1}nk = {α̃ ∈ Fn2 : kα̃k = k} называетсяk-м слоем булева куба.Множество всех наборов из {0, 1}n , у которыхфиксированы и одинаковы какие-то (n − k) разрядов, аостальные k разрядов произвольны, называется k-мернойгранью (подкубом) булева куба.Пример00010n 00110 o∗0∗10 =— грань размерности 2.1001010110Различные представления булева кубаКуб {0, 1}n — это:линейно упорядоченное множество относительнолексикографического порядка (возрастание номера);частично упорядоченное множество относительнооперации «6» покомпонентного сравнения наборов:если a = (a1 , .

. . , an ) и b = (b1 , . . . , bn ), тоa 6 b ⇐⇒ ∀ k : ak 6 bk ,например, 0100 6 0111, а наборы 010 и 101 несравнимы;линейное векторное (нормированное) пространство;конечное поле F2n ;регулярный двудольный граф: его вершинами являютсянаборы куба, рёбрами соединяются соседние в смыслерасстояния Хемминга вершины и только они.Индуктивное построение {0, 1}n−1 → {0, 1}n{0, 1}n−1{0, 1}n−1Индуктивное построение {0, 1}n−1 → {0, 1}nα̃1α̃1α̃kα̃kα̃2n−1α̃2n−1{0, 1}n−1{0, 1}n−1Индуктивное построение {0, 1}n−1 → {0, 1}n0α̃11α̃10α̃k1α̃k0α̃2n−11α̃2n−1{0, 1}n−1{0, 1}n−1Индуктивное построение {0, 1}n−1 → {0, 1}n0α̃11α̃10α̃k1α̃k0α̃2n−11α̃2n−1{0, 1}n−1{0, 1}n−1Индуктивное построение {0, 1}n−1 → {0, 1}n{0, 1}n0α̃11α̃10α̃k1α̃k0α̃2n−11α̃2n−1Булевы кубы малых размерностей111n=3011101110001010100n=2n=111101100000004-мерный куб11110111001101010110000100100100000010111101111010011010110010004-мерный куб11110111001101010110000100100100000010111101111010011010110010004-мерный куб111101110011010101100001001001001011110111101001101011001000сфераS1 (1001)00004-мерный куб111101110011010101100001001001001011110111101001101011001000шарB1 (1001)00004-мерный куб111101110011010101100001001001001011110111101001101011001000слой{0, 1}4200004-мерный куб111101110011010101100001001001001011110111101001101011001000грань∗10100004-мерный куб111101110011010101100001001001001011110111101001101011001000грань∗10∗00004-мерный куб111101110011010101100001001001001011110111101001101011001000грань∗1∗∗0000Куб {0, 1}5Куб {0, 1}6Куб {0, 1}7Домашнее задание12Доказать, что расстояние между двоичными векторамичётного веса чётно.Доказать, что если α̃, β̃ ∈ Fn2 , то ρ(α̃, β̃) = kα̃ ⊕ β̃k.3Слой наибольшей мощности среди всех слоёв булева кубаназывается средним слоем.

Доказать, чтопоследовательность |{0, 1}nk | при постоянном n иk = 0, 1 . . . n сначала возрастает, а затем убывает. Такжепоказать, что в кубе чётной размерности имеется всегоодин средний слой, а в кубе нечётной размерности — два.4Доказать, что каждый из пяти приведённых в текстепримеров метрических пространств действительноявляется таковым.

Какое отношение последний примерρ(X , Y ) = |X 4 Y | имеет к метрике Хемминга?.