Система счисления

Системы счисления в культуре
Индо-арабская
Арабская; Тамильская; Бирманская	Кхмерская; Лаосская; Монгольская; Тайская
Восточноазиатские
Китайская; Японская; Сучжоу; Корейская	Вьетнамская; Счётные палочки
Алфавитные
Абджадия; Армянская; Ариабхата; Кириллическая; Греческая	Грузинская; Эфиопская; Еврейская; Акшара-санкхья
Другие
Вавилонская; Египетская; Этрусская; Римская; Дунайская	Аттическая; Кипу; Майяская; Эгейская; Символы КППУ
Позиционные
	2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 60
	Нега-позиционная
	Симметричная
Смешанные системы
	Фибоначчиева
Непозиционные
	Единичная (унарная)

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

Система счисления:

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

Системы счисления подразделяются на позиционные, непозиционные и смешанные.

Позиционные системы счисления

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

Под позиционной системой счисления обычно понимается $b$ -ричная система счисления, которая определяется целым числом $b>1$ , называемым основанием системы счисления. Целое число без знака $x$ в $b$ -ричной системе счисления представляется в виде конечной линейной комбинации степеней числа $b$ :

x=\sum _{k=0}^{n-1}a_{k}b^{k}

, где

a_{k}

— это целые числа, называемые цифрами, удовлетворяющие неравенству

0\leq a_{k}\leq (b-1)

.

Каждая степень $b^{k}$ в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя $k$ (номером разряда). Обычно, в ненулевых числах $x$ , левые нули опускаются.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число $x$ записывают в виде последовательности его $b$ -ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

x=a_{n-1}a_{n-2}\dots a_{0}.

Например, число сто три представляется в десятичной системе счисления в виде:

103=1\cdot 10^{2}+0\cdot 10^{1}+3\cdot 10^{0}.

Наиболее употребляемыми в настоящее время позиционными системами являются:

2 — двоичная (в дискретной математике, информатике, программировании);
3 — троичная;
8 — восьмеричная;
10 — десятичная (используется повсеместно);
12 — двенадцатеричная (счёт дюжинами);
13 — тринадцатеричная;
16 — шестнадцатеричная (используется в программировании, информатике);
60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

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

Смешанные системы счисления

Смешанная система счисления является обобщением $b$ -ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел $\{b_{k}\}_{k=0}^{\infty }$ , и каждое число $x$ в ней представляется как линейная комбинация:

x=\sum _{k=0}^{n-1}a_{k}b_{k}

, где на коэффициенты

a_{k}

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

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

В зависимости от вида $b_{k}$ как функции от $k$ смешанные системы счисления могут быть степенными, показательными и т. п. Когда $b_{k}=b^{k}$ для некоторого $b$ , смешанная система счисления совпадает с показательной $b$ -ричной системой счисления.

Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина « $d$ дней, $h$ часов, $m$ минут, $s$ секунд» соответствует значению $d\cdot 24\cdot 60\cdot 60+h\cdot 60\cdot 60+m\cdot 60+s$ секунд.

Факториальная система счисления

В факториальной системе счисления основаниями являются последовательность факториалов $b_{k}=k!$ , и каждое натуральное число $x$ представляется в виде:

x=\sum _{k=1}^{n}d_{k}k!

, где

0\leq d_{k}\leq k

.

Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: число, на единицу меньшее номера (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе i! будет обозначать число инверсий для элемента i+1 в том множестве, в котором производятся перестановки (число элементов меньших i+1, но стоящих правее его в искомой перестановке)

Пример: рассмотрим множество перестановок из 5 элементов, всего их 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём 101-ую перестановку: 100 = 4!*4 + 3!*0 + 2!*2 + 1!*0 = 96 + 4; положим ti — коэффициент при числе i!, тогда t4 = 4, t3 = 0, t2 = 2, t1 = 0 , тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, 101-я перестановка будет иметь вид: (5,3,1,2,4) Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.

Фибоначчиева система счисления

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число $n$ в ней представляется в виде:

n=\sum _{k}f_{k}F_{k}

, где

F_{k}

— числа Фибоначчи,

f_{k}\in \{0,1\}

, при этом в коэффициентах

f_{k}

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

Непозиционные системы счисления

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

Биномиальная система счисления

Представление, использующее биномиальные коэффициенты

x=\sum _{k=1}^{n}{c_{k} \choose k}

, где

0\leq c_{1}<c_{2}<\dots <c_{n}

.

Система остаточных классов (СОК)

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей $(m_{1},m_{2},\dots ,m_{n})$ с произведением $M=m_{1}\cdot m_{2}\cdot \dots \cdot m_{n}$ так, что каждому целому числу $x$ из отрезка $[0,M-1]$ ставится в соответствие набор вычетов $(x_{1},x_{2},\dots ,x_{n})$ , где

x\equiv x_{1}{\pmod {m_{1}}};

x\equiv x_{2}{\pmod {m_{2}}};

…

x\equiv x_{n}{\pmod {m_{n}}}.

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка $[0,M-1]$ .

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в $[0,M-1]$ .

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям $(m_{1},m_{1}\cdot m_{2},\dots ,m_{1}\cdot m_{2}\cdot \dots \cdot m_{n-1})$ .

Система счисления Штерна–Броко

Система счисления Штерна–Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна–Броко.

Системы счисления разных народов

Единичная система счисления

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

Пятеричная система счисления (Счёт на пятки́)

Существовал в России. Применялся в народе как минимум до конца XVIII - начала XIX вв. Так у Ершова (в "Коньке-горбунке") Иван считает в пятеричной (на пятки́), а более просвещённый царь - переводит уже в десятеричную:

                                  «Два-пять шапок серебра». —
                                  «То есть, это будет десять»^[1].

Древнеегипетская система счисления

Древнеегипетская десятичная непозиционная система счисления возникла во второй половине третьего тысячелетия до н. э. Для обозначения чисел 0, 1, 10, 10², 10³, 10⁴, 10⁵, 10⁶, 10⁷ использовались специальные цифры. Числа в египетской системе счисления записывались как комбинации этих цифр, в которых каждая из цифр повторялась не более девяти раз. Значение числа равно простой сумме значений цифр, участвующих в его записи.^[2]

Вавилонская система счисления

Алфавитные системы счисления

Алфавитными системами счисления пользовались древние армяне, грузины, греки (ионическая система счисления), арабы (абджадия), евреи (см. гематрия) и другие народы Ближнего Востока. В славянских богослужебных книгах греческая алфавитная система была переведена на буквы кириллицы.^[2]

Еврейская система счисления

Еврейская система счисления в качестве цифр использует 22 буквы еврейского алфавита. Каждая буква имеет своё числовое значение от 1 до 400 (см. так же Гематрия). Ноль отсутствует. Цифры, записанные таким образом, наиболее часто можно встретить в нумерации лет по иудейскому календарю.

Греческая система счисления

Римская система счисления

Каноническим примером почти непозиционной системы счисления является римская, в которой в качестве цифр используются латинские буквы:
I обозначает 1,
V — 5,
X — 10,
L — 50,
C — 100,
D — 500,
M — 1000

Например, II = 1 + 1 = 2
здесь символ I обозначает 1 независимо от места в числе.

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

IV = 4, в то время как:
VI = 6

Система счисления майя

Майя использовали 20-ричную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчётов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

Для записи основными знаками были точки (единицы) и отрезки (пятёрки).

Кипу инков

Прообразом баз данных, широко использовавшихся в Центральных Андах (Перу, Боливия) в государственных и общественных целях в I—II тысячелетии н. э., была узелковая письменность Инков — кипу, состоявшая как из числовых записей десятичной системы^[3], так и не числовых записей в двоичной системе кодирования^[4]. В кипу применялись первичные и дополнительные ключи, позиционные числа, кодирование цветом и образование серий повторяющихся данных^[5]. Кипу впервые в истории человечества использовалось для применения такого способа ведения бухгалтерского учёта как двойная запись^[6].

См. также

Примечания

↑ http://www.books.kostyor.ru/tale91.html
↑ ¹ ² Системы счисления. Как считали в Древней Руси. Алфавитные системы счисления.
↑ Ordish George, Hyams, Edward. The last of the Incas: the rise and fall of an American empire. — New York: Barnes & Noble, 1996. — С. 80. — ISBN 0-88029-595-3.
↑ Experts 'decipher' Inca strings (неопр.). Архивировано 18 августа 2011 года.
↑ Carlos Radicati di Primeglio, Gary Urton. Estudios sobre los quipus. - стр.49 (неопр.).
↑ Dale Buckmaster (1974). "The Incan Quipu and the Jacobsen Hypothesis". Journal of Accounting Research. 12 (1): 178–181. Дата обращения: 24 декабря 2009.

Ссылки

Имеется викиучебник по теме «Системы счисления»

Гашков С. Б. Системы счисления и их применение. — М.: МЦНМО, 2004. — (Библиотека «Математическое просвещение»).
Фомин С. В. Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике).
Яглом И. Системы счисления // Квант. — 1970. — № 6. — С. 2-10.
Цифры и системы счисления. Онлайн Энциклопедия Кругосвет.
Стахов А. Роль систем счисления в истории компьютеров.
Микушин А. В. Системы счисления. Курс лекций "Цифровые устройства и микропроцессоры"
Butler J. T., Sasao T. Redundant Multiple-Valued Number Systems В статье рассмотрены системы счисления, использующие цифры больше единицы и допускающие избыточность в представлении чисел

[1] ttp://www.books.kostyor.ru/tale91.html

[lukped-2] ¹ ² Системы счисления. Как считали в Древней Руси. Алфавитные системы счисления.

[3] Ordish George, Hyams, Edward. The last of the Incas: the rise and fall of an American empire. — New York: Barnes & Noble, 1996. — С. 80. — ISBN 0-88029-595-3.

[4] Experts 'decipher' Inca strings (неопр.). Архивировано 18 августа 2011 года.

[5] Carlos Radicati di Primeglio, Gary Urton. Estudios sobre los quipus. - стр.49 (неопр.).

[autogenerated1-6] Dale Buckmaster (1974). "The Incan Quipu and the Jacobsen Hypothesis". Journal of Accounting Research. 12 (1): 178–181. Дата обращения: 24 декабря 2009.

[1]

[2]

[3]

[4]

[5]

[6]

Система счисления

Содержание

Позиционные системы счисления