Лекция 3. Системы счисления. Элементы комбинаторики

обратно

План

1. Системы счисления

1.1. Числа

1.2. Обозначения чисел и история систем счисления

1.3. Понятие системы счисления

1.4. Двоичная система счисления

1.5. Системы счисления, родственные двоичной

2. Элементы комбинаторики

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

Числа

Интуитивное представление о числе, по–видимому, так же старо, как и само человечество, хотя с достоверностью проследить все ранние этапы его развития в принципе невозможно. Прежде чем человек научился считать или придумал слова для обозначения чисел, он, несомненно, владел наглядным, интуитивным представлением о числе, позволявшим ему различать одного человека и двух людей или двух и многих людей. То, что первобытные люди сначала знали только “один”, “два” и “много”, подтверждается тем, что в некоторых языках, например в греческом, существуют три грамматические формы: единственного числа, двойственного числа и множественного числа. Позднее человек научился делать различия между двумя и тремя деревьями и между тремя и четырьмя людьми. Счет изначально был связан с вполне конкретным набором объектов, и самые первые названия чисел были прилагательными. Например, слово “три” использовалось только в сочетаниях “три дерева” или “три человека”; представление о том, что эти множества имеют между собой нечто общее – понятие троичности – требует высокой степени абстракции. О том, что счет возник раньше появления этого уровня абстракции, свидетельствует тот факт, что слова “один” и “первый”, равно как “два” и “второй”, во многих языках не имеют между собой ничего общего, в то время как лежащие за пределами первобытного счета “один”, “два”, “много”, слова “три” и “третий”, “четыре” и “четвертый” ясно указывают на взаимосвязь между количественными и порядковыми числительными.

Названия чисел, выражающие весьма абстрактные идеи, появились, несомненно, позже, чем первые грубые символы для обозначения числа объектов в некоторой совокупности. В глубокой древности примитивные числовые записи делались в виде зарубок на палке, узлов на веревке, выложенных в ряд камешков, причем подразумевалось, что между пересчитываемыми элементами множества и символами числовой записи существует взаимно однозначное соответствие. Но для чтения таких числовых записей названия чисел непосредственно не использовались. Ныне мы с первого взгляда распознаем совокупности из двух, трех и четырех элементов; несколько труднее распознаются на взгляд наборы, состоящие из пяти, шести или семи элементов. А за этой границей установить на глаз их число практически уже невозможно, и нужен анализ либо в форме счета, либо в определенном структурировании элементов. Счет на бирках, по–видимому, был первым приемом, который использовался в подобных случаях: зарубки на бирках располагались определенными группами подобно тому, как при подсчете избирательных бюллетеней их часто группируют пачками по пять или десять штук. Очень широко был распространен счет на пальцах, и вполне возможно, что названия некоторых чисел берут свое начало именно от этого способа подсчета.

Важная особенность счета заключается в связи названий чисел с определенной схемой счета. Например, слово “двадцать три” – не просто термин, означающий вполне определенную (по числу элементов) группу объектов; это термин составной, означающий “два раза по десять и три”. Здесь отчетливо видна роль числа десять как коллективной единицы или основания; и действительно, многие считают десятками, потому что, как отметил еще Аристотель, у нас по десять пальцев на руках и на ногах. По той же причине использовались основания пять или двадцать. На очень ранних стадиях развития истории человечества за основания системы счисления принимались числа 2, 3 или 4; иногда для некоторых измерения или вычислений использовались основания 12 и 60.

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

1.2. Обозначения чисел и история систем счисления Подробнее> >

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

Система счисления – очень сложное понятие.

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

Известно множество способов представления чисел. В любом случае число изображается символом или группой символов (словом) некоторого алфавита. Будем называть такие символы цифрами. Для представления чисел используются непозиционные и позиционные системы счисления.

В непозиционных системах каждая цифра имеет свой вес и ее значение не зависит от положения в числе – от позиции. Пример – римская система. Скажем, число 76 в этой системе выглядит так:

LXXVI, где L=50, X=10, V=5, I=1.

Как видно цифрами здесь служат латинские символы.

В позиционных системах значения цифр зависят от их положения (позиции) в числе.

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

В любой позиционной системе число может быть представлено в виде многочлена.

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

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

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

XXXV = 10+10+10+5 = 35; CCXIX = 100+100+10–1+10 = 219;

Во втором типе каждая цифра может иметь разные значения в зависимости от своего местоположения в числе:

(иероглифы по порядку: 2, 1000, 4, 100, 2, 10, 5)

Здесь дважды использован иероглиф “2”, и в каждом случае он принимал разные значения “2000” и “20”.

2´ 1000 + 4´ 100+2´ 10+5 = 2425

Для аддитивной (“добавительной”) системы нужно знать все цифры-символы с их значениями (их бывает до 4-5 десятков), и порядок записи. Например, в Латинской записи если меньшая цифра записана перед большей, то производится вычитание, а если после, то сложение (IV = (5–1) = 4; VI = (5+1) = 6).

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

Основанием системы счисления называется количество цифр и символов, применяющихся для изображения числа. Например р=10.

Определить основание очень легко, нужно только пересчитать количество значащих цифр в системе. Если проще, то это число, с которого начинается второй разряд у числа. Мы, например, используем цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Их ровно 10, поэтому основание нашей системы счисления тоже 10, и система счисления называется “ десятичная ”. В вышеприведенном примере используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (вспомогательные 10, 100, 1000, 10000 и т. д. не в счет). Основных цифр здесь тоже 10, и система счисления – десятичная.

База системы — это последовательность цифр, используемых для записи числа. Ни в одной системе нет цифры, равной основанию системы.

Как можно догадаться, сколько есть чисел, столько же может быть и оснований систем счисления. Но используются только самые удобные основания систем счисления. Как вы думаете, почему основание самой употребительной человеческой системы счисления 10? Да, именно потому, что на руках у нас 10 пальцев. “Но на одной то руке всего пять пальцев” – скажут некоторые и будут правы. История человечества знает примеры пятеричных систем счисления. “А с ногами – двадцать пальцев” – скажут другие, и будут тоже абсолютно правы. Именно так считали индейцы Майя. Это даже видно по их цифрам.

Подробнее> >

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

Двоичная система счисления является основной системой представления информации в памяти компьютера.

В этой системе счисления используются цифры: 0, 1.

Пример:

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

таким образом любое трехзначное число в десятичной системе можно представить:

где a, b, c цифры от 0 до 9 (горизонтальная линия над буквами показывает, что это именно цифры a, b, c, а не произведение чисел a, b, c).

Аналогично для любого трехзначного (трехразрядного) числа в двоичной системе счисления можно записать:

где a, b, c цифры 0 и 1.

Переведем число 12, записанное в десятичной системе счисления, в число, записанное в двоичной системе счисления.

– 4-х разрядное двоичное число.

В двоичной системе счисления всего две цифры, называемые двоичными (binary digits). Сокращение этого наименования привело к появлению термина бит, ставшего названием разряда двоичного числа. Веса разрядов в двоичной системе изменяются по степеням двойки. Поскольку вес каждого разряда умножается либо на 0, либо на 1, то в результате значение числа определяется как сумма соответствующих значений степеней двойки. Если какой–либо разряд двоичного числа равен 1, то он называется значащим разрядом. Запись числа в двоичном виде намного длиннее записи в десятичной системе счисления.

Предыдущая 1 2 345 6 7 8 9 10 11 12 13 Следующая