Кузин - Логические основы

Глава I. Информация и данные

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

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

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

Проблема 4. Кодирование информации: конструирование формальных языков и формальных кодов, обозначающих характеристики объектов реального мира; создание наборов данных для обозначения конкретных объектов реального мира с целью обработки информации об этих объектах.

1.1.Контрольные вопросы

1.Понятие концептуального класса и элемента концептуального клас-

са.

2.Основная цель обработки информации.

3.Атрибуты и коды значений атрибутов.

4.Понятие единицы данных и набора данных.

5.Внешнее и внутреннее представление данных.

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

10 С.Г. Кузин. Логические основы автоматической обработки данных

Глава I. Представление целых неотрицательных чисел

2. Представление целых неотрицательных чисел

2.1. Проблемы представления целых неотрицательных чисел

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

Целое число без знака определяется как характеристика (мера) количества элементов в множестве. Существует еще одно определение целого без знака - характеристика порядка расположенных в ряд элементов.

Определена алгебра целых чисел без знака (целых неотрица-

тельных чисел):

Здесь, N+ - основное множество алгебры (множество целых неотрицательных чисел); и - операции сложения и умножения соответственно.

Алгебра Aцбз замкнута относительно операций сложения и умножения. Т.е. результат такой операции над двумя целыми неотрицательными числами также является целым неотрицательным числом.

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

ется записью или кодом числа.

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

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

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

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

С. Г. Кузин. Логические основы автоматической обработки данных 11

Глава I. Представление целых неотрицательных чисел

Распространенный прием: сгрузив очередную доску, ставить в записной книжке «палочку».

Таким образом, последовательность «палочек» правомерно рассматривать как обозначение целого неотрицательного числа (Рис. I.4). Будем называть такое обозначение примитивной записью числа.

Рис. I.4. Примитивная запись целого без знака

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

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

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

2.3. Позиционная система обозначения целых без знака

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

Каждый, наверное, занимался усовершенствованием системы примитивных записей целых без знака. Для этого, последовательность единиц группировалась в десятки, десятки группировались в сотни и т.д. (Рис. I.5)

Рис. I.5. Переход к позиционной системе представления целых без знака

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

Глава I. Представление целых неотрицательных чисел

Здесь, d3,d2,d1,d0 - полное число тысяч, сотен, десятков и единиц соответственно.

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

•вводится конечное, относительно небольшое число знаков - алфа-

вит цифр;

•каждая линейная последовательность цифр образует запись (обозначение) некоторого числа.

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

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

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

онной системой счисления.

Прежде всего, выделим два целых числа без знака, которые играют особую роль: число, обозначаемое как 0, характеризует отсутствие элементов в множестве; число, обозначаемое как 1, характеризует минимально - возможное увеличение или уменьшение числа элементов в множестве.

Концепция позиционной В-ичной системы кодирования (счисления) целых чисел без знака заключается в четырех пунктах.

1.Выбирается произвольное, большее единицы, число, которое называется основанием системы счисления и обозначается как B. Числа меньшие B образуют базу системы счисления.

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

3.Любое целое число без знака единственным образом представляется с помощью чисел базы системы счисления и операций сложения -

умножения в виде канонического арифметического выражения:

ЗНАЧЕНИЕв(цбз)=(dn-1*Bn-1+dn-2*Bn-2+...+d1*B1+d0*B0)в. (I.4)

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

При этом, о коэффициенте di принято говорить как об i-м разряде числа, а об n - как о количестве разрядов числа. Диапазон чисел 0÷n-1

называется разрядной сеткой числа (Рис. I.6).

14 С.Г. Кузин. Логические основы автоматической обработки данных

Глава I. Представление целых неотрицательных чисел

Таблица I.2. Трехразрядные двоичные числа

разряды числа

Ниже приведена таблица цифр (заштрихованы) и записей чисел типа целое без знака в различных системах счисления.

Таблица I.3. Различные системы счисления

Любая позиционная система счисления (кодирования) решает проблему обозначения целых чисел без знака:

•любое целое без знака может быть обозначено последовательностью цифр - записью числа;

•записи (обозначения) самоинтерпретирующиеся, т.е. допускают простые алгоритмы выполнения арифметических операций: ОБОЗНАЧЕНИЕ (первое слагаемое) + ОБОЗНАЧЕНИЕ(второе слагаемое) = ОБОЗНАЧЕНИЕ (сумма двух слагаемых).

16 С.Г. Кузин. Логические основы автоматической обработки данных

Глава I. Представление целых неотрицательных чисел

Позиционное представление целого числа без знака основано на том, что значение любого такого числа может быть однозначно выражено через значение чисел базы и значение основания системы счисления. При таком выражении используются операции алгебры целых неотрицательных чисел. Таким образом, значение любого числа представляется в виде канонического арифметического выражения (арифметического выражения специфического вида - Рис. I.7)

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

Например: (AF7)16 →(10,15,7)16-10. Следует иметь в виду, что простых алгоритмов выполнения арифметических операций для такой системы не существует

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

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

Алгоритм I.1. Перевод В → 10.

Перевод В-ичной записи числа в десятичную запись числа. Для получения записи (d)10 числа d из записи (d)в, следует:

1.Построить в системе с основанием В соответствующее каноническое выражение [е]в, представляя основание как 10;

2.Представляя элементы этого канонического выражения [е]в в десятичной системе, перевести его в неканоническое выражение (е)10 десятичной системы;

3.Вычислить неканоническое выражение (е)10 и получить десятичную запись числа (d)10.

Пример.

Перевод (запись числа)8 → (запись числа)10;

С. Г. Кузин. Логические основы автоматической обработки данных 17

Алгоритм I.2 . Перевод 10 → В.

Перевод десятичной записи числа в В-ичную запись числа. Используются операции целочисленного деления:

X mod Y - результатом является остаток от деления X на Y;

X div Y - результатом является целая часть от деления X на Y. Вычисления выполняются в десятичной системе.

В результате получается запись числа в системе с основанием В, записанная в обратном порядке (Рис. I.8).

Пример. Перевод (запись числа)10 → (запись числа)2

В результате получаем: [125]10 = [1111101]2 Пример. Перевод (запись числа)10 → (запись числа)16

125 16

18 С.Г. Кузин. Логические основы автоматической обработки данных