МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ИСПОЛЬЗОВАНИЕ СИСТЕМ СЧИСЛЕНИЯ

II Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ИСПОЛЬЗОВАНИЕ СИСТЕМ СЧИСЛЕНИЯ

Бураков В.И. 1
1МКОУ Селявинская ООШ
Чепрасов Д.Н. 1
1МКОУ Селявинская ООШ
Автор работы награжден дипломом победителя II степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение.

На ранних ступенях развития цивилизации люди практически не умели считать. Они отличали друг от друга совокупности двух и трех предметов; любое множество, включавшее большее количество объектов, объединялась словом «много». Позднее стали появляться новые слова для обозначения количества чего-либо(4,5,6,7). Число 7 достаточно долгое время обозначало неопределенно большое количество. Данный факт отражен в русских пословицах, например, «Семь раз отмерь - один отрежь», «Семь бед - один ответ». Огромную роль при счете позднее стали играть пальцы человека. Поэтому неудивительно, что вновь возникавшие названия «больших» чисел строились на основе числа 10 – по количеству пальцев на руках.

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

Цель нашего исследования: изучить основные сферы применения систем счисления в современной жизни.

Для достижения цели нашего исследования были поставлены следующие задачи:

  1. Рассмотреть основные определения, связанные с системами счисления, и дать краткие исторические справки по их появлению

  2. Изучить применение систем счисления в информатике и математике

  3. Исследовать возможности применения систем счисления для решения прикладных задач.

Необходимо отметить, что в математике системы счисления изучаются подразделом «Теория чисел» и системы счисления изучены обширно.

Методологической основой исследования явились следующие источники: методическое пособие по теоретическим основам информатики Кубрякова Е.А. и книга Г.Б. Гашкова «Применение систем счисления».

§ 1. Основные понятия и история развития систем счисления

Для записи и выполнения математических операций над величинами необходима некоторая система обозначений. Такая система обозначений и называется системой счисления.

Система счисления - это знаковая система, в которой числа записываются по определенным правилам с помощью символов некоторого алфавита, называемых цифрами. Количество символов, входящих в алфавит системы счисления называют основанием системы счисления [2].

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

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

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

  • Цифры I, X, C, M можно использовать в записи числа не более 3 раз подряд, а V, L, D не более одного раза.

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

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

Таким образом, данные правила ограничивают возможное максимальное число, которое можно записать в римской системе счисления. Таким числом является MMMCMXCIX (1000+1000+1000-100+1000-10+100-1+10=3999). Судя по всему, этой величины вполне хватало для практических нужд древних римлян [2].

Примером непозиционной системы счисления может послужить славянская система счисления. В этой системе счисления нумерации для записи чисел использовались все буквы алфавита, правда, с некоторым нарушением алфавитного порядка. Буквам старой славянской азбуки были присвоены цифровые значения: от 1 до 10, затем через 10 до 100 и через 100 до 1000. Используя не более трех букв можно было записать любое натуральное число от 1 до 1110 (Таблица 1) [4].

Таблица 1. Славянская система счисления

Символ

Название

Обозначенная цифра

Символ

Название

Обозначенная цифра

 

Аз

1

 

Мыслите

40

 

Ведь

2

 

Наш

50

 

Глаголь

3

 

Кси

60

 

Добро

4

 

Он

70

 

Есть

5

 

Покой

80

 

Зело

6

 

Черви

90

 

Земля

7

 

Рцы

100

 

Иже

8

 

Слово

200

 

Фита

9

 

Твёрдо

300

 

И

10

 

Ук

400

 

Како

20

 

Ферт

500

 

Люди

30

 

Хер

600

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

Рассматривая произвольную систему счисления с основанием n>1, отметим, что число позиционных систем бесконечно. Для систем с основанием, не превышающем число 10, алфавит системы счисления будет состоять из соответствующих первых n цифр десятичной системы счисления начиная с 0. Для систем с основаниями, превышающимися 10, необходимо предложить способ записи каждой цифры в виде одного знака. Как правило, для этого используют букву латинского алфавита. В математическом отношении давно найден простой выход – каждая цифра, занимающая больше одного разряда, просто записывается в скобках. Например число A4F в шестнадцатеричной системе может быть записано как (10)4(15).

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

Для деления числа на основание системы нужно отбросить последнюю цифру (целочисленное деление) или же перенести разделитель на одну позицию влево [2].

§ 2. Перевод чисел из одной позиционной системы в другую.

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

Возьмем для примера число 257,45 в десятичной система счисления и представим его в следующем виде:

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

где q - основание системы счисления, n - число разрядов целой части числа, m - число разрядов дробной части числа, ai - цифра числа, Aq - само число [3].

Запись расширенной формы числа в своей основе имеет так называемую схему Горнера. Схема Горнера это алгоритм для вычисления частного и остатка от деления многочлена p(x) на х−a.

Перевод числа из n-ричной системы счисления в десятичную осуществляется записью и вычислением развернутой формы числа. Например, для перевода числа 403,155 в десятичную записываем развернутую форму числа:

=103,2810

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

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

Пример: 20710=X5=13125

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

Пример: 61210=X15=2AC15

Перевод дробной части осуществляется путем последовательного выполнения операций: умножения числа на основание системы, в которую выполняется перевод, и выделения в полученном результате целой части. Процесс продолжается до тех пор, пока после выделения целой части не останется число 0. Если процесс невозможно завершить, то говорят о том, что он выполнен с определенной степенью точности [2].

Пример 0,62510=X2=0,1012

§ 3. Использование систем счисления в технике и жизни.

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

Некоторые идеи, лежащие в основе двоичной системы, по существу были известны в Древнем Китае и Древней Индии. Пропагандистом двоичной системы был знаменитый Г. В. Лейбниц. Он отмечал особую простоту алгоритмов арифметических действий в двоичной арифметике в сравнении с другими системами и придавал ей определённый философский смысл. Известный современный математик Т. Данциг о нынешнем положении дел сказал: «Увы! То, что некогда возвышалось как монумент, очутилось в чреве компьютера». Причина такой метаморфозы не только уникальная простота таблицы умножения в двоичной системе, но и особенности физических принципов, на основе которых работает элементная база современных ЭВМ.

Возьмите, к примеру, двухполюсный электронный прибор - диод. Он может находиться только в двух состояниях: или проводит электрический ток - «открыт», или не проводит его - «заперт». По точно такому же принципы работают и триггер, имеющий два устойчивых состояния, и запоминающие элементы. Почему же не использовать тогда двоичную систему счисления? Ведь в ней только две цифры: 0 и 1. А это удобно для работы на электронной машине. И новые машины стали считать с помощью 0 и 1.

Примерами практического применения двоичной системы счисления в современной технике могут послужить пленочные фотокамеры и шрих-коды.

Как автоматические фотоаппараты узнают светочувствительность заправленной в них плёнки? Её измеряют в некоторых единицах, и вся выпускаемая сейчас в мире плёнка имеет одно из 24 стандартных значений светочувствительности. Эти значения кодируются некоторым стандартным образом наборами из нулей и единиц, естественно, длины 5. На поверхности кассеты для плёнки нанесены 12 квадратиков чёрного или серебристого цвета, образующих прямоугольник 2×6. Квадратики его верхней части мысленно занумеруем от 1 до 6, начиная слева. Квадратики нижней части аналогично занумеруем от 7 до 12. Серебристые квадратики — это просто металлическая поверхность кассеты, она проводит ток, который с контакта внутри аппарата подаётся на первый квадрат (он всегда серебристый). Чёрные квадраты покрыты краской, не проводящей ток.

Когда плёнка вставляется в фотоаппарат, шесть его контактов соприкасаются с шестью первыми квадратиками, и с квадратиков со 2-го по 6-й снимается информация — нуль, если квадратик чёрный и ток по соответствующему контакту не идёт, и единица в противном случае. Вся информация о светочувствительности плёнки заключена в квадратиках со 2-го по 6-й. В остальных квадратиках заключена информация о числе кадров в плёнке и т. п.

Ещё на поверхности кассеты можно увидеть штрих-код. Это так называемый универсальный код продукта, он сейчас ставится на всех продаваемых товарах.

Нужен он только для автоматического занесения информации в кассовый аппарат. Сам штрих-код состоит из тридцати чёрных полос переменной толщины, разделённой промежутками тоже переменной толщины. Толщина полос может принимать четыре значения от самой тонкой до самой толстой. Такую же толщину могут иметь и промежутки. Когда по сканеру проводят штрих-кодом, он воспринимает каждую чёрную полоску как последовательность единиц длины от одной до четырёх, и также воспринимает промежутки между полосами, но при этом вместо единиц сканер видит нули. Полностью весь штрих-код сканер воспринимает как последовательность из 95 цифр 0 или 1 (их давно уже принято называть битами). Что же содержит этот код? Он кодирует 13-разряд-ное десятичное число, совершенно открыто написанное под самим штрих-кодом. Если сканер не смог распознать штрих-код, то это число кассир вводит в аппарат вручную. Штрих-код нужен лишь для облегчения распознавания сканером изображения. Распознавать цифры, к тому же повёрнутые боком, может только сложная программа распознавания на универсальном компьютере, а не кассовый аппарат.

Какую же информацию содержит это 13-значное число? Этот вопрос к математике никакого отношения не имеет. Первая цифра задаёт тип товара, например, у товаров переменного веса она равна 2.Следующие пять цифр — это код производителя, а следующие пять цифр — код самого продукта в принятой этим производителем кодировке. Последняя цифра — это код проверки. Он однозначно вычисляется по предыдущим 12 цифрам следующим образом. Нужно сложить все цифры с нечётными номерами, утроить сумму, к ней прибавить сумму оставшихся цифр, а полученный результат вычесть из ближайшего (большего) кратного 10 числа.

А вот 95-битный код, соответствующий штрих-коду, более интересен. Он содержит в себе только указанное 12-значное число (контрольная цифра в самом штрих-коде не содержится), но с большой избыточностью. Первые три бита в нём, так же, как и последние — это всегда 101. Они нужны только для того, чтобы сканер смог определить ширину полосы, соответствующей одному биту (ведь размеры штрих-кода на разных упаковках могут быть разными) и настроиться на распознавание. В центре кода всегда стоит комбинация 01010, а левая и правая части кода состоят каждая из шести блоков по семь битов и содержат информацию о левых шести и правых шести из данных 12 десятичных цифр. Центральная комбинация позволяет, в частности, отличать поддельные или плохо напечатанные коды. Цифры 13-значного кода кодируются в левой и правой частях штрих-кода по-разному. В левой половине каждая цифра кодируется семёркой битов, начинающейся с 0 и заканчивающейся 1.

Цифры 13-значного кода кодируются в левой и правой частях штрих-кода по-разному. В левой половине каждая цифра кодируется семёркой битов, начинающейся с 0 и заканчивающейся 1, согласно таблице, представленной ниже.

В правой половине каждая цифра кодируется семёркой битов, начинающейся с 1 и заканчивающейся 0, которая получается из вышеприведённой, если в ней нули заменить на единицы и единицы на нули (это переход к дополнительному коду). Можно заметить, что каждый из кодов в таблице содержит нечётное число единиц и ровно две группы рядом стоящих единиц и ровно две группы рядом стоящих нулей. Это означает, что каждая цифра соответствует двум соседним полосам на штрих-коде. Но более важно то обстоятельство, что все десять кодов таблицы, будучи прочитанными не слева направо, а справа налево, будут отличаться от любого из кодов таблицы, прочитанного правильным образом. Очевидно, таблица для правой половины кода обладает теми же свойствами, только число единиц в каждом коде чётное. Такая избыточная (не четырёхбитовая, а семибитовая) таблица кодов нужна для того, чтобы сканер мог правильно прочитать штрих-код и в случае, когда код направляют в него «вверх ногами». Как сканер может отличать одно направление от другого? По чётности или нечётности числа единиц в первом же прочитанном семибитовом блоке, идущем после комбинации 101. При правильном направлении оно будет нечётным, а при обратном направлении — чётным. Перепутать же коды, прочитанные слева, и коды, прочитанные справа, согласно свойству таблицы, невозможно. Если же в каком-то из семибитовых блоков нарушено правильное чередование нулей и единиц в первом и последнем битах или ему не соответствует чётность числа единиц, то штрих-код признаётся поддельным или плохо пропечатанным [1].

Отметим также и тот факт, что в основе таких известных вещей как шрифт Брайля и азбука Морзе также лежит двоичная система счисления.

Шрифт Брайля был создан двенадцатилетним слепым мальчиком по имени Луи. В нём символы языка (буквы, знаки препинания и цифры) кодируются комбинациями от одной до шести выпуклых точек, расположенных в виде таблицы стандартного размера с тремя строчками и двумя столбцами. Элементы (точки) таблицы нумеруются числами 1, 2, 3 в первом столбце сверху вниз и 4, 5, 6 во втором столбце сверху вниз. Каждая точка либо продавливается специальной машинкой (или даже шилом) или остаётся целой. Всего различных способов продавить выпуклые точки в этой таблице 64 (в том числе и тот, в котором ни одна из точек не вдавлена).

Азбука Морзе изобретена Сэмюэлем Морзе. Она сопоставляет каждой букве алфавита последовательность из точек и тире. Естественней всего использовать такие последовательности длины 6, их всего 64 и хватит даже на русский алфавит. Но Морзе понимал, что длину сообщения желательно уменьшить, насколько возможно, поэтому он решил использовать последовательности длины не более 4, их всего 2+4+8+16=30. В русском алфавите пришлось не использовать буквы «э» и «ё» и отождествить мягкий и твёрдый знаки. Кроме того, наиболее часто используемым буквам он предложил давать самые короткие коды, чтобы уменьшить среднюю длину передаваемого сообщения [1].

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

Простейший из них следующий: остаток от деления некоторого числа на равен остатку от деления на числа, записанного последними его n цифрами. Аналогичный признак справедлив и для любого и любого числа вида . Чуть более сложен в применении признак делимости на 9: сумма цифр данного числа имеет тот же остаток от деления на 9, что и само число. Этот же признак справедлив и для делимости на 3.

Подобный же признак можно предложить и для делимости на число 9...9, состоящее из n девяток: надо разбить испытуемое число на n-разрядные блоки, начиная с младших разрядов, и всех их сложить (блок, образованный старшими разрядами, может быть короче); у полученного числа будет тот же остаток от деления, что и у исходного. Так как 99 делится на 11, то таким способом можно найти и остаток от деления на 11. Учитывая, что 999 делится на 111 и, следовательно, на 37, получаем признаки делимости на эти числа. Но есть более эффективный признак делимости на 11: надо складывать цифры числа, начиная с младших, чередуя знаки (первая цифра берётся со знаком плюс) — полученное число имеет тот же остаток от деления на 11, что и исходное.

Аналогичный признак делимости имеется и для числа 10...01, запись которого, кроме двух единиц, содержит n нулей. Испытуемое число разбивается на (n+1)-разрядные блоки, начиная с младших разрядов (блок, образованный старшими разрядами, может быть короче), и все они складываются с чередующимися знаками (первое число берётся со знаком плюс). Полученный результат имеет тот же остаток от деления, что и испытуемое число. Поскольку 1001=11·7·13, мы попутно получаем таким путём признаки делимости на 7, 13, 91, 77, 143.

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

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

Признаки делимости могут помочь в нахождении ошибки при выполнении умножения больших чисел. Простейший из способов контроля — проверка по модулю 9 . Этому способу обучали ещё в средневековых университетах: у обоих множителей находятся остатки от деления на 9, потом исходные числа перемножаются и у результата опять находится остаток от деления на 9, который сравнивается с остатком от деления на 9 произведения исходных чисел, подлежащего проверке. Если остатки разные, то произошла ошибка. Если известно, что ошибка только в одном разряде, то можно точно указать величину ошибки, но не её положение. В случае совпадения результатов остаётся возможность одной ошибки типа замены 0 на 9 или наоборот, а также нескольких ошибок. В этом случае можно провести ещё аналогичную проверку по модулю 11, которая или подтвердит существование ошибки указанного вида, или установит наличие нескольких ошибок (или их отсутствие) [1].

Заключение

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

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

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

Как уже говорилось выше, системы счисления используются при возникновении потребности в расчетах. Но одной лишь математикой их применение не ограничено. В ходе исследования было выявлено, что числа в двоичной системе используются, например, в фотокамерах и штрих-коде. Также на основе двоичных чисел были созданы азбука Морзе и шрифт Брайля.

Но все-таки это понятие математическое. В ходе нашей работы было изучено использование систем счисления для формулирования признаков делимости.

Список использованной литературы

  1. Гашков С.Б. Применение систем счисления. / С.Б. Гашков. – Москва : Издательство Московского центра непрерывного математического образования, 2004. – 54 с.

  2. Кубряков Е.А. Элементы теории информации и ее представления в памяти компьютера: учебно-методическое пособие по курсу «Теоретические основы информатики» Е.А. Кубряков. – Воронеж : ВГПУ, 2009. – 71 с.

  3. Студопедия.орг / [сайт]. - http://studopedia.org/8-67729.html

  4. Учителям информатики и математики и их любознательным ученикам / И. Деменев [сайт]. – URL: http://comp-science.narod.ru/Demenev/files/history.htm

Просмотров работы: 2956