Смежный вектор дискретная математика

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (Аксиомы булевой алгебры). Названия операций пока не введены.

1. X & Y = Y&X, X V Y = Y V X – коммутативность.

2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4. Поглощение – X & X = X, X V X = X.

5. Свойства констант

X & I = X, где I – аналог универсального множества.

6. Инвальтивность (X*)* = X

7. Дополнимость X V X* = I, X & X* = 0.

8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, Множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.

Oбъединение эквивалентно V, пересечение — &, дополнение — *, пустое множество – 0, а универсальное – I.

Все аксиомы булевой алгебры справедливы в операциях над множествами.

Видео:Графы, вершины, ребра, инцидентность, смежностьСкачать

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

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

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

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

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

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

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

100101₂ =1×2 5 +1×2 2 +1×2 0 =32₁₀ +4₁₀ +1₁₀ =35₁₀.

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

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

Определение.Расстоянием Хемминга 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 (`a n ,`b n ) = 1), называют соседними.

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

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

Лексикографическим называют такой порядок векторов`b n , когда соответствующие им двоичные числа расположены по возрастанию от 0 до 2 n – 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 . Сопоставим множеству всех 2 n векторов`b n следующую древовидную структуру, начинающуюся
в корневой вершине О (вершине нулевого уровня). Из нее выходят вниз два отрезка (ребра), соответствующие значениям b<sub>1</sub>=0(влево) и b<sub>1</sub>=1(вправо) и оканчивающиеся вершинами первого уровня. Из них выходят вниз по два ребра, соответствующие b<sub>2</sub>=0(влево) и b<sub>2</sub>=1(вправо) и оканчивающиеся новыми вершинами — второго уровня и т. д. Процесс завершается построением всех вершин n-го уровня. Данная структура называется
бинарным деревом и обозначается Т n . На рис. 4.1 показано
дерево Т 3 для 3-мерного булевого вектора`b 3 =(х, у, z).

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

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

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

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

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

Вопросы для проверки знаний.

1. Есть ли принципиальное различие правил выполнения сложения и вычитания в десятичной системе счисления и других системах с постоянными основаниями?

2. Какой формат компьютерного представления чисел называют беззнаковым целым числом?

3. Какой формат компьютерного представления чисел называют целым числом со знаком?

4. Какой способ компьютерного представления целых чисел называют прямым кодом?

5. Какой способ компьютерного представления целых чисел называют дополнительным кодом?

6. Для каких целых чисел прямой код совпадает с дополнительным кодом?

7. Может ли целое число занимать в электронной памяти а) 4 бита, б) 6 бит, в) 8 бит, г) 10 бит?

8. По каким правилам осуществляется перевод беззнаковых байтовых целых чисел из прямого кода в дополнительный и обратно?

9. По каким правилам осуществляется перевод байтовых целых чисел со знаком из прямого кода в дополнительный и обратно?

10. В каких случаях вычитание байтовых беззнаковых целых чисел дает результат в прямом коде, а в каких – в дополнительном?

11. Что называют двоичным (булевым) n-мерным вектором?

12. Какую операцию называют инвертированием булевого вектора?

13. Какие числа называют порядковыми номерами булевых векторов?

14. Что называют лексикографическим порядком двоичных векторов?

Видео:ПРОСТОЙ СПОСОБ, как запомнить Векторы за 10 минут! (вы будете в шоке)Скачать

Лекция 1_02: Наборы из нулей и единиц

В этой лекции мы рассматриваем элементы множества B k — наборы фиксированной длины из нулей и единиц. Такие наборы можно трактовать по-разному, часто полезно сопоставлять эти трактовки и быстро в случае надобности переходить от одной к другой.

Вершина куба.

Характеристический вектор множества.

Набор булевых значений.

Двоичное представление целого числа.

Состояние памяти компьютера.

Путь в целочисленной решетке.

Результаты случайных испытаний (например, бросаний монеты).

И другие, более сложные.

Видео:Вектор. Сложение и вычитание. 9 класс | МатематикаСкачать

Вершина куба

Начнем с того, что набор из k нулей и единиц можно трактовать как вершину k –мерного единичного куба, у которого одна из вершин находится в начале координат, а исходящие из нее ребра лежат на координатных осях.

Такой куб легко представить себе для k , равного 1, 2 и 3, а для больших размерностей все «выглядит аналогично». Попробуйте!

Вот интересное использование этой трактовки 0-1-наборов.

Изобразим 5-мерный куб, в котором проведены только ребра, необходимые для минимальной связи между вершинами.

Так устроено соединение процессоров во многопроцессорных компьютерах. В них обычно вершин-процессоров больше, типично k=16 . Но все, что нужно, мы увидим здесь.

Каждый процессор кодируется набором из пяти 0-1 символов. Процессор, в коде которого последний символ 1, связывается с процессором, у которого код отличается только в последнем символе — там стоит 0. Например, процессор 10111 прицепляется к 10110. Процессор, код которого оканчивается на 10, прицепляется к процессору с кодом, отличающимся во втором с конца символе: так что 10110 связывается с 10100. И т. д.

Это близкие соединения. По ним соединяются любые два процессора.

Видео:Урок 3. Произведение векторов и загадочный угол между векторами. Высшая математика | TutorOnlineСкачать

Упражнение

Постройте в 10-мерном кубе путь от процессора 0110100110 к процессору 0111110011 .

Видео:18+ Математика без Ху!ни. Скалярное произведение векторов. Угол между векторами.Скачать

Набор булевых значений

Что такое булевы значения?

Английский математик Джордж Буль (1815-1864) в 1854 году предложил систему исчисления логических высказываний, введя новый тип логических величин, принимающих два значения — ИСТИНА и ЛОЖЬ ( True и False ). Для этих (булевых) величин были введены своеобразные операции, вполне естественные с точки зрения формальной логики.

Сейчас булевы величины широко используются в программировании (тип Boolean ). Мы сейчас рассмотрим булевы величины, операции с ними и их связь с 0-1 значениями.

Булевы значения и операции

Начнем с примеров булевых значений.

“π > 3.1415926” — это ИСТИНА ,

“π > 4.0005926” — это ЛОЖЬ ,

“x > y+3” — это ИСТИНА или ЛОЖЬ , в зависимости от значений x и y .

Операция отрицание , она же НЕТ или NOT или Ø ( ! в языке программирования Си) имеет один логический операнд (она одноместная ) и вырабатывает противоположное ему значение:

Ø (π > 3.1415926) = False

Операция конъюнкция

Эта операция называется еще логическим умножением или логическим И и обозначается AND ,
а также Ù или & .

У нее два булевских операнда и результат операции также булевское значение «оба операнда истинны» . Например, (x > 3) Ù (x истинно для всех x , которые больше 3 и меньше 7.

Операция дизъюнкция

Эта операция называется еще логическим сложением или логическим ИЛИ и обозначается OR , а также Ú или || .

У нее два булевских операнда и результат операции также булевское значение «хотя бы один из операндов истинен» . Например, (x > 7) Ú (x истинно для всех x , которые больше 7, и всех, которые меньше 3.

Операция эквиваленция

Часто эту операцию называют эквивалентностью . Ее обозначают EQU или º .

У нее два булевских операнда и результат операции также булевское значение «значения операндов одинаковы» . Например,
(x > 7) º (x > 3) истинно для всех x , которые больше 7, и всех, которые меньше 3.

Операция «исключающее ИЛИ»

Эта операция обозначается XOR (от e X clusive OR ), она общепринятого обозначения не имеет, хотя в одной очень авторитетной системе я видел подчеркнутый знак Ú : Ú .

У этой операции два булевских операнда, и ее результат также булевское значение: «значения операндов не совпадают» .

(x > 3) XOR (x истинно для всех x , которые меньше 3, и для всех, которые больше 7.

Эта операция имеет удобное свойство

которое используется в компьютерной графике (например, для изображения быстро перемещаемого знака).

Операция импликация

Редко используемая операция «следования» обозначается IMP (от IMP lication ), или É .

У нее два булевских операнда и результат операции также булевское значение «либо ложен первый операнд, либо истинен второй» .

(x истинно для всех x , которые больше 3 и меньше 7.

Таблица логических операций

x y	x Ù y x Ú y x º y x Ú y x É y
F F F T T F T T	F F T F T F T F T F F T F T T T T T F T

0-1 представление булевых значений

Естественна трактовка единицы и нуля как логических значений, соответственно, как True и False .

Все логические операции легко переписать для этого представления. Но и 0-1 набор можно представлять как набор логических значений и все перечисленные логические операции выполнять над наборами-операндами покомпонентно .

Пример логических операций над 0-1 наборами

x y	0000000 11111111 000 1111 000 11111
x Ù y x Ú y x º y x Ú y x É y	0000000000 11111 000 111111111111 111 0000000 11111 000 1111111 00000 1111111 000 11111

Логические функции

Комбинируя значения отдельных компонент логического набора в более сложных операциях, можно составлять более сложные функции от логических аргументов.

Функция от логических значений, принимающая логические значения, называется логической функцией .

Заметим, что каждая логическая функция может быть задана таблицей истинности — перечислением тех наборов аргументов, которым соответствует значение True . Используя эту таблицу, всегда можно представить логическую функцию в виде дизъюнкции конъюнкций:

где T — таблица истинности. Каждый входящий в нее набор a определяет для каждой переменной x_i способ ее вхождения в дизъюнкцию, соответствующую a : входит в нее сама переменная или ее отрицание. Эта зависимость спрятана в функции a . Такая функция называется дизъюнктивной нормальной формой , или сокращенно ДНФ

Интересна задача сокращения записи ДНФ до минимума.

Видео:Что такое вектора? | Сущность Линейной Алгебры, глава 1Скачать

Характеристический вектор множества

Если сопоставить элементы конечного множества S мощности k позициям в наборе из k нулей и единиц, то подмножествам можно сопоставить такие наборы.

Пусть для простоты S = 1:9 . Подмножеству A = соответствует набор 110001101 . Такой 0-1 набор c _A называется характеристическим вектором множества S .

Операции над множествами легко моделируются логическими операциями над их характеристическими векторами. Например,

(Греческая буква c называется хи . Если вы не помните наизусть греческих букв, то можете воспользоваться нашим справочником.)

Видео:✓ Что такое вектор? Чем отличается понятие "вектор" от понятия "направленный отрезок" | Борис ТрушинСкачать

Двоичное представление числа

Вы, конечно, знаете, что каждое натуральное число однозначно представимо в виде суммы степеней 2, причем каждая степень в этой сумме появляется не больше одного раза, т. е. с коэффициентом 0 или 1. Эти коэффициенты составляют представление числа в двоичной системе счисления .

Например, 83 = 64+16+2+1 = 1010011.

Таким образом, каждый набор из k нулей и единиц соответствует какому-либо числу в диапазоне от 0 до 2 k −1 .

Из нахождения двоичного представления не нужно устраивать великого мероприятия. Нужно просто записать нужное число, а рядом остаток от его деления на два. Затем под числом записать частное от этого деления и повторять этот процесс пока частное не будет равно нулю. Остатки от деления, прочитанные снизу вверх, и дадут искомое представление. Вот так:

Итак 37965₁₀ = 1001010001001101₂ .

Степени двойки

Степени двойки из-за использования двоичной системы встречаются так часто, что некоторые из них полезно помнить наизусть.

Число 2 10 — это наша тысяча. Оно обозначается K и называется кило , (ср. килобайт).

2 20 = 1 048 576 — это миллион ( мега, M ). Дальше следуют гига, G, и тера, T , найдите их значения сами.

А когда найдете, можете сравнить со значениями в нашем справочнике

Арифметические действия с двоичными числами

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

Как прибавить единицу к числу 10001110100011111 ?

Ответ: двигаясь от конца к началу, заменять единицы на нули, а встретив нуль, заменить его на единицу и остановиться.

В рассматриваемом случае получится 10001110100 100000 . Красным выделена изменившаяся часть.

Разработано много эффективных схем сложения, вычитания, умножения и деления двоичных чисел. Мы ими заниматься не будем.

Но нужно упомянуть об особом случае умножения и деления двоичного числа на степень двойки 2 k . Умножение выполняется приписыванием к записи числа k нулей. В компьютере это соответствует сдвигу записи числа на k позиций влево. Существуют машинные команды сдвига.

Мы говорим влево , считая, что число записано в компьютере так, как мы привыкли писать на бумаге — младшие разряды правее левых. В некоторых случаях полезно считать, что запись идет в противоположном направлении. К этому вопросу мы еще вернемся.

А про команды сдвига нужно поговорить еще.

Ясно, что сдвиге влево старшие разряды теряются (а при делении — сдвиг происходит вправо , и теряются младшие разряды). Существуют команды циклического сдвига, в которых вытесняемые разряды занимают освобождающиеся места с другого конца записи. Например, циклический сдвиг на три разряда влево выглядит так (показаны номера разрядов)

12345678 ® 45678 123 .

Как написать программу циклического сдвига элементов массива, не использующую большой дополнительной памяти (порядка длины массива)? Вот неожиданное решение:

procedure mirror(l,r: integer);
begin
while l

Здесь используется простенькая процедура swap , меняющая местами два значения. С ее помощью пишется процедура mirror , переворачивающая часть массива. используя эту процедуру, мы весь массив перевернули, а потом отдельно перевернули начало и конец.

Более удобные системы счисления

Двоичная система счисления удобна для компьютера, но неудобна для человека — слишком длинные получаются записи чисел:

Даже длину такой записи трудно определить!

Компромиссом между интересами человека и машины являются системы счисления с основаниями, близкими к 10, но являющимися степенью двойки — 8 и 16.

В восьмеричной системе , совершенно естественно, 8 цифр — 0, 1, 2, 3, 4, 5, 6, 7. Каждому разряду восьмиричной системы соответствуют 3 разряда двоичной системы, и переход от одной системы к другой очень прост:

0 — 000 2 — 010 4 — 100 6 — 110
1 — 001 3 — 011 5 — 101 7 — 111

Число из предыдущего абзаца в этой системе записывается так:

Итак, 25613532. Восьмеричная запись сейчас используется относительно редко.

Шестнадцатеричная система , напротив, очень популярна.
В ней 16 цифр. Десять обычных — 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Еще шесть — это буквы A, B, C, D, E, F.
Каждому разряду соответствуют 4 разряда двоичной системы:

0 — 0000 4 — 0100 8 — 1000 C — 1100
1 — 0001 5 — 0101 9 — 1001 D — 1101
2 — 0010 6 — 0110 A — 1010 E — 1110
3 — 0011 7 — 0111 B — 1011 F — 1111
Число из примера в этой системе записывается так:

Итак, 57175A.

Особенно широко используется 16-ричная запись при обсуждении вопросов памяти компьютера.

Память компьютера

Вся память компьютера состоит из мельчайших магнитных элементов, каждый из которых может находиться в одном из двух состояний. Одно из них отождествляется с нулем, а другое с единицей. Машина может «прочесть» состояние магнита, а, значит, и хранимую им двоичную цифру. Такая цифра называется битом (bit).

Так как этих цифр очень много, то с ними невозможно работать без укрупнения. Первое укрупнение — это объединение битов в восьмерки — байты (byte). Байт — минимальная адресуемая единица памяти. Это значит, что машинная команда, работающая с памятью может добраться только до всего байта целиком или до еще более крупной единицы памяти. Выделять в байте отдельные биты нужно специальными дополнительными действиями.

Пара подряд идущих байтов называется машинным словом (word). Слово располагается так, чтобы минимальный из адресов байтов был четным (это называется выравниванием — слово выравнивается на четный адрес).

Один из байтов старший, а другой младший.

Где расположен младший байт? В разных компьютерах по-разному. Если впереди, то говорят, что компьютер мелкоконечный ( Little-Endian — этот термин ввел Джонатан Свифт в «Путешествии Гулливера»). Если сзади, то компьютер крупноконечный ( Big-Endian ).

Наши персональные компьютеры — мелкоконечные, и когда вы находите в памяти целое число, занимающее два байта, например, 515 = 0203₁₆ , то в первом байте пишется 03 , а во втором — 02 .

Побайтовое кодирование символов

Важным событием в развитии информатики (Computer Science) и вычислительной техники было принятие байта в качестве единицы при кодировании символов. Вначале такие коды были приняты фирмой IBM при разработке знаменитого комплекса IBM-360, а сейчас превратились в общемировой стандарт.

В Советском Союзе внедрением машин Единой Серии (ЕС), клонировавших IBM-360, байты появились «автоматически». Было очень удобно, что в 256 = 2 8 кодовых возможностей свободно умещаются и прописные и строчные буквы и латиницы и кириллицы.

Стандарты кодирования. Стандарт ASCII

Сейчас самым важным стандартом (их несколько) является ASCII .

Это аббревиатура для A merican S tandard C ode for I nformation I nterchange .

Он стал мировым стандартом кодировки для практически всех компьютеров. В этом коде на каждый символ приходится по одному байту, причем стандарт фиксирует верхнюю половину таблицы с кодами от 0 до 127 . Представив байт двумя 16-ричными цифрами, мы можем сказать, что это коды от 00 до 7F . Некоторые сведения об этой таблице хорошо запомнить.

Первые две строчки заполнены служебными символами (типа возврата каретки, перевода строки, табуляции, звонка, конца передачи).

Следующая строка начинается с 20 — кода пробела. Дальше идут различные специальные знаки, которые можно не помнить.

Дальше идет строка цифр: от 30 для 0 до 39 для 9. Остаток заполнен спецзнаками. Строки 4 и 5 заполнены прописными латинскими буквами: 40 для @ ( at «коммерческое» , а совсем не собака ), 41 для A и т.д. вплоть до 5A для Z .

Строки 6 и 7 аналогично заполнены строчными латинскими буквами. 60 используется для ` (обратного апострофа).

Почти полную таблицу (без объяснения части служебных кодов) можно найти, например, в нашем справочнике.

Вторая половина таблицы ASCII существует в нескольких вариантах (они называются codepages — кодовые страницы). Для нас наиболее важны следующие страницы 437 — MS DOS Extended 1252 — Windows 866 — DOS Cyrillic 1251 — Win Cyrillic
Две последние таблицы также есть в нашем справочнике.

Стандат UNICODE

Сейчас идет активный перевод программного обеспечения на двухбайтовую систему кодировки. Принят международный стандарт, именуемый UNICODE. Этот стандарт имеет «кодовое пространство» в 2 16 = 65536 символов, чего вполне достаточно для всех языков мира, включая полный набор китайских иероглифов (сейчас в китайских компьютерных системах используется сокращенный набор в примерно 5000 знаков).

Для более удобного перехода ASCII ® UNICODE разработана специальная кодировка UTF-8 (Unicode Transport Format), о которой, как и об Уникоде, лучше рассказать отдельно.

Видео:Новое задание профиля №2. Все, что нужно знать о векторах | Аня МатеманяСкачать

Картинка

Двухцветную (скажем, черно-белую) картинку можно свести к некоторому «растру» — прямоугольной решетке и затем рассматривать ее как подмножество черныъ точек в множестве всех точек этой решетки. А для задания множества можно построить его характеристический вектор («вытянув» предварительно решетку в линию, т.е. линейно пронумеровав точки решетки, нумеровать элементы прямого произведения двух множеств мы уже умеем).

Например, следуя художнику Малевичу, нарисуем «черный квадрат» 6 ´ 6 на поле 8 ´ 8 . Вот этот «Черный квадрат» и ниже его представление в одну строку. Конечно, вместо белых квадратиков нужно писать нули, а вместо черных — единицы.

Есть и более экономные представления картинок.

00000000 01111110 01111110 01111110 01111110 01111110 01111110 00000000

Видео:Высшая математика. Линейные пространства. Векторы. БазисСкачать

Передача по двоичному каналу связи

В технике связи передачу по каналу связи очень часто рассматривают как последовательность импульсов, находящихся на двух уровнях ( сигнал и нет сигнала ), и в этом смысле сигнал называют двоичным. Информация, передаваемая по такому каналу связи, рассматривается как 0-1 последовательность.

Смысл нулей и единиц в этой последовательности может быть очень разнообразным и хитрым. (это могут быть сжатые тексты и изображения, компьютерные программы, запись звука, шифрограммы). Некоторые варианты мы в дальнейшем рассмотрим Но чаще всего — это тексты, о байтовом представлении которых уже говорилось.

Видео:Почему сумма всех чисел равна - 1/12. ОбъяснениеСкачать

Результаты случайных испытаний

В теории вероятностей принято рассматривать случайные последовательности. Для примера их считают результатами бросания монеты: при падении монета может упасть на разные стороны, которые традиционно называются Гербом и Решеткой (Решкой). Вот и получается

ГГГ РР Г Р ГГ РРРР Г Р Г Р ГГГ Р Г

— те же нули и единицы.

Видео:Все типы 2 задание векторы ЕГЭ по математике профиль 2024Скачать

Путь в целочисленной решетке

0-1 набор иногда полезно представлять путем на прямоугольной решетке, таким путем, в котором возможны шаги только вправо или вверх.

Вот путь для набора

11 0 111 000 1 00 11 .

По разности координат начала и конца легко судить о числе нулей и единиц в наборе.

Видео:7.5 ЧАСОВ МАТАНА!!! ПОДАРОК ВСЕМ СТУДЕНТАМ ДЛЯ ПОДГОТОВКИ К ЗАЧЁТАМ И ЭКЗАМЕНАМ ОТ ЁЖИКА В МАТАНЕ!!!Скачать

Штрихкоды

Нули и единицы, несущие информацию, могут иногда представляться очень своеобразно. Например, вы уже встречались, вероятно, с полосками на упаковках товаров. Они называются штрихкодами (barcodes) и предназначены для быстрого считывания информации специальными устройствами. На фотографии С. Е. Столяра вы видите, как кассир в магазине специальным сканнером «считывает» штрихкод с упаковки.

Сейчас есть очень много вариантов штрихкодов, специально приспособленных для тех или иных ситуаций. Рассмотрим только некоторые из них.

Почтовики используют специальные коды для сортировки писем.

Можно сравнить американские и английские коды

Кодировка почты США позволяет кодировать цифры. Такой код называется «2 из 5» (интересно, почему?).

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

Видео:ВЫЧИТАНИЕ ВЕКТОРОВ ЧАСТЬ I #егэ #огэ #математика #геометрия #профильныйегэСкачать

Представление чисел с плавающей точкой

Мы рассмотрели только самые простые представления 0-1 наборов. Во многих ситуациях набор делится на части, или поля, каждое из которых трактуется по-своему. Вот важный пример такого рода.

Числа с плавающей точкой представляются в компьютере приблизительно. Сейчас широко распространен стандарт IEEE, в котором фиксированы две формы числа — 32-битовая и 64-битовая. Мы рассмотрим только первую из них. Итак, число занимает двойное слово, и составляющие его 32 бита b₁,…,b₃₂ разбиты на три поля (это для нас ново: 0-1 набор разбивается на поля, и только это разбиение нам сейчас важно):

s = b₁ — знак числа,
e = b_2:9 — порядок числа,
f = b_10:32 — дробная часть нормализованной мантиссы,

Видео:Разложение вектора по базису. 9 класс.Скачать

Перебор 0-1 наборов

Сейчас мы ответим на три вопроса:

1. Сколько элементов в множестве |B k | ?
2. Как эти элементы перенумеровать ?
3. Как эти элементы перебрать ?

Ответы на первые два вопроса мы уже дали раньше: |B k | = 2 k , и каждый набор можно рассматривать как двоичное представление целого числа, которое и является его номером.

Например, #(0101) = 5.

Как же эти элементы перебрать ?

Очень просто: начать с нулевого набора, которому соответствует число 0 , а далее прибавлять о единице (работая прямо с двоичным набором, мы это уже умеем).

Однако в некоторых случаях такая форма перебора неудобна из-за того, что при переходе от одного набора к другому текущий набор сильно изменяется.

Вопрос: нельзя ли осуществить перебор так, чтобы при каждом переходе изменение было только в одном бите.

Ответ: это возможно.

Мы покажем эту возможность дважды:

Как математики и как программисты.

В первой колонке запишем в половине строк нули, а дальше единицы. Заполним первую половину наборами длины k-1 , а затем зеркально отобразим эти наборы во второй половине. При этом наборы любой меньшей длины будем перебирать так же. В таблице показано заполнение еще до зеркального отражения. А теперь то, что получается

Как программисты:

Запишем перебор наборов по возрастанию и с единичными «мутациями»:

Видите? Там, где в правой таблице меняется значение бита, в левой появляется 1. (докажите!)

Значит, нужно иметь два рабочих 0-1 набора. В первом моделировать прибавление 1, а во втором, зная позицию изменения, менять значение бита.

Эта последовательность наборов называется кодом Грея, по имени американского инженера, который запатентовал такие коды. Они используются при проектировании датчиков угла поворота.

Видео:Зачем нужен ВЕКТОР. Объяснение смыслаСкачать

Упражнения

Переведите в двоичную систему числа 34567, 11438, 16 777 351.

Переведите в 8-ричную и 16-ричную систему число 10101011100010100101010110.

Выполните все логические операции с наборами 101010010101001010101010 и 000010111101011101011101.

Закодируйте в ASCII и переведите в двоичную систему текст Hello, Dolly!

Нарисуйте черно-белую растровую картинку 16 ´ 16 и закодируйте ее по строчкам и по столбцам.

Какой номер имеет набор 0001101110? Сколько наборов такого размера всего?

Постройте таблицу кодов Грея для k = 5 .

Видео:Разбираем стереометрию за 6 часов | ЕГЭ по математике | Эрик ЛегионСкачать

Дополнительная литература

Это действительно классический западный учебник по основным алгоритмам информатики. Книга дорогая, но очень полезная.

Книг по комбинаторике очень много, но по программистским вопросам только одна.

Она была издана издательством «Мир» в 1988 году тиражом 45000 экземпляров, так что иногда встречается.

В 2008 г. издательство «Вильямс» выпустило несколько тонких «тетрадок» примерно по 150 стр. Так началась долгожданная публикация четвертого тома книги Дональда Кнута «Искусство программирования».

Во втором выпуске рассказывается о переборах последовательностей из нулей и единиц (автор называет их кортежами) и о переборах перестановок, которыми мы будем заниматься на следующей лекции. Спешите обзаводиться!