Метрики (525947)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Метрические пространства: определенияПусть 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 | имеет к метрике Хемминга?.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги