Учебное пособие -> Глава1. Базовые понятия.

Глава 1. Базовые понятия

Информация

Информация (лат. informatio разъяснение, пояснение) – совокупность сведений (данных), которая воспринимается из окружающей среды (входная информация), выдается в окружающую среду (исходная информация) или сохраняется внутри определенной системы.

Свойства информации:

• объективность и субъективность;

• полнота;

• достоверность;

• адекватность;

• доступность;

• актуальность.

Материальный носитель – материальный объект или среда, служащая для передачи информации.

Изменение характеристики носителя называется сигналом, а значение этой характеристики параметром сигнала.

Источник информации – это субъект или объект, порождающий нформацию и представляющий ее в виде сообщения.

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

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

Рисунок 1 – Передача сообщения

Семиотика (греч. semeion – знак, признак) – науа, занимающаяся исследованием свойств знаков и знаковых систем.

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

Синтаксический, рассматриваются внутренние свойства сообщений.

Семантический,  анализируется смысловое содержание сообщения, его отношение к источнику информации

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

Существуют три меры информации:

• синтаксическая;

• семантическая;

• прагматическая.

На синтаксическом уровне для измерения информации вводятся два параметра:

• Объем информации (объемный подход) .

• Количество информации (вероятностный подход) I

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

Объём данных в техническом смысле этого слова как информационный объём сообщения или как объём памяти, необходимый для хранения сообщения без каких-либо изменений.

Единицы измерения информации: 1 бит = количество двоичных цифр (0 и 1). Пример: код 11001011 имеет объем данных V= 8 бит.

1 байт = 8 бит

1 Кбайт = 1024 байт = 210 байт

1 Мбайт = 1024 Кбайт  = 220 байт =1 048 576 байт;

1 Гбайт = 1024 Мбайт = 230 байт = 1 073 741 824 байт;

1 Тбайт = 1024 Гбайт = 240 байт = 1 099 511 627 776 байт.

Вероятностный подход

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

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

Если N – общее число опытов, а N_А – количество благоприятных исходов случайного события А, то отношение N_A/N, называется относительной частотой появления события А.

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

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

Формула Хартли для равновозможных исходов .

Формула Шеннона для неравновозможных исходов .

Количество информации (в битах), заключенное в двоичном слове, равно числу двоичных знаков в нем  .

Семантическая мера информации

Тезаурус — это совокупность сведений, которыми располагает пользователь или система.

Рисунок 2 – Зависимость количества семантической информации, воспринимаемой потребителем, от его тезауруса

При Sp→0 пользователь не воспринимает, не понимает поступающую информацию;

При Sp→∞ пользователь все знает, и поступающая информация ему не нужна.

Прагматическая мера информации

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

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

Целевая функция – есть математическое выражение некоторого критерия качества одного объекта (решения, процесса и т.д.) в сравнении с другим.

Кодирование информации

Рисунок 3 – Процесс передачи информации

Алфавит – множество знаков, в котором определен их порядок (общеизвестен порядок знаков в русском алфавите: А, Б,..., Я)

Алфавит прописных русских букв

Алфавит Морзе

Алфавит клавиатурных символов ПЭВМ IBM (русифицированная клавиатура)

Алфавит знаков правильной шестигранной игральной кости

Алфавит арабских цифр

Алфавит шестнадцатеричных цифр

Алфавит двоичных цифр

Двоичный алфавит «точка, «тире»

Двоичный алфавит «плюс», «минус»

Алфавит прописных латинских букв

Алфавит римской системы счисления

Алфавит языка блок-схем изображения алгоритмов

Алфавит языка программирования

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

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

Кодирование – перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.

Декодирование – операция обратная кодированию.

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

Декодер – устройство, производящее декодирование.

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

Математическая постановка задачи кодирования:

А – первичный алфавит. Состоит из N знаков со средней информацией на знак I_А .

В – вторичный алфавит из М  знаков со средней информацией на знак I_В.

Сообщение в первичном алфавите содержит n знаков, а закодированное – m знаков.

I_s(A) – информация в исходном сообщении, I_f(B) – информация в закодированном сообщении.

I_S(A) ≤ I_f(B) – условие обратимости кодирования, т.е не исчезновения информации.

n* I_А ≤   m* I_B (заменили произведением числа знаков на среднее информационное содержание знака).

m/n –характеризует среднее число знаков вторичного алфавита, который используется  для кодирования одного знака первичного. Обозначим его К (А, В)

К (А, В)≥ I (A) / I (B)  Обычно К (А, В) >1 

Кmin (А, В)= I (A) / I (B) – минимальная длинна кода

Равномерное алфавитное кодирование.
Представление чисел в компьютере

Компьютерный алфавит С включает буквы латинского алфавита – 52 шт.

Букв русского (прописные и строчные) – 66 шт.

Цифры 0…9 –  10 шт.

Знаки математических операций, препинания, спецсимволы – 20 штук

Итого: 148

К (С, 2) ≥ log2 148 ≥ 7,21,

так как длина кода – целое число, следовательно,  

К (С,2) = 8бит = 1байт.

 Именно такой способ кодирования принят в компьютерных системах. Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении. Это объемный способ измерения информации.

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

Таблицы кодировки

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

Для разных типов ЭВМ используют различные таблицы кодировки:

ANSI - (American National Standards Institute)

ASCII - (American Standard Cod for Information Interchange)

Рисунок 4 – Код обмена информации ASCII

Первоначально – 7 бит:

N=27=128 символов;

0…31 – всевозможные управляющие  символы;

32…127 – видимые на экране символы;

Сейчас – 8 бит, N=2⁸ =256 символов.

Символы со 128…255 – национальные алфавиты, псевдографика.

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

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

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

Таблица. Примеры систем счисления

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

Непозиционной системой счисления является самая простая система с одним символом (палочкой). Для изображения какого-либо числа в этой системе надо записать количество палочек, равное данному числу.

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

Запись чисел в непозиционной системе счисления осуществляется по следующим правилам:

если цифра слева меньше, чем цифра справа, то левая цифра вычитается из правой

Пример: (IV: 1 < 5, следовательно, 5 – 1 = 4, ХL: 10 < 50, следовательно, 50 — 10 = 40);

если цифра справа меньше или равна цифре слева, то эти цифры складываются

Пример: (VI: 5 + 1 = 6, VIII: 5+1+1+1=8, XX: 10+10 = 20).

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

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

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

Число в системе счисления с основанием P равно:

A_nA_n-1A_n-2 … A₁A₀,A_-1A_n-2  = А_n*Pⁿ + A_n-1*P^n-1 + ... + A₁*P¹ + А₀*P⁰ + A_-1*P^-1 + А_-2*P^-2 + ... А_-s*P^-s,

где нижние индексы – определяют месторасположение цифры в числе n и s  - количества разрядов для записи целой и дробной части числа соответственно. 

Примеры:

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

23,43₁₀= 2*10¹ + З*10⁰ + 4*10^-1 + З*10^-2

692₁₀ = 6* 10² + 9*10¹ + 2

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

1101₂= 1*2³ + 1*2²+0*2¹+ 1*2⁰

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

341,5₈ =3*8²+ 4*8¹ +1*8⁰ +5*8^-1

Шестнадцатеричная система

A1F4₁₆ = A*16² + 1*16¹ + F*16⁰ + 4*16^-1

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

Минимальное значащее число (не равное 0), которое можно записать в s разрядах дробной части .

Всего можно записать  разрядных чисел

Диапазон значащих чисел  N в системе счисления с основанием  P при наличии  n  разрядов в целой части и s разрядов в дробной части (без учета знака числа) будет: ,

Двоичная система счисления - позиционная система счисления с основанием 2, цифры 0 и 1.

Преимущества:

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

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

Простота создания таблиц сложения и умножения.

Восемь бит дают 256 различных комбинаций включенных и выключенных состояний.

Число в двоичной системе счисления:

A= A_n*2ⁿ + A_n-1 *2^n-1 + ... + A₁ *2¹ + A₀*2⁰,  A_i  = 0 / 1

Таблица сложения:

Таблица умножения:

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

или 1*2⁰+1*2¹+0*2²+0*2³+1*2⁴+1*2⁵ = 51

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

75₁₀=1001011₂

Двоичная система счисления - позиционная система счисления с основанием 8, цифры от 0 до 7.

Таблица сложения для восьмеричной системы счисления

Таблица умножения для восьмеричной системы счисления

Двоичное, десятичное и шестнадцатеричное представления

Перевод целых чисел из одной системы счисления в другую

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

Остатки от деления должны быть выражены цифрами системы счисления с основанием Q.  Представление искомого числа в системе счисления с основанием Q получается выписыванием последнего частного и остатков от деления в обратном порядке.

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

На практике такой порядок перевода чисел используется при переводе десятичную систему счисления.

23Е₁₆ = ?₁₀ = 2*16²+3*16¹+ Е*16⁰ = 574₁₀

Правило 3. Перевод чисел из восьмеричной системы счисления в двоичную и наоборот переводится по Триадам.

1076₈ = 001 000 111 110₂

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

23E₁₆ = 0010 0011 1101₂

Пример: Перевести число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную

Ответ: 75₁₀ = 1 001 011₂ = 113₈ = 4B₁₆.

Перевод дробных чисел из одной системы счисления в другую

Как правило, это происходит через промежуточный перевод в десятичную систему:

Шаг  1.

Если основание СС - p, простая дробь содержит n цифр и b_k – цифры дроби (1 ≤ k ≤ n, 0 ≤ b_k ≤ p_-1), то она может быть представлена в виде  суммы:                                

O,Y_p =  ∑ b_kp^-k

0,011₂ =0*2^-1+1*2^-2+1*2^-3=0,375¹⁰

Шаг 2.

Умножить исходную дробь в десятичной СС на p, выделить целую часть – она будет первой цифрой новой дроби, отбросить дробную часть;

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

Записать дробь в виде последовательности цифр после ноля с разделителем в порядке их появления в п.1 и 2.

Пример

0,37510→ O,Y₂

       0, 375*2 = 0,750

       0, 75*2   = 1,50

       0, 5*2     = 1,0

0,375₁₀  = 0,011₂

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

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

0,25; -10,44; +0,9781

Пример: Диапазон чисел (N) в системе счисления с основанием Р при наличии m разрядов в целой части и S разрядов в дробной (без учета знака числа) будет:

P^-S ≤ N ≤  Р^m - P^-S

При р=2, m=10 и S=6       0,015 ≤ N ≤ 1024.

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

С плавающей точкой.  Число Х10 называется нормализованным, если оно представлено в виде

Х₁₀ =±М₁₀*10^±К ,

где М₁₀ – мантисса, 0,1≤ М¹⁰< 1, К – порядок, целое положительно десятичное число.

Пример: -1234₁₀= -0,1234*10⁴, 0,003₁₀=0,3*10^-2

При нормализации выполняется деление числа на 4 составляющих: знак числа, мантисса, знак порядка, порядок.

Для произвольной системы счисления.

Х_р =± М_р*P^±К ,  Р^-1 ≤ М< 1

Представление чисел в ЭВМ

Способы представления чисел:

целые положительные числа (без знака)

целые со знаком

вещественные нормализованные числа.

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

в однобайтовом формате значения от 00000000₂ до 11111111₂,

в двухбайтовом формате — от 0000000000000000₂ до 1111111111111111₂.

Диапазоны значений целых чисел без знака

Целые числа со знаком обычно занимают в памяти компьютера один, два или четыре байта, при этом самый левый (старший) разряд содержит информацию о знаке числа. Знак “плюс” кодируется нулем, а “минус” — единицей.

Диапазоны значений целых чисел без знака

Пример

72₁₀=1001000₂

однобайтовый формат

двубайтовый формат

число 65535 в двубайтовом формате

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

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

Прямой код

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

Прямой код числа: 1                     

Прямой код числа: -127

,

где n-разрядность кода, a_зн – значение знакового разряда.

Пример: если разрядность кода равна 4, то

1101=(-1)1[1x20+0x21+1x22]=-5

Обратный код

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

Пример:

 число: -1, модуль 0 0000001, обратный код 1 1111110

 число: -127, модуль 0 1111111 , обратный код 1 0000000

где n-разрядность машинного слова, aзн=0 для положительных чисел, aзн=1 для отрицательных чисел.

1010 = 1*(-23+1)+[0x20+1x21+0x22] = -7+2=-5

Дополнительный код

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

число: -1 = обратный код 1 1111110

число: -127 =  обратный код 1 0000000

Дополнительный код числа: -1              

Дополнительный код числа: -127

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

Алгоритм перевода отрицательных чисел в положительные

Число + его дополнительный код =0.

Представление в двоичном дополнительном коде в случае 3-битного кодирования чисел.

Для дополнительного кода справедливо следующее соотношение:

где n-разрядность машинного слова, aзн=0 для положительных чисел, a_зн =1 для отрицательных чисел.

Пример:

1101 = 1*(-23)+[1x20+1x21+0x22]=-8+3=-5

Операции над целыми числами

Сложение.

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

Умножение

Целочисленное деление и нахождение остатка от деления

Сложение обратных кодов

А и В положительные

А положительное, B отрицательное и по абсолютной величине больше, чем А

А положительное, B отрицательное и по абсолютной величине меньше, чем А

А и B отрицательные

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

Сложение дополнительных кодов

А и В положительные

А положительное, B отрицательное и по абсолютной величине больше, чем А

А положительное, B отрицательное и по абсолютной величине меньше, чем А

А и B отрицательные

Формат представления вещественных чисел

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

Чем больше разрядов отводится под запись мантиссы, тем выше точность представления числа.

Чем больше разрядов занимает порядок, тем шире диапазон от наименьшего отличного от нуля числа до наибольшего числа, представимого в машине при заданном формате.

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

Число 6.25₁₀ = 110.01₂ = +0,11001•2⁺¹¹.

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

Число –0.125₁₀ = –0.001₂ = –0.1*2^–10 (отрицательный порядок записывается в дополнительном коде).

Характеристики форматов вещественных чисел

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

Арифметические операции с вещественными числами

Сложение .

Δk=|k1-k2|

если k1>k2, то  k=k1

    иначе  k=k2

если 10^-1<=M<1, то вывод результата в виде M×10^k,иначе предварительная нормализация

Пример.

X₁=0.87654 * 10₁, X₂=0.94567*10². Пусть под запись мантиссы отводится 5 разрядов.

Δk=1, k₁<k₂ следовательно k₁=k₂=2 (уравняли порядки).

мантиссу числа X₁ сдвигаем на один разряд влево (пропадет 4).

новая мантисса равна 0,94567+0,08765=1,03332

мантисса вышла за допустимый интервал  >1.

нормализуя, получим мантиссу 0,10333 (теряем 2) и порядок увеличиваем на 1.

Ответ: X=0,10333*10³ = 103,3324.

Вычитание сводится к сложению с дополнительным кодом.

Умножение производится по правилу – мантиссы перемножаются, а порядки складываются. Если нужно, то полученное число нормализуется.

Пример

(0.11101 * 2¹⁰¹) * (0.1001 * 2¹¹) = (0.11101 * 0.1001) . 2^(101+11) = 0.100000101 . 2¹⁰⁰⁰.

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

Пример

0.1111 * 2¹⁰⁰ : 0.101 * 2¹¹ = (0.1111 : 0.101) * 2^(100-11) = 1.1 * 21 = 0.11 * 2¹⁰.