Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Двоичные (булевы) векторы



Двоичным (булевым) n-мерным вектором называют набор из n чисел (b1, b2, ..., bn), каждое из которых может принимать только значения в двоичной системе счисления – 0 или 1.

Двоичный вектор является обратным (инвертированным) к , если он образован из заменой всех нулей единицами, а единиц – нулями.

Например, если = (0,1,1,1,0,1), то = (1,0,0,0,1,0).

Если в записи двоичного вектора длины n устранить запятые, его можно рассматривать как двоичную запись некоторого целого числа. Наименьшим таким числом является 0. Ему соответствует вектор = (0, ...,0). Наибольшим является число 2n – 1, которому соответствует вектор = (1, ...,1). Следовательно, при помощи полного набора двоичных векторов длины n можно записать все 2n целых чисел из отрезка
[0,2n1]. Такие числа называют порядковыми номерамивекторов. Их используют как в двоичном виде, так и в десятичной системе счисления.

Пример 1.Найти порядковый номер булева вектора = (1,0,0,1,0,1) в десятичной системе счисления.

Решение. Устраняя запятые в векторе, получим двоичную запись 1001012. Переводя ее по правилу 2.1.1 в десятичную систему счисления, получим:

1001012 =1×25 +1×22 +1×20 =3210 +410 +110 =3510.

Ответ: десятичный порядковый номер заданного булева вектора равен 3510.

В качестве меры близости булевых векторов используют расстояние Хэмминга.

Определение.Расстоянием Хемминга r между булевыми векторами `a n и`b n называют величину r(`a n, `b n), которая равна числу координат, по которым различаются векторы `a n и`b n.

Пример 8. r(100011, 110011)=1, r(0101, 1010)=4.

Определение. Булевы векторы`a n и`b n , различающиеся ровно по одной координате ( r (`an,`b n) = 1), называют соседними.

Рассмотрим наиболее употребительные геометрические интерпретации булевых n – мерных векторов.

1. Представление в виде двоичных чисел. Если в записи вектора `bn устранить запятые, ее можно рассматривать как двоичную запись некоторого целого числа. Наименьшим таким числом является 0. Ему соответствует вектор `bn =(0, ..., 0). Наибольшим является число 2n1, которому соответствует`bn = (1, ..., 1). Следовательно, при помощи векторов `bn можно записать все 2n целых чисел из интервала [0, 2n – 1]. Такие числа будем называть порядковыми номерами векторов.

Лексикографическим называют такой порядок векторов`bn, когда соответствующие им двоичные числа расположены по возрастанию от 0 до 2n – 1.

В качестве примера рассмотрим полное множество 3-мерных двоичных векторов, расположенных в лексикографическом порядке:

0 (0, 0, 0), 4 (1, 0, 0),

1 (0, 0, 1), 5 (1, 0, 1),

2 (0, 1, 0), 6 (1, 1, 0),

3 (0, 1, 1), 7 (1, 1, 1).

2. Бинарное дерево Тn. Сопоставим множеству всех 2n векторов`bn следующую древовидную структуру, начинающуюся
в корневой вершине О (вершине нулевого уровня). Из нее выходят вниз два отрезка (ребра), соответствующие значениям b1=0(влево) и b1=1(вправо) и оканчивающиеся вершинами первого уровня. Из них выходят вниз по два ребра, соответствующие b2=0(влево) и b2=1(вправо) и оканчивающиеся новыми вершинамивторого уровня и т. д. Процесс завершается построением всех вершин n-го уровня. Данная структура называется
бинарным деревом и обозначается Тn. На рис. 4.1 показано
дерево Т3для 3-мерного булевого вектора`b3=(х, у, z).

Рис. 4.1. Бинарное дерево Т3

Пронумеруем слева направо все вершины n-го уровня от 0до
2n – 1. Каждому вектору `bn можно однозначно поставить
в соответствие путь из корневой вершины О в вершину n–го уровня с порядковым номером вектора `bn. Например, вектору (0,1,0)в рассмотренном примере соответствует путь из корневой вершины в вершину 2 (0102 = 210) по ребрам х = 0, у = 1, z = 0. Таким образом, бинарное дерево полностью описывает все 2n векторов`bn.

3. Единичный n-мерный куб Вn. Единичным n-мерным кубом называют полный набор вершин, соответствующих векторам`bn, в котором каждые две соседних вершины (которым соответствуют векторы, различающиеся ровно по одной координате) соединены отрезком (ребром). Обозначается единичный n-мерный куб как Вn. На рис. 4.2 показаны кубы В1, В2, а также плоские проекции кубов В3, В4.

Определение. Дана вершина`an в Вn. Множество вершин Вn {bn}, для которых r(an,`bn)= r, называют сферой радиуса r. Множество {gn} вершин Вn, для которых r(an,`gn r, называют шаром радиуса r.

Рис. 4.2. Единичные n-мерные кубы В1, В2 и плоские проекции кубов В3, В4




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.