ДВОИЧНОЕ КОДИРОВАНИЕ ИНФОРМАЦИИ

ДВОИЧНОЕ КОДИРОВАНИЕ ИНФОРМАЦИИ В компьютере для представления информации используется двоичное кодирование, так как удалось создать надежно работающие технические устройства, которые могут со стопроцентной

Как правило, компьютеры хранят действительные числа в Научной нотации , или Формат с плавающей запятой .Это означает, что вместо хранения двоичное число 1010.1101, как оно сейчас написано на экране, компьютер может представлять его внутренне как 0,10101101 * 2 ⁴ . Причины этот выбор формата станет ясным, когда мы рассмотрим различия между представлениями с фиксированной запятой и с плавающей запятой .

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

Пример:

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

000000000000000000000000000 грамм) на массу электрон (0.000000000000000000000000000

Теперь, когда мы увидели, почему формат с плавающей запятой намного более популярен. чем формат с фиксированной точкой, наша новая задача — найти систематический метод представления чисел с плавающей запятой в виде строк из единиц и нулей.

3.1.2 Представление с плавающей запятой номера

Числа с плавающей запятой представлены в виде m * r ^e , где м — это мантисса , r — это основание или с основанием , а e — это показатель степени .

Пример:

1.011011 ₂ * 2 ³ эквивалентно 1011.011 ₂
Мантисса равна 1,011011, система счисления равна 2, а показатель степени равен 3.

Система счисления r понимается как 2 и компьютеру не требуется чтобы сохранить его явно.

Существует много различных форматов чисел с плавающей запятой, и каждый из них из них могут иметь разный уровень точности. В зависимости от формата который используется, общий размер двоичной последовательности действительного числа и относительный размер различных полей в этой последовательности может быть различным. Например, как мы увидим позже в формате с плавающей запятой IEEE, экспонента может занимать 8 бит из 32 бит (25% от общего числа size), или 11 из 64 бит (17%), или 15 из 128 бит (12%).А Число с плавающей запятой не нужно хранить в одной ячейке памяти. Двоичная последовательность числа может быть разбита на несколько слов для достижения большая точность.

Число битов, выделенных показательной части и мантиссе часть номера полностью зависит от потребностей пользователя. Номер бит, выделенных для экспоненты, определит диапазон чисел что можно представить. Например, астрофизик сверху для работы с номерами от 2 * 10 ³³ до 9 * 10 ^-28 , диапазон из 10 ⁶¹ , что означает, что ему необходимо выделить достаточно бит для представления 61 различных значений показателя степени от -28 ₁₀ до +33 ₁₀ .

Количество битов, выделенных части мантиссы, будет определять максимальное количество значащих цифр, которое может быть сохранено, что, в свою очередь, определяет точность , которую может иметь число. Номер записанное как 3.14159 более точное, чем записанное число как 3.14. Пожалуйста, не путайте точность с точностью . Точность — это мера правильности, а точность — мера точности.Число записывается как 3,04159 является более точным, но менее точным, чем записанное число как 3.14 (обратите внимание на опечатку в 3. 0 4159).

• Нормализация чисел с плавающей запятой

Нормализация мантиссы : Есть два общепринятых способа нормализации мантисса. Один из них — всегда ограничивать мантиссу в диапазоне от 0,100 … 00 до 0,111 ….. 11. Если результат двоичной операции вида 1.xxx …. * 2 ^e , он будет нормализован до 0.1xxx … * 2 ^{e + 1} , и если результат имеет вид 0.01 ….. * 2 ^e это будет нормализовано до 0,1 ….. * 2 ^{e — 1} . Обратите внимание, что специальный исключение должно быть сделано для нуля, потому что оно не может быть нормализовано.

Другой приемлемый способ — ограничить мантиссы в диапазоне 1.000 … 00 до 1.111 … 11, так что число с плавающей запятой всегда выражается в форма 1.xxx ….. * 2 ^e .

Основным преимуществом нормализации мантиссы является повышение точности. 8-битная ненормализованная мантисса 0.00000011 имеет только 2 значащие цифры, в то время как 8-битная нормализованная мантисса 0,11010010 имеет 8 значащих цифр.

Смещение показателя степени : В реальной жизни мы имеем дело с обоими положительными и отрицательные мантиссы, а также с отрицательными и положительными показателями. Отрицательная мантисса обычно хранится в форме дополнения до двух, но экспоненты всегда хранятся в смещенных от. Помните, что n-бит экспонента позволяет представить 2 ⁿ возможных беззнаковых экспонент значения от 0 до 2 ⁿ — 1.Если вычесть постоянное значение ( смещение ) из 2 ^{n — 1} из каждого из этих значений без знака, мы получаем a ряд чисел от -2 ^{n — 1} до 2 ^n-1 -1, то есть представляются беззнаковыми числами от 0 до 2 ⁿ — 1 . Добавление константы к самому отрицательному члену, чтобы сделать его равным нулю, есть просто еще один способ представления отрицательных чисел.

Пример:

Если (в десятичной системе) мы имеем ряды -5, -4, -3, -2, -1,0,1,2,3,4 , мы можем добавить 5 к каждому из этих чисел, чтобы получить новую серию 0,1,2,3,4,5,6,7,8,9.Таким образом, мы можем использовать беззнаковые числа от 0 до 9 для представления чисел от -5 до +4, зная, что мы должны вычесть 5 из беззнакового ряда попасть в подписанный сериал.

E _s = E _t + B

Пример:

При n = 3, 2 ⁿ = 8, а смещение составляет 2 ^{n — 1} = 4. В этом случае
истинная экспонента колеблется от -4 до 3, и она будет сохранена
как смещенная экспонента от 0 до 7.

0,00010111 ₂ нормализовано до 0.10111 * 2 ^-3
Истинная экспонента -3, она будет сохранена в смещенной форме -3 + 4 = 1

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

3.1.3 Формат с плавающей запятой IEEE

Существует несколько различных форматов хранения реальных данных в компьютерах. Мы уже видели довольно упрощенный вариант: двоичная последовательность, разделенная на два поля — экспонента и мантисса. Сейчас мы рассмотрим самое популярный формат, который используется в реальном мире: с плавающей запятой IEEE формат .

IEEE (IEEE для института инженеров электроники и электротехники) формат сам по себе разделен на три основных формата, называемых single , double и quad , каждый из которых имеет определенный уровень точности.

Число с плавающей запятой IEEE определяется следующим образом:

N = (-1) ^S * 1.F * 2 ^E

Формат одинарной точности представлен следующим образом:

Число занимает всего 32 бита.Первый бит — это знаковый бит (0 <=> положительный, 1 <=> отрицательный) следующие 8 бит зарезервированы для экспонента со смещением , а оставшиеся 23 бита оставлены для дробная часть мантиссы.

Почему мы храним только дробную часть мантиссы, а не вся мантисса? Числа с плавающей запятой IEEE нормализованы так, чтобы их мантиссы всегда имеют целую часть, равную 1, то есть мантиссы всегда лежат в диапазоне от 1.000 …. 00 до 1.111 …. 11 (если не указано иное указано, мы всегда говорим о двоичных числах). Поскольку по определению формата IEEE целая часть мантиссы всегда будет 1, там нет необходимости хранить его явно, что позволяет сэкономить один бит. Таким образом, дробное часть мантиссы может иметь один дополнительный значащий бит. Двойная точность и четверная точность работают с мантиссой точно так же.

Во всех трех форматах минимальный показатель степени (т.е. 0) вместе с мантиссой = 0 (как целая, так и дробная часть равны 0) используется для представления знаковый ноль, в то время как максимальный показатель используется для представления плюса или минуса бесконечность, или NaN . NaN означает не число. Также обратите внимание, что поскольку В формате IEEE используется знаковый бит, нет необходимости в арифметике с дополнением до двух. здесь.

Пришло время для примера.

Пример:

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

3,2 АРИФМЕТИКА ПЛАВАЮЩЕЙ ТОЧКИ

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

Рассмотрим сложение двух вещественных десятичных чисел. как числа с фиксированной запятой:

1234,00
+
56,78
_______

1290,78

Теперь, если мы попытаемся сложить те же числа, записанные в нотации с плавающей запятой, мы видим, что простое добавление мантисс не имеет смысла, если экспоненты равны:

0,1234 * 10 ⁴
+
0.5678 * 10 ²
___________

???????

Таким образом, перед сложением / вычитанием необходимо выполнить следующие шаги. два числа с плавающей запятой:

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

2. Сложить / вычесть мантиссы.

3. При необходимости повторно нормализовать результат (это называется после нормализации ).

Мы применяем эти шаги к приведенному выше примеру:

1.0,1234 * 10 ⁴ + 0,5678 * 10 ² = 0,1234 * 10 ⁴ + 0,005678 * 10 ⁴
2. 0,1234 * 10 ⁴ + 0,005678 * 10 ⁴ = 0,129078 * 10 ⁴
3. В этом примере результат уже нормализован.

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

При умножении двух чисел с плавающей запятой выполните следующие действия. шаги:
1. Сложите экспоненты.
2. Умножьте мантиссы (как числа без знака).
3. Подобные знаки дают положительный результат, разные знаки дают отрицательный результат.

При выполнении арифметики с плавающей запятой всегда следует учитывать Обратите внимание на следующие факты:

1.Поскольку в целом показатель степени и мантисса разделяют одно и то же слово, часто необходимо распаковать их, т.е. разделите их, прежде чем проводить с ними операции. Например, с формат IEEE, экспонента и мантисса упакованы вместе в 32-битное слово, чтобы минимизировать объем памяти, когда они хранятся в памяти. Когда номер распаковывается для участия в операции, формат называется расширенный . Ведущий 1 вставлен спереди 23-битной дробной мантиссы, что приводит к 24-битной мантиссе, а затем мантисса расширяется до 32 бит.В таком компьютере, как 68000, где слова имеют 16 бит, мантисса расширяется, чтобы занимать два полных слова, что значительно увеличивает его точность. Все расчеты производятся с расширенная 32-битная мантисса. После того, как «номер выполнил свою работу», его упаковывается в исходный формат и сохраняется в памяти.

2. Если два показателя различаются более чем на m + 1, где m — количество значащих бит мантиссы, нет указывает на добавление или вычитание этих двух чисел, потому что меньшее число слишком мало, чтобы существенно повлиять на большее число.Там есть нет смысла добавлять 0,123987 * 10 ³ к 0,112233 * 10 ⁴¹ потому что это добавление не повлияет на мантиссу из 6 цифр. Конец результат будет фактически равен большему операнду.

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

3,3 ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД ДВОИЧНЫМИ ЧИСЛАМИ

Логические операции, которые мы рассматриваем в этом курсе, — это И , OR , EOR и НЕ .Их называют «логическими», потому что они считают 1 истинным и 0 ложным (это принятое соглашению, но нет причин, по которым 0 нельзя назвать истинным, а 1 ложным) . Эти операции по существу побитовые, т.е. они выполняются бит по битам. Операция НЕ — единственная, которая принимает один операнд. вместо двух. Остальные операции выполняются между парами соответствующих биты в двух операндах. Позже мы увидим, что процессор Motorola 68000 имеет специальные инструкции, которые выполняют эти операции.

Когда логическая операция применяется к двум словам по n бит каждое, операция выполняется между соответствующими парами битов. Например, если у нас есть abcd И wxyz , Результат мноп где p = d И z , o = c И y , n = b И x , м = a И Вт .

Пример:

А = 01011001
B = 00001111
А И В = С = 00001001

Пример:

А = 01011001
B = 00001111
A ИЛИ B = C = 01011111

Пример:

А = 01011001
B = 00001111
A EOR B = C = 01010110

А = 1010011 НЕ A = 0101100 = дополнение A

3.4 РЕЗЮМЕ

• Как правило, компьютеры хранят действительные числа в формате с плавающей запятой.

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

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

• Преимущество представления с фиксированной точкой в ​​том, что оно не требует сложных аппаратное или программное обеспечение. Его недостаток в том, что он работает очень неэффективно. с точки зрения места для хранения с очень большими и очень маленькими номерами. Его использование поэтому следует ограничиваться небольшими диапазонами действительных чисел.

• Числа с плавающей запятой представлены в виде m * r ^e , где м — это мантисса , r — это основание или с основанием , а e — это показатель степени .Числа с плавающей запятой хранятся в компьютерах в виде двоичных последовательностей, разделенных на разные поля, одно поле хранит мантиссу, другое — показатель степени и т. д. Основание системы счисления понимается и не сохраняется явно. В зависимости от формата, который используется общий размер двоичной последовательности действительного числа и относительный размер различных полей в этой последовательности может быть различным.

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

• По соглашению числа с плавающей запятой всегда нормализованы.

• Есть два общепринятых способа нормализации мантиссы.Один из них — всегда ограничивайте мантиссу в диапазоне от 0,100 … 00 до 0,111 ….. 11 соответствующим образом регулируя показатель степени. Другой приемлемый способ — ограничить мантисса в диапазоне от 1.000 … 00 до 1.111 … 11, снова путем регулировки соответственно показатель степени.

• Нормализация показателя степени называется смещением.

• N-битовый показатель степени может представлять 2 ⁿ различных значений показателя степени. Прежде чем оно будет сохранено в компьютере, истинное значение экспоненты к нему добавляется константа или смещение, и именно этот новый смещенный показатель хранится.Величина смещения выбирается так, чтобы максимально отрицательная значение истинной экспоненты может быть сохранено в компьютере как 0. Предвзятость выбирается так, чтобы истинные значения n-битной экспоненты варьировались от -2 ^n-1 до 2 ^n-1 — 1, могут быть представлены внутри с серией беззнаковых чисел от 0 до 2 ⁿ — 1.

• Формула, связывающая истинное значение показателя степени с показателем степени в компьютере хранится:

E _s = E _t + B
, где E _s — это сохраненная или смещенная экспонента, E _t — истинный показатель степени, а B — смещение (константа).

• Самый популярный формат для хранения реальных данных в компьютерах сегодня — Формат с плавающей запятой IEEE . Сам он разделен на три основных формата: называется single , double и quad , каждый из них имеющий определенный уровень точности.

• Число с плавающей запятой IEEE определяется как:

N = (-1) ^S * 1.F * 2 ^E

где S — знаковый бит: 0 для положительной мантиссы, 1 для отрицательной мантисса; F — дробная часть мантиссы; и E — смещенный экспонента.E — bias дает вам истинную экспоненту.

• Двоичная последовательность числа с плавающей запятой IEEE делится на 3 поля: первое поле размером один бит хранит знаковый бит, следующее поле, размер которого варьируется от одного уровня точности к другому, хранит смещенные экспонента, а остальные биты составляют третье поле, в котором хранится дробная часть мантиссы. Перед хранением мантиссу нормализуют. так что он всегда находится в диапазоне от 1.000 … 000 до 1.111 … 111, и ведущая 1 не сохраняется, потому что она понятна. Показатель степени имеет должны быть скорректированы соответствующим образом. В следующей таблице перечислены функции. из трех основных форматов IEEE:

		Одинарный	Двойной	Четырехъядерный
Количество бит, принимаемых:
	Знак	1	1	1
	Показатель степени	8	11	15
	Дробная мантисса	23	52	111
	Всего	32	64	128
Показатель степени:
	Смещение	127	1023	16383
	Диапазон (смещенной) экспоненты:	0..255	0..2047	0..32767

• Следующие шаги должны быть выполнены перед сложением / вычитанием двух числа с плавающей запятой:

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

2. Сложить / вычесть мантиссы.

3. При необходимости повторно нормализовать результат (это называется постнормализацией).

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

• При умножении двух чисел с плавающей запятой выполните следующие действия:

1.Добавьте экспоненты.
2. Умножьте мантиссы (как числа без знака).
3. Подобные знаки дают положительный результат, разные знаки дают отрицательный результат.

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

• Если показатели двух чисел отличаются более чем на m + 1, где m — это количество значащих бит мантиссы, добавлять нет смысла или вычитая эти два числа, потому что меньшее число слишком мало чтобы существенно повлиять на большее число.

• Если показатель результата операции больше максимального возможное значение или меньше минимального

возможное значение, есть случай переполнения экспоненты или истощения экспоненты, соответственно.

• 4 основные логические операции, которые выполняются с двоичными значениями: И , OR , EOR и НЕ . Их называют «логическими», потому что они считают 1 истинным, а 0 — ложным. Эти операции являются побитовыми, т.е. они выполняются между соответствующими парами битов.

• Результат выражения a AND b истинен тогда и только тогда, когда оба а и б верны. В противном случае это ложь.Вот таблица истинности для И операция:



а	б	а И б
0	0	0
0	1	0
1	0	0
1	1	1


Операция AND может использоваться для выборочной очистки (установки в 0) битов.

• Результат операции a OR b ложен тогда и только тогда, когда и a, и b ложны. Верно, когда оба оператора верны, или когда только один из их правда. Вот таблица истинности для операции ИЛИ:



а	б	a OR b
0	0	0
0	1	1
1	0	1
1	1	1


Операция ИЛИ может использоваться для выборочной установки (установки в 1) битов.

• Операция EOR или Exclusive OR дает истинный результат тогда и только тогда, когда только один из операндов верен. Ложно, если оба операнда верны, или когда оба операнда ложны. Вот таблица истинности для операции EOR:



а	б	a EOR b
0	0	0
0	1	1
1	0	1
1	1	0


Операция EOR может использоваться для выборочного переключения (изменения состояния) битов.

• Операция НЕ принимает единственный операнд и просто инвертирует его биты. В таблица истинности для операции НЕ:

Вещественные числа — Представление данных — Высшая редакция вычислительной науки

Вещественные числа — это числа, которые включают дроби / значения после десятичной точки.

Например, 123,75 — действительное число. Этот тип числа также известен как число с плавающей запятой .

Все числа с плавающей запятой хранятся компьютерной системой с использованием мантиссы и показателя степени .

Следующий пример используется для иллюстрации роли мантиссы и экспоненты.Он не полностью отражает компьютерный метод хранения действительных чисел, но дает общее представление.

Число 123,75 может быть представлено с использованием математической научной записи как:

1,2375 x 10 ² = 123,75

Умножение числа на десять в степени двойки (10 ² ) перемещает значения на две позиции вверх (или десятичная точка вниз на два разряда), так что число 123 находится перед десятичной точкой, а число 75 теперь идет сразу после десятичной точки.В этом примере мантисса равна 1,2375, а показатель степени — 2. Обычно это можно представить как:

MX 10 ^E

Чтобы представить то же значение в двоичном формате, примените следующие правила:

Представьте число 123.75 как:

20 2

Число, созданное в двоичном формате, является мантиссой:

111101111

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

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

1.11101111

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

1.11101111 — десятичная точка должна переместиться на шесть позиций, чтобы точно представить 123.75

Таким образом, показатель нашего числа равен 6. В двоичной системе число шесть равно:

Поскольку 4 + 2 = 6

Чтобы представить 123,75, мантисса будет 111101111, а показатель степени — 110. Это можно представить как:

MX 2 ^E (где M представляет мантиссу, а E представляет показатель степени)

1.11101111 x 2 ¹¹⁰

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

• увеличение количества бит, выделенных мантиссе, повысит точность числа с плавающей запятой
• увеличение количества биты, выделенные для экспоненты, увеличивают диапазон чисел, которые могут храниться

двоичная арифметика — Представляет действительное число без потери точности

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

Однако, если вас интересуют только алгебраические числа, то вам повезло: теория реальных замкнутых полей является полной, o-минимальной и разрешимой. Это было доказано Тарским в 1948 году.

Но есть загвоздка. Вы не хотите использовать алгоритм Тарского, поскольку он относится к классу сложности NONELEMENTARY, что настолько непрактично, насколько это вообще возможно для непрактичных алгоритмов.Есть более современные методы, которые сводят сложность к DEXP, который является лучшим из известных нам на данный момент.

Обратите внимание, что проблема NP-сложная, потому что она включает SAT. Однако неизвестно (или не предполагается), что он находится в НП.

РЕДАКТИРОВАТЬ Я попытаюсь объяснить это немного подробнее.

Основой для понимания всего этого является проблема принятия решений, известная как теории по модулю удовлетворенности, или сокращенно SMT. По сути, мы хотим решить SAT для теории, основанной на классической логике.

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

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

Арифметика Пресбургера — это теория натуральных чисел со сложением. Эта теория разрешима.

Арифметика Пеано — это теория натуральных чисел со сложением и умножением. Эта теория неразрешима, как это было доказано Гёделем.

Арифметика Тарского — это теория действительных чисел со всеми полевыми операциями (сложение, вычитание, умножение и деление). Интересно, что эта теория разрешима. В то время это был крайне противоречивый результат. 3-3 = 0 $$

Итак, возникает вопрос, какие еще операции вы можете добавить к арифметике Тарского и при этом сохранить разрешимость.{ix} $, тогда у вас автоматически будет тригонометрия.

Альфред Тарский (1948), Метод принятия решений для элементарной алгебры и геометрии .

Введение в теоретическую информатику: вычисления и представление

• Различают спецификацию и реализацию или, что эквивалентно, математических функций и алгоритмы / программы .
• Представление объекта в виде строки (часто из нулей и единиц).
• Примеры представлений для общих объектов, таких как числа, векторы, списки и графики.
• Представления без префиксов.
• Теорема Кантора: Действительные числа не могут быть представлены точно как конечные строки.

«Алфавит (так в оригинале) был великим изобретением, которое позволило людям (так в оригинале) запоминать и усваивать с небольшими усилиями то, что другие узнали на собственном горьком опыте, то есть учиться по книгам, а не по прямым, возможно, болезненным, контакт с реальным миром.”, Б.Ф. Скиннер

«Название песни« HADDOCK’S EYES ». [сказал Рыцарь]

«О, это название песни, не так ли?» — сказала Алиса, пытаясь заинтересоваться.

«Нет, ты не понимаешь», — сказал Рыцарь с немного раздраженным видом. «Так НАЗЫВАЕТСЯ имя. Имя на самом деле «ПРЕСТАРЕЛЫЙ МУЖЧИНА».

«Тогда мне следовало сказать:« Так называется ПЕСНЯ »?» Алиса поправилась.

«Нет, не надо: это совсем другое! ПЕСНЯ называется «ПУТИ И СРЕДСТВА»: но это только то, что она НАЗЫВАЕТСЯ, знаете ли! »

«Ну, а что же тогда за песня?» сказала Алиса, которая к этому времени была полностью сбита с толку.

«Я к этому подходил», — сказал Рыцарь. «Песня действительно НАСТОЯЩИЙ НА ВОРОТАХ, а мелодия — мое собственное изобретение».

Льюис Кэрролл, В Зазеркалье

В первом приближении, вычисление — это процесс, который отображает вход на выход .

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

В этой главе мы сосредоточимся на части what , а именно на определении вычислительных задач. Для начала нам нужно определить входы и выходы. Захват всех потенциальных входов и выходов, которые мы, возможно, когда-либо захотим вычислить, кажется сложной задачей, поскольку сегодня вычисления применяются к широкому спектру объектов. Мы вычисляем не только числа, но и тексты, изображения, видео, графики соединений социальных сетей, МРТ, данные генов и даже другие программы. Мы представим все эти объекты как строки нулей и единиц, то есть такие объекты, как \ (0011101 \) или \ (1011 \), или любой другой конечный список из \ (1 \) и \ (0 \). с.(Этот выбор сделан для удобства: в нулях и единицах нет ничего «святого», и мы могли бы использовать любой другой конечный набор символов.)

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

За последние несколько десятилетий мы стали свидетелями революции в том, что мы можем представлять и передавать в цифровой форме.Мы можем запечатлеть события с почти идеальной точностью и мгновенно распространить их среди неограниченной аудитории. Более того, как только информация находится в цифровой форме, мы можем вычислить над ней и получить представление о данных, которые были недоступны в прежние времена. В основе этой революции лежит простое, но глубокое наблюдение, что мы можем представить неограниченное разнообразие объектов, используя конечный набор символов (и фактически используя только два символа 0 и 1 ).

В последующих главах мы обычно будем принимать такие представления как должное и, следовательно, будем использовать такие выражения, как «программа \ (P \) принимает \ (x \) в качестве входных данных», когда \ (x \) может быть числом, вектором, граф или любой другой объект, когда мы действительно имеем в виду, что \ (P \) принимает в качестве входных данных представление \ (x \) в виде двоичной строки. Однако в этой главе мы подробнее остановимся на том, как мы можем построить такие представления.

Основные выводы из этой главы:

• Мы можем представить все виды объектов, которые мы хотим использовать в качестве входов и выходов, используя двоичных строк .Например, мы можем использовать двоичный базис для представления целых и рациональных чисел в виде двоичных строк (см. Раздел 2.1.1 и Раздел 2.2).

• Мы можем составить представлений простых объектов для представления более сложных объектов. Таким образом, мы можем представлять списки целых или рациональных чисел и использовать их для представления таких объектов, как матрицы, изображения и графики. Кодирование без префиксов — один из способов добиться такой композиции (см. Раздел 2.5.2).

• Вычислительная задача задает отображение от входа к выходу — функцию . Крайне важно различать «что» и «как» или спецификацию и реализацию (см. Раздел 2.6.1). Функция просто определяет, какой выход соответствует какому входу. Он не указывает , как вычислять выходные данные из входных, и, как мы видели в контексте умножения, может быть несколько способов вычисления одной и той же функции.

• Хотя набор всех возможных двоичных строк бесконечен, он по-прежнему не может представлять всего . В частности, не существует представления действительных чисел и (с абсолютной точностью) в виде двоичных строк. Этот результат также известен как «теорема Кантора» (см. Раздел 2.4) и обычно упоминается как результат о том, что «действительные числа неисчислимы». Также подразумевается, что существует различных уровней бесконечности, хотя мы не будем углубляться в эту тему в этой книге (см. Замечание 2.10).

Две «большие идеи», которые мы обсуждаем, — это Большая идея 1 — мы можем составлять представления простых объектов для представления более сложных объектов, и Большая идея 2 — очень важно различать программы функций («что») и ‘ («как»). Последнее будет темой, к которой мы будем возвращаться снова и снова в этой книге.

Определение представлений

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

Чтобы использовать такие объекты, как числа, изображения, графики или другие в качестве входных данных для вычислений, нам необходимо точно определить, как представлять эти объекты в виде двоичных строк.* \). Конечно, мы не можем просто представить все числа в виде строки «\ (0011 \)» (например). Минимальное требование состоит в том, что если два числа \ (x \) и \ (x ‘\) различны, то они будут представлены разными строками. Другой способ сказать это — мы требуем, чтобы функция кодирования \ (E \) была один к одному .

Представление натуральных чисел

Теперь мы покажем, как можно представить натуральные числа в виде двоичных строк. На протяжении многих лет люди представляли числа по-разному, в том числе римскими цифрами, счетными метками, нашей собственной индуистско-арабской десятичной системой и многими другими.{96n} \). Изображение взято из сообщения в блоге А. К. Андерсена.

Если \ (n \) четно, то наименее значащая цифра двоичного представления \ (n \) равна \ (0 \), а если \ (n \) нечетно, то эта цифра равна \ ( 1 \). n \).

Значение представлений (обсуждение)

Для нас естественно думать о \ (236 \) как о «действительном» числе, а о \ (11101100 \) как о «просто» его представлении. Однако для большинства европейцев в средние века CCXXXVI было бы «действительным» числом, а \ (236 \) (если бы они даже слышали о нем) было бы странным индо-арабским позиционным представлением. ¹ Когда наши AI-роботы-повелители материализуются, они, вероятно, будут думать о \ (11101100 \) как о «фактическом» числе, а о \ (236 \) как о «просто» представлении, которое им нужно использовать, когда они дают команды людям. .

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

Австрийский философ Людвиг Витгенштейн, с другой стороны, утверждал, что математических объектов не существует вообще, а существуют только фактические отметки на бумаге, составляющие \ (236 \), \ (11101100 \) или . ССХХХVI . По мнению Витгенштейна, математика — это всего лишь формальное манипулирование символами, не имеющими внутреннего значения. Вы можете думать о «фактическом» числе как о (несколько рекурсивно) «то, что является общим для \ (236 \), \ (11101100 \) и CCXXXVI и всех других прошлых и будущих репрезентаций, которые предназначены для объект».

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

Представления за пределами натуральных чисел

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

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

\ [ZtS (m) = \ begin {case} 0 \; NtS (m) & m \ geq 0 \\ 1 \; NtS (-m) & m <0 \ end {ases} \]

Повторяя ту же идею, как только мы можем представить объекты типа \ (T \), мы также можем представить списков списков, таких объектов и даже списки списков списков и так далее, и тому подобное.Мы вернемся к этому моменту, когда обсудим кодировку без префикса в Разделе 2.5.2.

Представление действительных чисел

Набор из действительных чисел \ (\ R \) содержит все числа, включая положительные, отрицательные и дробные, а также иррациональных чисел , таких как \ (\ pi \) или \ (e \). {e} \) ближе всего к \ (x \).e \) для \ (b, e \). Это называется «с плавающей запятой», потому что мы можем думать о числе \ (b \) как о последовательности двоичных цифр, а о \ (e \) как о расположении «двоичной точки» в этой последовательности. Использование плавающего представления является причиной того, почему во многих системах программирования печать выражения 0,1 + 0,2 приводит к 0,30000000000000004 , а не 0,3 , подробнее см. Здесь, здесь и здесь.

Читатель может (справедливо) обеспокоиться тем фактом, что представление с плавающей запятой (или рациональное число один) может только приблизительно представлять действительные числа. Во многих (хотя и не во всех) вычислительных приложениях можно сделать точность достаточно высокой, чтобы это не повлияло на конечный результат, хотя иногда нам нужно быть осторожными. Действительно, ошибки с плавающей запятой иногда не могут быть предметом для шуток. Например, ошибки округления с плавающей запятой были причастны к отказу U.Ракета S. Patriot для перехвата иракской ракеты Скад, унесшая жизни 28 человек, а также ошибка в 100 миллионов фунтов стерлингов при вычислении выплат британским пенсионерам.

Теорема Кантора, счетные множества и строковые представления действительных чисел

«Для любого сбора фруктов мы можем приготовить больше фруктовых салатов, чем фруктов. В противном случае мы могли бы обозначить каждый салат разными фруктами и рассмотреть салат из всех фруктов, которых нет в их салате. Этикетка этого салата есть в нем тогда и только тогда, когда его нет.* \). Представление о том, что существуют «оттенки бесконечности», глубоко беспокоило математиков и философов в то время. Философ Людвиг Витгенштейн (о котором мы упоминали ранее) назвал результаты Кантора «полнейшей чепухой» и «смехотворной». Другие думали, что они еще хуже. Леопольд Кронекер назвал Кантора «развратником молодежи», а Анри Пуанкаре сказал, что идеи Кантора «должны быть изгнаны из математики раз и навсегда». \ infty \).* \) (со строками, отсортированными в лексикографическом порядке) и содержит последовательность \ (StF (x) (0), StF (x) (1), StF (x) (2), \ ldots \). Элементы диагонали и в этой таблице имеют значения

.

\ [StF (\ suremath {\ text {\ texttt {«»}}}) (0), StF (0) (1), StF (1) (2), StF (00) (3), StF ( 01) (4), \ ldots \]

, которые соответствуют элементам \ (StF (x_n) (n) \) в \ (n \) — й строке и \ (n \) —м столбце этой таблицы для \ (n = 0,1,2, \ ldots \). Функция \ (\ overline {d} \), которую мы определили выше, отображает каждое \ (n \ in \ N \) в отрицание \ (n \) — го диагонального значения.* \) — некоторая строка, и пусть \ (g = StF (x) \). Если \ (n \) — позиция \ (x \) в лексикографическом порядке, то по построению \ (\ overline {d} (n) = 1-g (n) \ neq g (n) \), что означает, что \ (g \ neq \ overline {d} \), что мы и хотели доказать.

Чтобы завершить доказательство теоремы 2.5, нам нужно показать лемму 2.9. Это требует некоторого опыта в области вычислений, но в остальном все просто. Если у вас раньше не было большого опыта работы с ограничениями реального ряда, то формальное доказательство, приведенное ниже, может быть трудновыполнимо.\ infty \), то должен быть какой-то ввод \ (k \), с которым они не согласны. Если взять такой минимум \ (k \), то числа \ (f (0) .f (1) f (2) \ ldots f (k-1) f (k) \ ldots \) ​​и \ (g (0). G (1) g (2) \ ldots g (k) \ ldots \) ​​согласуются друг с другом вплоть до \ (k-1 \) — й цифры после десятичной точки, и не согласны по \ (k \) — я цифра. Но тогда эти числа должны быть разными. Конкретно, если \ (f (k) = 1 \) и \ (g (k) = 0 \), то первое число больше второго, а в противном случае (\ (f (k) = 0 \) и \ ( g (k) = 1 \)) первое число меньше второго.\ infty \). Поскольку \ (f \) и \ (g \) различны, должен быть некоторый вход, на котором они различаются, и мы определяем \ (k \) как наименьший такой вход и предполагаем без ограничения общности, что \ (f ( к) = 0 \) и \ (g (k) = 1 \). (В противном случае, если \ (f (k) = 1 \) и \ (g (k) = 0 \), то мы можем просто поменять ролями \ (f \) и \ (g \). * \) до \ (S \).* \).

Существует отображение на некотором счетном множестве \ (T \) в \ (S \).

Существует взаимно однозначное отображение \ (S \) в некоторое счетное множество \ (T \).

Убедитесь, что вы знаете, как доказать эквивалентность всех приведенных выше результатов.

Представление объектов помимо чисел

Числа, конечно, ни в коем случае не единственные объекты, которые мы можем представить в виде двоичных строк. Схема представления для представления объектов из некоторого набора \ (\ mathcal {O} \) состоит из функции кодирования , которая отображает объект в \ (\ mathcal {O} \) в строку, и декодирования функция, которая декодирует строку обратно в объект в \ (\ mathcal {O} \).* \ rightarrow_p \ mathcal {O} \) является (возможно, частичной) функцией и такая, что \ (D \) и \ (E \) удовлетворяют тому, что \ (D (E (o)) = o \) для каждого \ (о \ ин \ mathcal {O} \). \ (E \) известна как функция кодирования , а \ (D \) известна как функция декодирования .

Обратите внимание, что условие \ (D (E (o)) = o \) для каждого \ (o \ in \ mathcal {O} \) подразумевает, что \ (D \) равно на (вы понимаете, почему?) . Оказывается, что для построения схемы представления нам нужно всего лишь найти функцию , кодирующую .* \), существует либо ноль, либо единственный \ (o \ in \ mathcal {O} \) такой, что \ (E (o) = x \) (иначе \ (E \) не было бы взаимно однозначным ). Мы определим \ (D (x) \) равным \ (o_0 \) в первом случае и этот единственный объект \ (o \) во втором случае. По определению \ (D (E (o)) = o \) для каждого \ (o \ in \ mathcal {O} \).

Конечные представления

Если \ (\ mathcal {O} \) равно конечному , то мы можем представить каждый объект в \ (\ mathcal {O} \) в виде строки длиной не более некоторого числа \ (n \). Какое значение имеет \ (n \)? Обозначим через \ (\ {0,1 \} ^ {\ leq n} \) множество \ (\ {x \ in \ {0,1 \} ^ *: | x | \ leq n \} \) строк длиной не более \ (n \).{n + 1} -1 \), как следует из следующей леммы:

Для любых двух непустых конечных множеств \ (S, T \) существует взаимно однозначное \ (E: S \ rightarrow T \) тогда и только тогда, когда \ (| S | \ leq | T | \ ).

Пусть \ (k = | S | \) и \ (m = | T | \), и поэтому запишем элементы \ (S \) и \ (T \) как \ (S = \ {s_0, s_1, \ ldots, s_ {k-1} \} \) и \ (T = \ {t_0, t_1, \ ldots, t_ {m-1} \} \). Нам нужно показать, что существует взаимно однозначная функция \ (E: S \ rightarrow T \) тогда и только тогда, когда \ (k \ leq m \). Для направления «если», если \ (k \ leq m \), мы можем просто определить \ (E (s_i) = t_i \) для каждого \ (i \ in [k] \).Ясно, что для \ (i \ neq j \), \ (t_i = E (s_i) \ neq E (s_j) = t_j \), и, следовательно, эта функция взаимно однозначна. С другой стороны, предположим, что \ (k> m \) и \ (E: S \ rightarrow T \) — некоторая функция. Тогда \ (E \) не может быть взаимно однозначным. Действительно, для \ (i = 0,1, \ ldots, m-1 \) отметим элемент \ (t_j = E (s_i) \) в \ (T \). Если \ (t_j \) был отмечен ранее, то мы нашли два объекта в \ (S \), отображающих один и тот же элемент \ (t_j \). В противном случае, поскольку \ (T \) имеет \ (m \) элементов, когда мы добираемся до \ (i = m-1 \), мы отмечаем все объекты в \ (T \).Следовательно, в этом случае \ (E (s_m) \) должен отображаться на элемент, который уже был отмечен ранее. (Это наблюдение иногда называют «принципом голубиной норы»: принцип, согласно которому если у вас есть голубятня с \ (m \) отверстиями и \ (k> m \) голубями, то в одной норе должно быть два голубя. .)

Кодировка без префиксов

При показе схемы представления рациональных чисел мы использовали «хитрость» кодирования алфавита \ (\ {0,1, \ | \} \) для представления кортежей строк как одной строки.Это частный случай общей парадигмы кодирования без префиксов . Идея заключается в следующем: если наше представление имеет свойство, что никакая строка \ (x \), представляющая объект \ (o \), не является префиксом (т.е. начальной подстрокой) строки \ (y \), представляющей другой объект \ (o ‘\), то мы можем представить список объектов, просто объединив представления всех членов списка. Например, поскольку в английском языке каждое предложение заканчивается знаком препинания, например точкой, восклицательным знаком или вопросительным знаком, ни одно предложение не может быть префиксом другого, и поэтому мы можем представить список предложений, просто соединяя предложения одно за другим. .(Английский язык имеет некоторые сложности, такие как точки, используемые для сокращений (например, «например») или цитаты в предложениях, содержащие знаки препинания, но точка высокого уровня представления предложений без префиксов по-прежнему сохраняется.)

Оказывается, мы можем преобразовать каждое представление в форму без префиксов. Это оправдывает Большую идею 1 и позволяет нам преобразовать схему представления для объектов типа \ (T \) в схему представления списков объектов типа \ (T \).* \), определим

\ [ \ overline {E} (o_0, \ ldots, o_ {k-1}) = E (o_0) E (o_1) \ cdots E (o_ {k-1}) \ ;. \]

Теорема 2.18 — это пример теоремы, которую немного сложно разобрать, но на самом деле ее довольно просто доказать, если вы поймете, что она означает. Поэтому я настоятельно рекомендую вам остановиться здесь, чтобы убедиться, что вы поняли формулировку этой теоремы. Вы также должны попытаться доказать это самостоятельно, прежде чем продолжить.

2.9: Если у нас есть представление каждого объекта без префиксов, мы можем объединить представления объектов \ (k \), чтобы получить представление для кортежа \ ((o_0, \ ldots, o_ {k-1}) \) .

Идея доказательства проста. Предположим, что, например, мы хотим декодировать тройку \ ((o_0, o_1, o_2) \) из ее представления \ (x = \ overline {E} (o_0, o_1, o_2) = E (o_0) E (o_1) E (о_2) \). Мы сделаем это, сначала найдя первый префикс \ (x_0 \) для \ (x \), который является представлением некоторого объекта. Затем мы декодируем этот объект, удалим \ (x_0 \) из \ (x \), чтобы получить новую строку \ (x ‘\), и продолжим дальше, чтобы найти первый префикс \ (x_1 \) из \ (x’ \ ) и так далее (см. упражнение 2.9). Свойство без префикса \ (E \) гарантирует, что \ (x_0 \) будет фактически \ (E (o_0) \), \ (x_1 \) будет \ (E (o_1) \) и т. Д.

Приведем формальное доказательство. Предположим, для противодействия, что существуют два различных кортежа \ ((o_0, \ ldots, o_ {k-1}) \) и \ ((o’_0, \ ldots, o ‘_ {k’-1 }) \) такая, что

\ [ \ overline {E} (o_0, \ ldots, o_ {k-1}) = \ overline {E} (o’_0, \ ldots, o ‘_ {k’-1}) \ ;. \; \; (2.4) \] Обозначим строку \ (\ overline {E} (o_0, \ ldots, o_ {k-1}) \) через \ (\ overline {x} \).

Пусть \ (i \) будет первым индексом, таким что \ (o_i \ neq o’_i \). (Если \ (o_i = o’_i \) для всех \ (i \), то, поскольку мы предполагаем, что два кортежа различны, один из них должен быть больше другого.В этом случае мы предполагаем без ограничения общности, что \ (k ‘> k \), и пусть \ (i = k \).) В случае, \ (i

\ [ \ overline {x} = \ overline {E} (o_0, \ ldots, o_ {k-1}) = x_0 \ cdots x_ {i-1} E (o_i) E (o_ {i + 1}) \ cdots E (o_ {k-1}) \]

и

\ [ \ overline {x} = \ overline {E} (o’_0, \ ldots, o ‘_ {k’-1}) = x_0 \ cdots x_ {i-1} E (o’_i) E (o’_ {я + 1}) \ cdots E (o ‘_ {k’-1}) \]

, где \ (x_j = E (o_j) = E (o’_j) \) для всех \ (j

В случае, когда \ (i = k \) и \ (k ‘> k \), получаем противоречие следующим образом. В данном случае

\ [\ overline {x} = E (o_0) \ cdots E (o_ {k-1}) = E (o_0) \ cdots E (o_ {k-1}) E (o’_k) \ cdots E ( o ‘_ {k’-1}) \]

, что означает, что \ (E (o’_k) \ cdots E (o ‘_ {k’-1}) \) должен соответствовать пустой строке \ (\ text {\ suremath {\ text {\ texttt {«» }}}} \).* \) быть взаимно однозначной функцией. Тогда существует взаимно однозначное кодирование без префиксов \ (\ overline {E} \) такое, что \ (| \ overline {E} (o) | \ leq 2 | E (o) | +2 \) для каждые \ (o \ in \ mathcal {O} \).

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

Идея доказательства состоит в том, чтобы использовать карту \ (0 \ mapsto 00 \), \ (1 \ mapsto 11 \), чтобы «удвоить» каждый бит в строке \ (x \), а затем отметить конец строки присоединив к нему пару \ (01 \).* \) путем определения \ (\ overline {E} (o) = \ suremath {\ mathit {PF}} (E (o)) \).

Для доказательства леммы нам нужно показать, что (1) \ (\ overline {E} \) взаимно однозначно, а (2) \ (\ overline {E} \) не имеет префиксов. Фактически, свобода префикса является более сильным условием, чем взаимно однозначность (если две строки равны, то, в частности, одна из них является префиксом другой), и, следовательно, достаточно доказать (2) , что мы сейчас и делаем. .

Пусть \ (o \ neq o ‘\) in \ (\ mathcal {O} \) — два различных объекта.Мы докажем, что \ (\ overline {E} (o) \) не является префиксом \ (\ overline {E} (o ‘) \). Определите \ (x = E (o) \) и \ (x ‘= E (o’) \). Поскольку \ (E \) взаимно однозначно, \ (x \ neq x ‘\). Согласно нашему предположению, \ (\ suremath {\ mathit {PF}} (x) \) является префиксом \ (\ suremath {\ mathit {PF}} (x ‘) \). Если \ (| x | <| x '| \), то два бита в позициях \ (2 | x |, 2 | x | +1 \) в \ (\ suremath {\ mathit {PF}} (x) \ ) имеют значение \ (01 \), но соответствующие биты в \ (\ suremath {\ mathit {PF}} (x ') \) будут равны либо \ (00 \), либо \ (11 \) (в зависимости от \ (| x | \) - ый бит \ (x '\)) и, следовательно, \ (\ suremath {\ mathit {PF}} (x) \) не может быть префиксом \ (\ suremath {\ mathit {PF}) }(Икс')\).Если \ (| x | = | x '| \), то, поскольку \ (x \ neq x' \), должна быть координата \ (i \), по которой они различаются, что означает, что строки \ (\ suremath { \ mathit {PF}} (x) \) и \ (\ suremath {\ mathit {PF}} (x ') \) различаются координатами \ (2i, 2i + 1 \), что снова означает, что \ (\ suremath {\ mathit {PF}} (x) \) не может быть префиксом \ (\ suremath {\ mathit {PF}} (x ') \). Если \ (| x |> | x ‘| \), то \ (| \ suremath {\ mathit {PF}} (x) | = 2 | x | +2> | \ suremath {\ mathit {PF}} (x ‘) | = 2 | x’ | +2 \) и, следовательно, \ (\ suremath {\ mathit {PF}} (x) \) длиннее (и не может быть префиксом) \ (\ suremath {\ mathit { PF}} (x ‘) \).Во всех случаях мы видим, что \ (\ suremath {\ mathit {PF}} (x) = \ overline {E} (o) \) не является префиксом \ (\ suremath {\ mathit {PF}} (x ‘ ) = \ overline {E} (o ‘) \), что завершает доказательство.

Доказательство леммы 2.20 — не единственный и даже не лучший способ преобразовать произвольное представление в безпрефиксную форму. В упражнении 2.10 предлагается построить более эффективное преобразование без префиксов, удовлетворяющее \ (| \ overline {E} (o) | \ leq | E (o) | + O (\ log | E (o) |) \).

«Доказательство Python» (необязательно)

Доказательства теоремы 2.18 и лемма 2.20 являются конструктивными в том смысле, в каком они дают нам:

• Способ преобразования функций кодирования и декодирования любого представления объекта \ (O \) в функции кодирования и декодирования без префиксов, и

• Способ расширения кодирования и декодирования отдельных объектов без префиксов до кодирования и декодирования списков объектов путем конкатенации.

В частности, мы могли преобразовать любую пару функций Python encode и decode в функции pfencode и pfdecode , которые соответствуют кодированию и декодированию без префиксов.Точно так же, учитывая pfencode и pfdecode для отдельных объектов, мы можем расширить их до кодирования списков. Покажем, как это работает для функций NtS и StN , которые мы определили выше.

Мы начинаем с «Python-доказательства» леммы 2.20: способа преобразования произвольного представления в представление без префикса . Функция без префикса ниже принимает в качестве входных данных пару функций кодирования и декодирования и возвращает тройку функций, содержащих функции кодирования и декодирования без префиксов , а также функцию, которая проверяет, является ли строка допустимой кодировкой объект.

  # принимает функции кодирования и отображения декодирования
# объекты в списки битов и наоборот,
# и возвращает функции pfencode и pfdecode, которые
# сопоставляет объекты спискам битов и наоборот
# без префиксов.
# Также возвращает функцию pfvalid, которая говорит
# является ли список допустимой кодировкой
def без префиксов (кодирование, декодирование):
    def pfencode (o):
        L = кодировать (o)
        return [L [i // 2] для i в диапазоне (2 * len (L))] + [0,1]
    def pfdecode (L):
        return decode ([L [j] для j в диапазоне (0, len (L) -2,2)])
    def pfvalid (L):
        return (len (L)% 2 == 0) и all (L [2 * i] == L [2 * i + 1] для i в диапазоне ((len (L) -2) // 2)) и L [-2:] == [0,1]

    вернуть pfencode, pfdecode, pfvalid

pfNtS, pfStN, pfvalidN = без префиксов (NtS, StN)

НТС (234)
# 11101010
пфНТС (234)
# 111111001100110001
пфСтН (пфНТС (234))
# 234
pfvalidM (pfNtS (234))
# true  

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

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

  def репреслисты (pfencode, pfdecode, pfvalid):
    "" "
    Принимает на себя функции pfencode, pfdecode и pfvalid,
    и возвращает функции encodelists, decodelists
    который может кодировать и декодировать списки объектов
    соответственно.
    "" "

    def encodelist (L):
        "" "Получает список объектов, кодирует его как список битов" ""
        return "" .join ([pfencode (obj) для obj в L])

    def decodelist (S):
        "" "Получает списки битов, возвращает списки объектов" ""
        я = 0; j = 1; res = []
        в то время как j <= len (S):
            если pfvalid (S [i: j]):
                res + = [pfdecode (S [i: j])]
                я = j
            j + = 1
        вернуть res

    вернуть список кодирования, список декодирования


LtS, StL = списки представителей (pfNtS, pfStN, pfvalidN)

LtS ([234,12,5])
# 111111001100110001111100000111001101
StL (LtS ([234,12,5]))
# [234, 12, 5]  

Буквы и текст

Мы можем представить букву или символ строкой, а затем, если это представление не содержит префиксов, мы можем представить последовательность символов, просто объединив представление каждого символа.Одним из таких представлений является ASCII, который представляет буквы и символы \ (128 \) в виде строк из \ (7 \) битов. Поскольку представление ASCII имеет фиксированную длину, оно автоматически не содержит префиксов (вы понимаете, почему?). Юникод - это представление (на момент написания) около 128000 символов в виде чисел (известных как кодовых точек ) между \ (0 \) и \ (1,114,111 \). Существует несколько типов представления кодовых точек без префиксов, популярным из которых является UTF-8, который кодирует каждую кодовую точку в строку длиной от \ (8 \) до \ (32 \).6 \), который написан с использованием точек с отступом, расположенных в два столбца и три строки, см. Рисунок 2.10. (Для кодирования некоторых символов требуется более одной шестибитной строки, поэтому в системе Брайля используется более общая кодировка без префиксов.)

Система Брайля была изобретена в 1821 году Луи Брайлем, когда ему было всего 12 лет (хотя он продолжал работать над ней и улучшать ее на протяжении всей своей жизни). Брайль был французским мальчиком, потерявшим зрение в возрасте 5 лет в результате несчастного случая.

Мы можем использовать языки программирования, чтобы исследовать, как наша вычислительная среда представляет различные ценности.Проще всего это сделать на «небезопасных» языках программирования, таких как C , которые разрешают прямой доступ к памяти.

Используя простую программу C , мы получили следующие представления различных значений. Можно видеть, что для целых чисел умножение на 2 соответствует «сдвигу влево» внутри каждого байта. Напротив, для чисел с плавающей запятой умножение на два соответствует добавлению единицы к показательной части представления. В используемой нами архитектуре отрицательное число представлено с использованием подхода дополнения двух. C представляет строки в форме без префиксов, гарантируя, что в их конце находится нулевой байт.

  int 2: 00000010 00000000 00000000 00000000
интервал 4: 00000100 00000000 00000000 00000000
интервал 513: 00000001 00000010 00000000 00000000
длинный 513: 00000001 00000010 00000000 00000000 00000000 00000000 00000000 00000000
интервал -1: 11111111 11111111 11111111 11111111
внутр -2: 11111110 11111111 11111111 11111111
строка Hello: 01001000 01100101 01101100 01101100 01101111 00000000
строка abcd: 01100001 01100010 01100011 01100100 00000000
поплавок 33.0: 00000000 00000000 00000100 01000010
с плавающей точкой 66.0: 00000000 00000000 10000100 01000010
с плавающей точкой 132.0: 00000000 00000000 00000100 01000011
двойной 132.0: 00000000 00000000 00000000 00000000 00000000 10000000 01100000 01000000  

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

Как только мы можем представить числа и списки чисел, мы также можем представить векторов (которые представляют собой просто списки чисел). Точно так же мы можем представлять списки списков, и таким образом, в частности, можем представлять матриц .Чтобы представить изображение, мы можем представить цвет каждого пикселя списком из трех чисел, соответствующих интенсивности красного, зеленого и синего цветов. (Мы можем ограничиться тремя основными цветами, поскольку у большинства людей в сетчатке глаза есть только три типа колбочек; нам потребовалось бы 16 основных цветов для представления цветов, видимых креветке-богомолу.) Таким образом, изображение размером \ (n \) пикселей будет представлен списком из \ (n \) таких списков длиной три. Видео можно представить в виде списка изображений. Конечно, эти представления довольно расточительны, и для изображений и видео обычно используются гораздо более компактные представления, хотя в этой книге мы не будем этим заниматься.2} \) такое, что \ (A_ {i, j} = 1 \) тогда и только тогда, когда край \ (\ overrightarrow {i \; j} \ in E \). Мы можем преобразовать неориентированный граф в ориентированный, заменив каждое ребро \ (\ {i, j \} \) на оба ребра \ (\ overrightarrow {i \; j} \) и \ (\ overleftarrow {i \; j } \)

Другое представление для графов - это представление списка смежности . То есть мы отождествляем множество вершин \ (V \) графа с множеством \ ([n] \), где \ (n = | V | \), и представляем граф \ (G = (V, E) \) как список \ (n \) списков, где \ (i \) - й список состоит из внешних соседей вершины \ (i \).Разница между этими представлениями может быть значительной для некоторых приложений, хотя для нас обычно несущественна.

2.11: Представление графа \ (G = (\ {0,1,2,3,4 \}, \ {(1,0), (4,0), (1,4), (4,1), (2,1), (3,2), (4,3) \}) \) в представлениях матрицы и списка смежности.

Представление списков и вложенных списков

Если у нас есть способ представления объектов из набора \ (\ mathcal {O} \) в виде двоичных строк, то мы можем представлять списки этих объектов, применяя преобразование без префиксов.* \), то мы можем представить вложенные списки элементов из \ (\ mathcal {O} \), используя строки в пятиэлементном алфавите \ (\ Sigma = \ {\) 0 , 1 , [, ] , , \ (\} \). Например, если \ (o_1 \) представлен 0011 , \ (o_2 \) представлен 10011 , а \ (o_3 \) представлен 00111 , то мы можем представить вложенный список \ ( (o_1, (o_2, o_3)) \) как строка "[0011, [10011,00111]]" над алфавитом \ (\ Sigma \).* \) - это некоторая функция, которая отображает строки в строки, а \ (n \) - целое число, мы могли бы делать такие утверждения, как «\ (F (n) +1 \) является простым», чтобы означать, что если мы представляем \ (n \) как строку \ (x \), то целое число \ (m \), представленное строкой \ (F (x) \), удовлетворяет тому, что \ (m + 1 \) простое число. (Вы можете видеть, как это соглашение об идентификации объектов с их представлением может избавить нас от громоздкого формализма.) Точно так же, если \ (x, y \) - некоторые объекты, а \ (F \) - функция, которая принимает строки в качестве входных данных. , то под \ (F (x, y) \) будем понимать результат применения \ (F \) к представлению упорядоченной пары \ ((x, y) \).Мы используем те же обозначения для вызова функций на \ (k \) - наборах объектов для каждого \ (k \).

Это соглашение об идентификации объекта с его представлением в виде строки - это то, которому мы, люди, всегда следуем. Например, когда люди говорят такое утверждение, как «\ (17 \) - простое число», на самом деле они имеют в виду, что целое число, десятичное представление которого представляет собой строку « 17 », является простым.

Когда мы говорим

\ (A \) - алгоритм, вычисляющий функцию умножения натуральных чисел.* \) - это строка, представляющая пару \ ((a, b) \), тогда \ (F (x) \) будет строкой, представляющей их продукт \ (a \ cdot b \).

Определение вычислительных задач как математических функций

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

В следующих главах мы обратимся к математическому определению вычислительных процессов, но, как мы обсуждали выше, в настоящий момент мы сосредоточены на вычислительных задачах . То есть мы ориентируемся на спецификацию , а не на реализацию . Опять же, на абстрактном уровне вычислительная задача может определять любые отношения, которые должны иметь выход с входом. Однако большую часть этой книги мы сосредоточимся на простейшей и наиболее распространенной задаче вычисления функции .* \ rightarrow \ {0,1 \} \) такое, что \ (F (x) = 1 \), если \ (x \ in L \) и \ (F (x) = 0 \), если \ (x \ not \ в L \). Функции с одним битом вывода называются логическими функциями , а подмножества строк называются языками . Вышеупомянутое показывает, что это два, по сути, один и тот же объект, и мы можем идентифицировать задачу определения принадлежности к \ (L \) (известную в литературе как , определяющую язык ) с задачей вычисления функции \ (F \ ).

Для каждой конкретной функции \ (F \) может быть несколько возможных алгоритмов для вычисления \ (F \).Нам будут интересны такие вопросы как:

• Может ли быть случай, что для данной функции \ (F \) не существует алгоритма для вычисления \ (F \)?

• Если есть алгоритм, какой лучший? Может ли быть, что \ (F \) «фактически невычислим» в том смысле, что каждый алгоритм для вычисления \ (F \) требует чрезмерно большого количества ресурсов?

• Если мы не можем ответить на этот вопрос, можем ли мы показать эквивалентность между различными функциями \ (F \) и \ (F '\) в том смысле, что либо они обе просты (т.е., есть быстрые алгоритмы) или они оба сложные?

• Может ли функция, которую трудно вычислить, когда-либо быть хорошей ? Можем ли мы использовать его для приложений в таких областях, как криптография?

Для этого нам необходимо математически определить понятие алгоритма , что мы и сделаем в главе 3.

Отличите функции от программ!

Вы всегда должны остерегаться возможных противоречий между спецификациями и реализациями или эквивалентным образом между математическими функциями и алгоритмами / программами .Не помогает то, что языки программирования (включая Python) используют термин «функции» для обозначения (частей) программ . Эта путаница также происходит из тысячелетней истории математики, когда люди обычно определяли функции с помощью способа их вычисления.

Например, рассмотрим функцию умножения натуральных чисел. Это функция \ (\ suremath {\ mathit {MULT}}: \ N \ times \ N \ rightarrow \ N \), которая отображает пару \ ((x, y) \) натуральных чисел в число \ (x \ cdot y \).Как мы уже упоминали, это может быть реализовано более чем одним способом:

  def mult1 (x, y):
    res = 0
    пока y> 0:
        res + = x
        у - = 1
    вернуть res

def mult2 (x, y):
    a = str (x) # представить x как строку в десятичной системе счисления
    b = str (y) # представить y как строку в десятичной системе счисления
    res = 0
    для i в диапазоне (len (a)):
        для j в диапазоне (len (b)):
            res + = int (a [len (a) -i]) * int (b [len (b) -j]) * (10 ** (i + j))
    вернуть res

печать (mult1 (12,7))
# 84
печать (mult2 (12,7))
# 84  

И mult1 , и mult2 выдают одинаковый результат при одинаковой паре входных натуральных чисел.(Хотя mult1 займет гораздо больше времени, когда числа станут большими.) Следовательно, хотя это две разные программы , они вычисляют одну и ту же математическую функцию . Это различие между программой или алгоритмом \ (A \) и функцией \ (F \), которую \ (A \) вычисляет , будет абсолютно решающим для нас в этом курсе (см. Также рисунок 2.13). ).

2.13: Функция - это отображение входов на выходы.Программа - это набор инструкций о том, как получить вывод при вводе. Программа вычисляет функцию, но это не то же самое, что функция, несмотря на популярную терминологию языка программирования.

Функция отличается от программы . Программа вычисляет функцию.

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

Мы изучим вопрос поиска (или, по крайней мере, определения границ), что такое лучший алгоритм для вычисления \ (F \) для различных интересных функций \ (F \).

Упражнения

Какой из этих объектов может быть представлен двоичной строкой?

1. Целое число \ (x \)

2. Неориентированный граф \ (G \).* \ rightarrow \ N \) такое, что \ (StN (NtS (n)) = n \) для каждого \ (n \ in \ N \).

Кодировку ASCII можно использовать для кодирования строки из \ (n \) английских букв как двоичной строки \ (7n \) бит, но в этом упражнении мы просим найти более компактное представление для строк английских строчных букв.

1. Докажите, что существует схема представления \ ((E, D) \) для строк из 26-буквенного алфавита \ (\ {a, b, c, \ ldots, z \} \) в виде двоичных строк такая, что для каждого \ (n> 0 \) и длины - \ (n \) строка \ (x \ in \ {a, b, \ ldots, z \} ^ n \), представление \ (E (x) \) представляет собой двоичную строку длиной не более \ (4.{\ lfloor 4.6n + 1000 \ rfloor} \).

2. Функция Python bz2.compress - это преобразование строк в строки, в котором для сжатия используется алгоритм без потерь (и, следовательно, один к одному ) bzip2. После преобразования в нижний регистр и сокращения пробелов и чисел текст Толстого «Война и мир» содержит \ (n = 2 517 262 \). Тем не менее, если мы запустим bz2.compress в строке текста «Война и мир», мы получим строку длиной \ (k = 6 274 768 \) бит, что составляет всего \ (2.49n \) (и, в частности, намного меньше, чем \ (4.6n \)). Объясните, почему это не противоречит вашему ответу на предыдущий вопрос.

3. Интересно, что если мы попытаемся применить bz2.compress к случайной строке , мы получим намного худшую производительность. В своих экспериментах я получил соотношение примерно \ (4,78 \) между количеством бит на выходе и количеством символов на входе. Тем не менее, можно представить, что можно было бы добиться большего и что существует компания под названием «Pied Piper» с алгоритмом, который может без потерь сжимать строку из \ (n \) случайных строчных букв до менее чем \ (4. {\ lfloor 0.* \) представляет собой представление натуральных чисел без префиксов. Определим \ (F '(o) = G (| F (o) |) F (o) \) (т.е. конкатенацию представления длины \ (F (o) \) и \ (F (o) \)).

   1. Докажите, что \ (F '\) является представлением \ (O \) без префиксов.

   2. Покажите, что мы можем преобразовать любое представление в представление без префиксов путем модификации, которая переводит строку битов \ (k \) в строку длиной не более \ (k + O (\ log k) \).

   3. Покажите, что мы можем преобразовать любое представление в представление без префиксов путем модификации, которая переводит строку битов \ (k \) в строку длиной не более \ (k + \ log k + O (\ log \ log k) \).* \) в \ (\ mathbb {N} \), где \ (\ mathbb {Z} \) - это набор \ (\ {\ ldots, -3, -2, -1,0, + 1, + 2 , + 3, \ ldots \} \) всех целых чисел.

      Библиографические примечания

      Изучение представления данных в виде строк, включая такие вопросы, как сжатие , и исправление ошибок . относится к сфере теории информации , как описано в классическом учебнике Ковер и Томас (Cover, Thomas, 2006). Представления также изучаются в области проектирования структур данных , как описано в таких текстах, как (Cormen, Leiserson, Rivest, Stein, 2009).

      Вопрос о том, следует ли представлять целые числа с первой или последней значащей цифрой, известен как представление с прямым порядком байтов и прямым порядком байтов. Эта терминология взята из занимательной и информативной статьи Коэна (Cohen, 1981) о конфликте между приверженцами обеих школ, который он сравнил с враждующими племенами в книге Джонатана Свифта «Путешествие Гулливера» . Дополнение до двух целых чисел со знаком было предложено в классическом отчете фон Неймана (von Neumann, 1945), в котором подробно описаны подходы к проектированию для компьютера с хранимой программой, хотя аналогичные представления использовались еще раньше в счетах и ​​других механических вычислительных устройствах.

      Идея о том, что мы должны отделить определение или спецификацию функции от ее реализации или вычисления , может показаться «очевидной», но математикам потребовалось довольно много времени, чтобы прийти к этой точке зрения. Исторически функция \ (F \) определялась правилами или формулами, показывающими, как получить результат из ввода. Как мы более подробно обсудим в главе 9, в 1800-х годах это несколько неформальное понятие функции начало «ломаться по швам», и в конечном итоге математики пришли к более строгому определению функции как произвольного назначения входных данных выходным.Хотя многие функции могут быть описаны (или вычислены) одной или несколькими формулами, сегодня мы не считаем это существенным свойством функций, а также допускаем функции, которые не соответствуют какой-либо «хорошей» формуле.

      Мы упоминали, что все представления действительных чисел по своей сути являются приблизительными . Таким образом, важно понять, какие гарантии мы можем предложить в отношении качества аппроксимации выходных данных алгоритма в зависимости от качества аппроксимации входных данных.Этот вопрос известен как вопрос определения численной устойчивости заданных уравнений. Веб-сайт руководства по плавающей запятой содержит подробное описание представления с плавающей запятой, а также множество способов, которыми он может незаметно выйти из строя, см. Также веб-сайт 0.30000000000000004.com.

      Даубен (Dauben, 1990) дает биографию Кантора с акцентом на развитие его математических идей. (Halmos, 1960) - классический учебник по теории множеств, включающий также теорему Кантора.Теорема Кантора также рассматривается во многих текстах по дискретной математике, в том числе (Lehman, Leighton, Meyer, 2018) (Lewis, Zax, 2019).

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

      Комментарии размещаются в репозитории GitHub с помощью приложения utteranc.es. Для комментирования требуется логин GitHub. Если вы не хотите разрешать приложению отправлять сообщения от вашего имени, вы также можете прокомментировать Проблема с GitHub для этой страницы.

      Составлено 02.09.2021 18:24:47

      Авторские права 2019, Боаз Барак.
      Это произведение под лицензией Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Международная лицензия.

      Создано с использованием pandoc и panflute с шаблонами, полученными из gitbook и bookdown.

      Глава 6: Целочисленное представление и арифметика

      Глава 6: Целочисленное представление и арифметика

      Целочисленное представление и арифметика

      ---

      Целочисленное представление
      • Бит - двоичная цифра
      • 1 байт = 8 бит
      • 1 слово = 2 байта
      • Целое число занимает два байта; может быть подписанным или неподписанным.

      Целые числа без знака

      • Может представлять целые числа от 0 до 65 535
      • В двоичном формате это от
      • Внутренне, двоичное представление десятичного значения как 16 бит.

      Целые числа со знаком

      • Необходимо зарезервировать один бит для знака.
      • Три пути:
      • Знак-величина
      • Дополнение до 1
      • Дополнение 2

      ---

      Знак - величина
      • Использует старший бит слова для представления знака.
      • 0 - положительный
      • 1 - Отрицательный.
      • Остальная часть числа закодирована в части величины

       37 = 00000000 00100101
      -37 = 10000000 00100101 

       6712 = 00011010 00111000
      -6712 = 10011010 00111000 

      • Может представлять числа от -32 767 до 32 767.
      • Но, два представления для нуля:

       0 = 00000000 00000000
      -0 = 10000000 00000000 

   4. Арифметика может быть громоздкой.

   ---

   Дополнение 1
   • Отрицательное число сохраняется как побитовое дополнение соответствующего положительного числа. количество.
   • Крайний левый бит положительного числа равен 0. Бит отрицательного числа равен 1.

    196 = 00000000 11000100
   -196 = 11111111 00111011 

   • Может представлять числа от -32 767 до 32 767.
   • Арифметика проще, чем знак-величина.
   • Но все еще есть два представления для нуля:

    0 = 00000000 00000000
   -0 = 11111111 11111111 

   ---

   Дополнение 2
   • Современный метод
   • Положительное число, представленное так же, как и другие два метода
   • Отрицательное число, полученное взятием дополнения к положительному числу до единицы и добавив 1.

    6713 = 00011000 00011101
   Композиция 1 = 11100111 11100010
   Композиция 2 = 11100111 11100011 

   • Целое число Word может представлять числа от -32 768 до 32 767.
   • Целое число байтов может представлять числа от -128 до 127.
   • Одна версия нуля:

    00000000 00000000 

   ---

   Преобразование байтового целого числа в слово
   • Расширение знака
   • Копировать знаковый бит байта во все биты старшего байта слово.

    37 = 00100101 -> 00000000 00100101
   -37 = 11011011 -> 11111111 11011011 

   5. CBW
   • преобразует подписанный байт в AL в слово в AX

   Преобразование слова целого числа в байт

   • Удалить старший байт слова. Сохраните только младший байт.
   • Имеет значение, только если исходный номер может быть представлен байтом.

   ---

   Целочисленная арифметика (сравнение единиц и двух)
   • Дополнение: просто добавьте два двоичных представления.
   • Вычитание: найти отрицательное значение одного числа, прибавить ко второму.

   Дополнение к 1 комп.

   • Сложите двоичные представления двух чисел.
   • Если есть переноска, добавьте ее обратно с правой стороны.

    51 00110011
   + (-37) + 11011010
           ----------
           1 00001101
                  +1
           ----------
       14 00001110 

   Дополнение к 2 Comp

   • Сложите двоичные представления двух чисел.
   • Не обращайте внимания на перенос.

    51 00110011
   + (-37) + 11011011
            ----------
       14 1 00001110 

   Вычитание в 2-х Comp

   ---

   Перелив
   • Если два числа имеют разные знаки, их сумма никогда не переполнится.
   • Если у них одинаковый знак, они могут переполниться.
   • Произошло переполнение, если знак результата отличается от знака добавлений.

   ---

   Сложение, вычитание, увеличение, уменьшение и отрицание

    добавить / дополнительную регистрацию / память, регистр / память / константу 

   • Оба операнда должны быть одинакового размера
   • Максимум, один операнд может быть из памяти

    инкр. / Дек. Рег. / Мем. 

   • операнды могут быть байтами или словами

    негр. Рег / мем 

   • Инвертирует байт или слово операнда

   Умножение

    mov AX, банан
   имул вишня
   mov Apple, AX 

   6. DX содержит все биты знака (надеюсь)

   Дивизия

    mov AX, банан
   cwd
   идив вишня
   mov AX, Apple 

   7. остаток находится в DX

   math - Может ли действительное число IEEE 754 "охватывать" все целые числа в пределах своего диапазона?

   Нет, не все, но существует диапазон, в котором вы можете точно представить все целые числа.

   Структура 32-битных чисел с плавающей запятой

   32-битный тип с плавающей запятой использует

   • 1 бит для знака
   • 8 бит для экспоненты
   • 23 бита для дроби (подразумевается ведущая 1)

   Представляющие числа

   По сути, у вас есть номер в форме

     (-) 1.xxxx_xxxx_xxxx_xxxx_xxxx_xxx (двоичный)
     

   , который затем вы сдвигаете влево / вправо с (несмещенной) экспонентой.

   Чтобы он представлял целое число, требующее n бит, вам необходимо сдвинуть его на n-1 бит влево. (Все x es за пределами числа с плавающей запятой просто равны нулю)

   Представление целых 24-битных чисел

   Легко видеть, что мы можем представить все целые числа, требующие 24 бита (и меньше)

     1xxx_xxxx_xxxx_xxxx_xxxx_xxxx.0 (несмещенная экспонента = 23)
     

   , поскольку мы можем установить x es по желанию либо на 1 , либо на 0 .24 - 1 = 16777215

   Следующее большее целое число - 1_0000_0000_0000_0000_0000_0000 . Таким образом, нам нужно 25 бит.

   Представление целых чисел с 25 битами

   Если вы попытаетесь представить 25-битное целое число (несмещенная экспонента = 24), числа будут иметь следующий вид:

     1_xxxx_xxxx_xxxx_xxxx_xxxx_xxx0.0
     

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

   Максимум найден

   Мы можем представить `1_0000_0000_0000_0000_0000_0000 в форме 1_xxxx_xxxx_xxxx_xxxx_xxxx_xxx0.0 , просто назначив 1 всем x es. Следующее большее целое число: 1_0000_0000_0000_0000_0000_0001 . Легко видеть, что это число не может быть представлено точно, потому что форма не позволяет нам установить последнюю цифру на 1 : это всегда 0 .

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

   Диапазон, в котором могут быть представлены все целые числа (включая границы)

   • 2 ²⁴ как верхняя граница
   • -2 ²⁴ как нижняя граница

   Структура 64-битных чисел с плавающей запятой

   • 1 бит для знака
   • 11 разрядов экспоненты
   • 52 дробных бита

   Диапазон, в котором могут быть представлены все целые числа (включая границы)

   • 2 ⁵⁴ как верхняя граница
   • -2 ⁵⁴ как нижняя граница

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

   Примечание : Это не означает, что это все целых чисел, которые мы можем представить, но это дает вам диапазон, в котором вы можете представить всех целых чисел. За пределами этого диапазона мы можем представить только степень двойки, умноженную на целое число из указанного диапазона.

   Комбинаторный аргумент

   Просто убеждая себя в том, что 32-битные числа с плавающей запятой не могут представлять все целые числа, которые может представлять 32-битное целое число, нам даже не нужно смотреть на структуру чисел с плавающей запятой.

   1. Используя 32 бита, мы можем представить 2 ³² различных вещей. Не больше, не меньше.
   2. 32-битное целое число использует все эти "вещи" для представления чисел (попарно различных).
   3. 32-битное число с плавающей запятой может представлять по крайней мере одно число с дробной частью.

   Таким образом, 32-битное число с плавающей запятой не может представлять это дробное число в дополнение ко всем 2 ³² целым числам.