--PAGE_BREAK--4.1. Рис. 5.1.
Если будут нумероваться не только буквы алфавита, но и все образованные слова в каком-то порядке, считая в этом случае и буквы как однобуквенные слова, то Q=N. Номер очередного слова может определяться в соответствии с лексикографическим порядком (см. §1.2, п. 2). Очевидно, что в этом случае будем иметь соответствие g(q)=u, где uнекоторое слово из множества слов V, и однозначную нумерацию.
Такого рода процедуру называют иногдаарифметизацией. Введенные какие-либо достаточно простые отображения fили gпозволяют перевести отношения и операции, определенные на словах, в отношения и операции на номерах. Требование «достаточной простоты» отображения сводятся к тому, чтобы некоторые основные отношения (такие, как отношение вхождения одного слова в другое, – например, вхождение слова «уда», – приспособление для ужения, – в слово на|уда|чу, и т. п.) и операции (такие, как операции соединения слов и т. п.) переходили в отношения и операции, имеющие простую алгоритмическую природу (см. дополнительно §3.3).
2. Линейные (векторные) и нормированные (банаховы) пространства в контексте теории дискретных структур представляют наибольший интерес.
Векторное (линейное) пространствонад полем F– аддитивно записанная абелева группа V, в которой определено умножение на скаляр, то есть отображение F´V®V:(l,x)®lx, удовлетворяющее следующим аксиомам (x, yÎV; l, m, 1ÎF):
1) l(x+y) = lx+ly,
2) (l+m)x = lx+mx,
3) (lm)x = l(mx),
4) 1×x = x
Элементы векторного пространства называются точками этого пространства либо векторами, а элементы поля F– скалярами.
Векторное пространство Vесть частный случай модуля над кольцом, а именно, Vесть унитарный модуль (модуль с единицей) над полем. Унитарный модуль над некоммутативным телом также называют векторным пространством над телом.
Аксиомы (4.48) отражают аддитивность и однородность линейного пространства.
Пример5.5.К числу линейных пространств относятся:
1. Множество вещественных чисел Rс обычно определенными операциями сложения и умножения.
2. Множество всех упорядоченных n-к вещественных чисел, если операции сложения и умножения на число определены следующим образом.
Если x=(x1, …, xn), y=( y1, …, yn), то x+y=(x1+y1, …, xn+yn);
при x, yÎR.
3. Пространство функций .Если для любых f(x), g(x)Î под f(x)+g(x) понимается сумма значений fи g, взятые при одних и тех же значениях x. То под lf(x) нужно понимать новую функцию, полученную из f(x) умножением всех ее значений на l. Нулевой функцией будет f(x)=0 на всем отрезке [a,b].
Линейное пространство получает законченное описание тогда, когда свойства аддитивности и однородности дополнены возможностью измерения величин самих элементов (векторов). Введение к понятию линейного нормированного пространства (банахова пространства), если для каждого xÎXсуществует неотрицательное число , называемое нормой x. Норма должна удовлетворять следующим условиям:
1) =0 тогда и только тогда, когда x=0;
2) ;
3) – неравенство треугольника.
В этом случае величина обладает всеми свойствами меры (x, y). Действительно:
1) =0, если x-y=0, то есть x=y;
2) =;
3) учитывая, что y-x=-(x-y), находим .
Следовательно, линейное нормированное пространство является метрическим пространством с метрикой
(5.3).
Все рассмотренные ранее метрические пространства дополненные свойствами аддитивности и однородности, превращаются в нормированные линейные пространства. Для этих пространств обычно используют специальные обозначения.
Пример 5.6.
1. Пространство или с нормой при n=1 ;
2. Пространство с нормой ;
3. Пространство с нормой ;
4. Пространство непрерывных функций f(t), определенных на промежутке [a,b], с нормой .
3. Дискретные пространства и пространства близости. Тривиальное замыкание, определенное ранее, удовлетворяет всем пяти условиям (см. §5.1, п. 2) и, следовательно, является топологией. Эта топология называется дискретной. Все подмножества множества Xбудут в этой топологии и замкнутыми, и открытыми. Всякое множество может рассматриваться как дискретное топологическое пространство, причем в конечных множествах, где всякое подмножество является объединением конечного числа элементов, возможна лишь дискретная топология.
Пример 5.7.
1. Если семейство U
совпадает с множеством B(X) всех подмножеств X(см. §1.1, п.3), то имеет место дискретная топология.
2. Дискретная топология индуцируется тривиальной метрикой (см. Пример 5.3):
.
В этом случае имеем дискретное топологическое пространство (X, ).
Пример 5.8.
1. Если U={Æ,X} – крайний случай совокупности U, – то такое семейство определяет топологию на любом множестве X. Такая топология называется антидискретной.
2. Простым примером не дискретного топологического пространства служит прямая линия. Рассматривая ее как числовую прямую и определяя для каждого подмножества A, замыкание как совокупность чисел, являющихся пределами сходящихся последовательностей чисел из A, – получаем топологию, называемую естественно топологией. Одной из полных систем окрестностей здесь служит система всех (открытых) интервалов.
Пространство близости– множество Xс бинарным отношением dна множестве всех его подмножеств, удовлетворяющее следующим аксиомам:
1) AdBравносильно BdA(симметричность);
2) Ad(BÈC) равносильно AdBили AdC(аддитивность);
3) AdAравносильно A¹Æ(рефлексивность).
Отношение dопределяет близостную структуру, или просто близость на X. При этом, если AdB, то Aи Bназываются близкими множествами, а если (означает отрицание d), – то далекими.
Свойства близости пространства являются обобщением равномерных свойств метрического пространства аналогично тому, как в топологическом пространстве обобщаются его непрерывные свойства.
Понятие близостного пространства представляется полезным в решении проблем метризации путем равномерных покрытий множеств.
Покрытиемданного топологического пространства называется любая конечная совокупность его открытых множеств, дающих в своей сумме все это пространство. К числу важных покрытий, тесно связанных с покрытием Лебега размерности, относится e
-покрытиеотличительной особенностью которого является то, что все его элементы имеют диаметр
Лебега размерностьи является той размерностью, которая определяется путем покрытий.
Взаимно однозначное отображение fмножества Xна множество Yназывается близостным изоморфизмом относительно близостей на множествах Xи Y. Соответственно, если fблизостно непрерывно относительно и обратное отображение f–1
близостно непрерывно относительно . Близостный изоморфизм есть гомоморфизм индуцированных топологических пространств.
Два пространства близости (X, d) и (Y, ) близостно изоморфны, если существует близостный изоморфизм (X, d) и (Y,). Изучение близостных инвариантов является содержанием теории пространства близости. Каждый топологический инвариант является близостным инвариантом.
Пример 5.9.Каждая метрика порождает близость dна множестве X. Два множества A, BÌXблизки относительно dв том и только в том случае, если (A, B)=0. Следовательно, если – произвольная метрика на множестве Xи положим AdBтогда и только тогда, когда (A, B)=0, то тем самым определяется близость dна множестве X. Близость dназывается близостью индуцированной метрики .
4. Метрика Хемминга– имеет своим истоком проблемы кодирование теории информационных процессов. Основой данной метрики является метрика нормированных множеств булевой алгебры (см. п. 5, примера 5.3).
При формировании метрики Хемминга рассматривается векторное пространство над конечным полем характеристики 2–F2, то есть двоичные векторы, как частично упорядоченный набор нулей и единиц (см., например §2.2, п. 8).
Метрикой (расстоянием)Хемминга dмежду двумя векторами (словами, кодами и т. п.) является число мест, в которых символы двоичных векторов не совпадают.
Пример 5.10.Пусть из всего множества возможных векторов, состоящих из n=8 символов 0 и 1, выбраны векторы-коды слов: ai, ajи ak. Получим расстояние между ними в соответствие с приведенным определением:
ai=
||0 1 1 0 1 0 1 1 ||
aj=
||1 0 1 0 0 1 1 0 ||
|ai-aj|
* * * * *
d(ai-aj)=5
ak=
||0 1 1 0 1 0 1 0||
|ai-ak|
*
d(ai-ak)=1
|aj-ak|
* * * *
d(aj-ak)=4.
Нетрудно проверить, что метрика Хемминга удовлетворяет всем аксиомам расстояния:
1) d(ai,aj)³0 и d(ai,aj)=0, тогда и только тогда, когда ai=aj;
2) d(ai,aj)+d(aj,ak)³d(ai,ak) (в приведенном примере 5+4>1; заметим также d(ai,aj)+d(ai,ak)³d(aj,ak) – (5+1>4) и d(ai,ak)+d(aj,ak)=d(ai,aj) – 1+4=5);
3) d(ai,aj)= d(aj,ai).
В отдельных случаях может представлять интерес так называемое приведенное расстояние Хемминга – представляющее собой отношение расстояния dkn– размерности пространства.
Пример 5.10.а.Для кодовых слов ai, ajи akиз примера 5.10 относительное расстояние d1будет (ai,aj)==0,625, (ai,ak)=0,125 и (aj,ak)=0,5.
продолжение
--PAGE_BREAK--
5. Примеры метризации.Метрика Хемминга может быть использована в различных задачах. Так в теории систем существует проблема оценки близости подпространства A, BÌXпри оценке качеств систем одного и того же назначения. В исходной постановке эту проблему иллюстрирует пример 5.11.
Пример 5.11. Пусть имеется несколько систем A1,…,A,…,Am(), каждая из которых обладает своим набором полезных свойств из некоторого полезного набора качеств системы. Строго говоря, полезный набор, чаще всего, определить трудно.
Здесь возможны следующие варианты:
1. Состав свойств xj() одинаков. Проблема выбора отсутствует.
2. Различное число свойств при одинаковой их «значимости». Естественно, выбирается та система (×), которая имеет большее количество полезных свойств .
При наличии нескольких одинаковых по количеству свойств систем – сокращается число систем, принимаемых во внимание.
3. Количество свойств в наборах одинаково, но их составы различны. Здесь может быть полезным использование метрики Хемминга. Так, применяя, например, таблицу «системы – свойства» (см. таблицу 5.1)решение можно получить на основе логической близости по расстоянию Хемминга между мажорантой функцией по составу свойств рассматриваемых систем и булевыми функциями свойств этих систем.
В таблице 5.1 учитываются лишь четыре системы A1,A2,A3,A4(). При этом каждая из систем обладает четырьмя из n=8 возможных свойств.
Таблица 5.1.
Свойства
Системы
X1
x2
x3
x4
x5
x6
x7
x8
×××
A1
1
1
1
1
A2
1
1
1
1
A3
1
1
1
1
A4
1
1
1
1
1
1
1
*
*
*
*
*
*
*
*
*
*
Здесь «1» – наличие, «0» – отсутствие свойства.
Определение расстояния Хемминга векторами пространства свойств систем A1,A2,A3и A4и функцией показывает, что лучшим приближением к набору наиболее «проявленных» свойств является система A3.
В теории дискретных структур используется иногда понятие обобщенная метрика Хемминга. Смысл обобщения состоит в распространении оценки расстояния и на нечеткие множества. Последнее означает (см §4.3, п.1) введение вместо дискретной функции принадлежности m(x)={0,1} («не принадлежит» рассматриваемому множеству –0, «принадлежит» – 1) функции принадлежности m(x), определенной на множестве рациональных чисел, обычно на отрезке m(x)=[0,1].
С формальной стороны такое «обобщение» переводит метрику Хемминга в общеизвестную форму линейной метрики (см. пример 5.3, п.2). В самом деле,
(5.4),
подобна (x, y) в п. 2 примера 5.3.
Представляется, что тонкость состоит в том, что фактически вводится в метрику некоторая функция-множитель – в данном случае характеристическая функция принадлежности m(x) при этом часто неявно полагают все xij={1} (как, кстати, и сделано в примере 5.11, в таблице 5.1 – свойства xj() в общем существуют, но уровень их не определен и в данном случае, не учитывается).
Такой подход открывает широкий спектр «обобщений» путем введения разнообразных функций-множителей.
Так, например, в теории эффективности систем распространено применение весовой функции, оценивающей «значимость» отдельный свойств (координат векторного пространства) в общем, показатель совершенства системы.
Отметим отличие весовой функции от характеристической. Значения весовой функции g(x), где xÎX, взаимосвязаны соотношением:
(5.5).
Здесь Cнекоторая величина, зависящая от выбора множества значений функции g(x).
Так, значениями g(x) могут быть ранги элементов. В простейшем случае это натуральные числа номеров мест в соответствие со значимостью xjÎXj=1, 2,…, n=|X|. Тогда .
Чаще всего используют приведенные значения функции g(x)
,
определенные на полуинтервале (0,1].
Функция принадлежности m(xj) для каждого элемента xjÎXограничена лишь тем множеством М, на котором она определена.
Обычно М задают на отрезке [0,1]. Если суммировать принадлежности элементов xиз множества мощности |C|=n, то сумма будет лежать в пределах
(5.6).
При этом верхнее значение имеет место, когда все mj=1, а нижнее при всех mj=0, ().
Кроме того, алгебры весовых и характеристических функций различны. Первых – алгебра множеств рациональных чисел, а алгебра характеристических функций – одна из модификаций булевой алгебры (см. §2.3).
Если задать некоторую функцию f, например, предельную или среднюю , в пространстве X, со значениями соответственно или , то близость систем по своим свойствам к функции будут отражать метрики:
(5.7)
(5.8).
Нетрудно видеть, что здесь весовая функция взята в виде набора постоянных коэффициентов, «взвешивающих» те или иные свойства системы в независимости от уровня этих свойств. При таких условиях на различие метрик d1основное влияние оказывают значения m(x) и x. Однако при метриках d2на их различие влияют все составляющие m(x), xи g.
В следующем примере 5.11.а дана детальная иллюстрация оценки близости в рассматриваемом пространстве Xсоответствующих множеств (систем) по набору их свойств на основе введения различных по структуре метрик.
Пример 5.11.а. Используя в качестве исходных данных пример 5.11, получим сравнительные оценки близости множеств A1,A2,A3и A4.
С этой целью зададимся значениями показателя принадлежности mдля всех возможных характеристик систем (табл. 5.2). При этом, там, где в табл. 5.1 показатель принадлежности равен 1, в табл. 5.2 назначим m(x)>0,5, в противоположном случае примем m(x)£0,5. В нижней строке табл. 5.2 приведены показатели для формирования мажорирующих функций. Здесь значения m(x) определялось по схеме.
||mij|| Таблица 5.2
xj
Ai
x1
x2
x3
x4
x5
x6
x7
x8
A1
0,6
0,8
0,7
0,6
0,5
0,3
0,2
0,1
A2
0,1
0,2
1,0
0,9
0,9
0,3
0,7
0,4
A3
0,6
0,4
0,7
0,2
0,5
0,8
0,9
0,4
A4
0,6
0,4
0,3
0,2
0,4
0,8
0,9
1,0
0,475
0,450
0,675
0,475
0,575
0,550
0,675
0,475
1
1
1
1
||xij|| Таблица 5.3
xj
Ai
x1
x2
x3
x4
x5
x6
x7
x8
A1
0,9
0,8
0,6
0,6
0,2
0,1
0,1
0,2
A2
0,2
0,1
0,6
0,7
0,8
0,1
0,9
0,1
A3
0,2
0,2
0,3
0,1
0,1
0,9
0,8
0,6
A4
0,6
0,2
0,1
0,1
0,2
0,6
0,6
0,2
0,20
0,08
0,15
0,10
0,05
0,25
0,12
0,05
.
Такой подход связан с тем, что ближайшими числами к 1, являются числа большие 0,5, а к 0 – меньшие 0,5.
Число 0,5 приравнивается к 0 из тех соображений, что булева мажоранта (см. пример 5.11) ровна нулю, если одинаково число единиц и нулей в множестве ее переменных.
Таблица 5.4, в которой в метрику введены только весовые коэффициенты, а показатели принадлежности точно такие же, какие использованы в таблице 5.1, показывает существование влияния весовых коэффициентов на близость к соответствующим функциям сравнения. При этом следует отметить совпадение оценки в предыдущем разделе примера по мажоранте и средней функции в данной части (вновь наибольшей близостью отличается система A3).
Таблица 5.4
Свойства
Системы
x1
x2
x3
x4
x5
x6
x7
x8
при из
табл. 5.1
из табл. 5.3
и все xij={1}.
A1
A2
A3
A4
20
8
15
10
15
10
5
12
20
15
25
12
20
25
12
5
– мажоранта при
20
15
12
,
8
10
12
,
20
10
5
,
25
,
15
25
5
– средняя при
15
2
11,25
5
1,25
12,5
9
1,25
,
5
6
3,75
5
1,25
12,5
9
1,25
,
15
2
3,75
5
3,75
12,5
3
1,25
,
5
2
3,75
5
1,25
12,5
3
1,25
,
5
2
11,25
5
1,25
12,5
3
3,75
Таблицы 5.5 и 5.6 рассчитаны при введении в метрику и весовых коэффициентов и уровней характеристик систем, соответственно при целочисленных значениях xпоказателей принадлежности и достаточно произвольной выборки на отрезке [0,1]. В последнем случае оговорка «достаточно» связана с тем, что набор показателей принадлежности ограничивался близостью к установленным их значениям в табл. 5.1, в остальном же, осуществлялся произвольно.
Данные в табл. 5.5 и 5.6 показывают существенное влияние вводимых характеристик на близость к функциям и , соответствующих метрик.
Таблица 5.5
Свойства
Системы
x1
x2
x3
x4
x5
X6
x7
X8
при из
табл. 5.1
и из табл. 5.3
A1
A2
A3
A4
180
64
90
60
90
70
40
108
40
45
225
96
120
15
72
10
– мажоранта при
180
90
108
,
64
60
108
,
180
70
40
,
140
45
225
12
,
60
90
150
36
10
– средняя при
85
16
56,25
32,5
10
93,75
69
2,5
,
95
48
33,75
27,5
10
93,75
69
2,5
,
85
16
33,75
37,5
30
93,75
39
2,5
,
45
16
11,25
32,5
10
131,25
27
2,5
,
35
16
56,25
32,5
10
56,25
3
7,5
продолжение
--PAGE_BREAK--