I log n log 3 1,5849625... 1,6 бита  2  2  

Видим, что величина исходной энтропии увеличилась (соответственно

увеличилось количество информации, получаемой при устранении исходной

энтропии). 23

Действительно, когда у нас белых шаров было больше, мы заранее могли

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

неопределённости: ничего заранее предполагать не можем.

Вывод: Энтропия выше в том случае, если ожидаемые события равновероятны.

Или иными словами: при наступлении события мы получаем информации

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

Приставки КИЛО, МЕГА, ГИГА, ТЕРА и ПЕТА

Для измерения объёма данных используются единицы бит и байт.

Сами по себе единицы бит и байт являются довольно малыми единицами

измерения объёма данных. Если записывать объём современных жёстких

дисков в байтах, тогда будут получаться большие числа, неудобные для

восприятия человеком (например, 120ГБ в байтах: 128849018880 байт).

Чтобы большие объёмы данных записывались более компактными

числами, используются приставки КИЛО, МЕГА, ГИГА, ТЕРА и ПЕТА.

Соотношение между производными единицами следующее:

Единица Обозначение Объём Объём в байтах

1 килобайт 1КБ или 1KB 1024 байта 2

10 байт

1 мегабайт 1МБ или 1MB 1024КБ 2

20 байт

1 гигабайт 1ГБ или 1GB 1024МБ 2

30 байт

1 терабайт 1ТБ или 1TB 1024ГБ 2

40 байт

1 петабайт 1ПБ или 1PB 1024ТБ 2

50 байт

Возникает вопрос: почему используются единицы, кратные 1024, а не

ровно 1000? Дело в том, что так удобнее для компьютера. Компьютер считает в

двоичной системе счисления, и число 1024 (=2

10) для него является круглым.

Для нас, использующих десятичную систему счисления, круглыми

являются числа: 10, 100, 1000, 10000 и т.д., умножая на 10. Для компьютера

круглыми числами являются: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 и т.д.,

умножая на 2.

Приставки КИЛО, МЕГА, ГИГА, ТЕРА и ПЕТА могут использоваться и

совместно с единицей бит:

Единица Обозначение Объём

1 килобит 1Кбит 1024 бита

1 мегабит 1Мбит 1024Кбита

1 гигабит 1Гбит 1024Мбита

1 терабит 1Тбит 1024Гбита

1 петабит 1Пбит 1024Тбита 24

Единицы скорости передачи данных

При передаче данных чаще всего используется последовательный

интерфейс, когда данные передаются по однолинейному каналу по одному

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

секунду: бит/с. Например: 120Мбит/с означает «сто двадцать мегабит в

секунду».

Внутри компьютера данные обычно передаются с помощью параллельного

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

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

цифровая шина передаёт 8 бит за раз, то есть один байт.

В случае использования параллельного интерфейса скорость передачи

данных измеряется в байтах в секунду: байт/с. Например: 100Мбайт/с означает

«сто мегабайт в секунду».

Тема №3

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

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

Системой счисления называется определённый способ записи чисел с

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

* какие именно будут использоваться цифры (римские, арабские или же ещё какие-

нибудь);

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

что означает этот порядок).

Системы счисления бывают позиционные и непозиционные.

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

внутри записи числа неодинаковы и возрастают справа налево.

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

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

например, 555 каждая цифра имеет разное значение:

* первая справа цифра 5 означает количество единиц (5);

* вторая справа цифра 5 означает количество десятков (50);

* третья справа цифра 5 означает количество сотен (500).

Непозиционной СС называется такая система записи чисел, когда

значения цифр внутри записи числа не зависят от позиции цифр в числе.25

Например, к непозиционным относится римская СС. Римские числа

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

VI – шесть (5+1)

XIII – тринадцать (10+1+1+1)

XXV – двадцать пять (10+10+5)

Математические характеристики позиционных систем счисления

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

и основанием. Основание позиционной СС – это число, на единицу большее

самой старшей цифры.

Например, в десятичной СС используется десять цифр: 0, 1, 2, 3, 4, 5, 6, 7,

8 и 9. Самая старшая цифра здесь – это 9. Основание = 9 + 1 = 10.

Сколько цифр используется в той или иной позиционной системе

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

системы: «десятичная» – значит, используется десять цифр и основание равно

десяти.

Теоретически для записи чисел можно использовать какую угодно

позиционную систему счисления (необязательно десятичную): двоичную,

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

всех возможных позиционных систем счисления является двоичная СС.

Чтобы найти общее значение числа, записанного в той или иной

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

формулой:

XnXn-1…X3X2X1 = Xn·an-1

+ Xn-1·an-2

+…+ X3·a

2

+ X2·a

1

+ X1·a

0

(3)

где Xi– цифры внутри записи числа; n – общее количество цифр в записи

числа;

a – основание системы счисления.

Например, десятичное число 3518. Его значение вычисляется так:

3518 = 3·103

+ 5·102

+ 1·101

+ 8·100

= 3000 + 500 + 10 + 8

Одна позиция внутри записи числа в позиционной СС называется

разрядом. Нумерация разрядов идёт справа налево. Чаще нумерацию разрядов

начинают с нуля, а не с единицы: самый правый разряд целой части числа – это

нулевой разряд; слева от него – первый разряд; левее первого – второй разряд и 26

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

Например, в числе 3518 нулевой разряд равен 8, первый разряд равен 1,

второй разряд равен 5, третий разряд равен 3, четвёртый разряд равен 0, пятый

– тоже 0 и все остальные ещё более старшие разряды тоже равны 0:

00…00003518

Примеры позиционных систем счисления, применяемых на практике

Кроме десятичной СС на практике применяются: двоичная, восьмеричная

и шестнадцатеричная системы. Их цифры и основания приведены в таблице

ниже.

Система счисления Основание Алфавит цифр

Позиционные

Десятичная 10 0,1,2,3,4,5,6,7,8,9

Двоичная 2 0,1

Восьмеричная 8 0,1,2,3,4,5,6,7

Шестнадцатеричная 16 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

Непозиционные

Римская I(1), V(5), X(10), L(50), C(100), M(1000)

Двоичная СС

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

что вычислительные машины (компьютер, калькулятор) непосредственно

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

двоичной системе. Мы вводим числа в калькулятор в десятичной СС,

калькулятор автоматически преобразует запись чисел в двоичную СС,

производит расчёты с числами, представленными в двоичной СС, а затем

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

нас виде.

Из названия «двоичная» следует, что основание = 2 и используется только

две цифры: 0 и 1. Приведём примеры перевода записи чисел из десятичной СС

в двоичную и обратно.

Перевод из десятичной в двоичную

Для выполнения такого перевода, нужно выполнять деление исходного

десятичного числа на 2. Делить нужно нацело, запоминая, чему равен остаток

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

результат делим на 2. Выполняем деление до тех пор, пока результат не будет

равен нулю.27

После выполнения деления, чтобы получить ответ (запись числа в двоичной

СС) нужно собрать запомненные остатки от деления, составляя их справа

налево.

Переведём в двоичную СС десятичное число 193:

Действие Результат Остаток

193 : 2 96 1

96 : 2 48 0

48 : 2 24 0

24 : 2 12 0

12 : 2 6 0

6 : 2 3 0

3 : 2 1 1

1 : 2 0 1

По окончании деления записываем остатки справа налево:1 1 0 0 0 0 0 1

Ответ: 19310 = 110000012

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

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

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

X…XXXa

(в общем виде), 19310 (десятичное число), 110000012 (двоичное число) и

т.п.

Перевод из двоичной в десятичную

Чтобы перевести число в десятичную СС, нужно воспользоваться формулой

(3):

110000012 = 1•27

+ 1•26

+ 0•25

+ 0•24

+ 0•23

+ 0•22

+ 0•21

+ 1•20

=

= 1•128 + 1•64 + 0•32 + 0•16 + 0•8 + 0•4 + 0•2 + 1•1 = 19310

Восьмеричная СС

Основание = 8. Используемые цифры: 0, 1, 2, 3, 4, 5, 6 и 7.

Перевод из десятичной в восьмеричную

Переведём в восьмеричную СС десятичное число 193:

Действие Результат Остаток

193 : 8 24 1

24 : 8 3 0

3 : 8 0 3

Записываем остатки справа налево: 3 0 1

Ответ: 19310 = 3018

Перевод из восьмеричной в десятичную

Опять же пользуемся формулой (3):

3018 = 3·8

2

+ 0·8

1

+ 1·8

0

= 3·64 + 0·8 + 1·1 = 192 + 0 + 1 = 1931028

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

Основание = 16. Используемые цифры:

Шестнадцатеричная цифра 0 1 2 3 4 5 6 7 8 9 A B C D E F

Десятичное значение цифры 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Переведём в шестнадцатеричную СС десятичное число 193:

Действие Результат Остаток Остаток в виде шестнадцатеричной цифры

193 : 16 12 1 1

12 : 16 0 12 C

По окончании деления записываем остатки справа налево: C1

Ответ: 19310 = C116

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

Для этого нужно подставить цифры данного числа в формулу (3):

C116 = 12·161

+ 1·160

= 12·16 + 1·1 = 19310

Простой способ перевода из двоичной СС в восьмеричную и наоборот

Если требуется перевод из двоичной в восьмеричную СС, то это легко

выполняется следующим способом:

1) цифры внутри двоичного числа группируются по три, начиная справа; в

случае если для последней (самой левой группы) не хватило цифр, тогда

впереди числа дописываются нули;

в нашем примере с числом 193: 11000001 = 011 000 001

2) полученные группы из трёх двоичных цифр формально заменяются

восьмеричными цифрами в соответствии со следующей таблицей:

Двоичная группа цифр 000 001 010 011 100 101 110 111

Восьмеричная цифра 0 1 2 3 4 5 6 7

в нашем примере с числом 193: 110000012 = 011 000 0012 = 3018

По этой же таблице можно выполнить и обратное преобразование, формально

заменяя каждую восьмеричную цифру группой из трёх двоичных цифр.

Простой способ перевода из двоичной СС

в шестнадцатеричную и наоборот

Аналогичный способ можно применять и для перевода чисел из двоичной

СС в шестнадцатеричную. Отличие только в том, что здесь нужно 29

группировать не по три, а по четыре двоичных цифры:

Двоичная группа цифр 0000 0001 0010 0011 0100 0101 0110 0111

Шестнадцатеричная цифра 0 1 2 3 4 5 6 7

Двоичная группа цифр 1000 1001 1010 1011 1100 1101 1110 1111

Шестнадцатеричная цифра 8 9 A B C D E F

Наш пример: 110000012 = 1100 00012 = C116

О практическом применении восьмеричной и шестнадцатеричной СС

При первом появлении вычислительных машин, людям часто приходилось

вводить числовые данные и числовые коды команд в двоичном коде – в том

виде, в каком удобно компьютеру.

Однако при представлении чисел нулями и единицами очень легко

допустить ошибку (попробуйте ввести без ошибки следующее число:

0001010111101100 !) От множества нулей и единиц рябит в глазах.

Восьмеричная и шестнадцатеричная системы предоставляют простой

способ перевода чисел из длинной двоичной записи в более короткую

восьмеричную или шестнадцатеричную:

00010101111011002 = 000 001 010 111 101 1002 = 0123548 = 127548

00010101111011002 = 0001 0101 1110 11002 = 15EC16

Согласитесь, что ввести в компьютер число 12754 или 15EC гораздо

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

В то же время компьютеру ничего не стоит преобразовать, например,

число 15EC из шестнадцатеричной СС в удобную ему двоичную. Это

преобразование выполняется путём формальной замены каждой

шестнадцатеричной цифры на четвёрку двоичных цифр (см. табл. на стр.29).

Поэтому при необходимости ввода двоичного числа или кода обычно

используется ввод шестнадцатеричного числа.

В настоящее время шестнадцатеричные числа Вы можете встретить:

а) в программировании; б) там, где указывается адрес порта ввода-вывода; в)

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

адресации 32-хразрядного процессора составляют ячейки с адресами от 00000000

до FFFFFFFF.30

Преобразование чисел из одной СС в другую с помощью программы

«Калькулятор»

В Windows имеется стандартная программа «Калькулятор», позволяющая

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

шестнадцатеричные числа. Запускается программа так:

Пуск→Программы→Стандартные→Калькулятор.

Чтобы можно было преобразовывать формат чисел, необходимо иметь

инженерный вид калькулятора, который устанавливается командой

Вид→Инженерный. В верхней части инженерного калькулятора имеются

переключатели Hex, Dec, Oct и Bin.

Переключатель Hex Dec Oct Bin

Система счисления шестнадцатеричная десятичная восьмеричная двоичная

По умолчанию выбран переключатель Dec, что означает, что вводимые и

вычисляемые числа являются десятичными.

Чтобы преобразовать число из одной СС в другую, нужно:

1) установить переключатель (Hex, Dec, Oct или Bin) в соответствии с тем, в

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

десятичное число 193, тогда устанавливаем переключатель Dec;

2) ввести число по цифрам, чтобы оно отображалось в текстовом поле

калькулятора;

3) установить переключатель (Hex, Dec, Oct или Bin) в положение,

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

Например, если введённое число нужно преобразовать в двоичную СС, тогда

нужно установить переключатель Bin.

Результат преобразования будет показан мгновенно.

Тема №4

Логические основы ЭВМ

Логика

Логика – это наука о мышлении – наука о формах и способах мышления,

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

Одно из базовых понятий логики – это высказывание. Высказывание – это

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

Существует множество разновидностей высказываний, но все они могут

быть приведены к одной из двух основных форм: описательное высказывание31

или оценочное высказывание.

Описательное высказывание содержит описание чего-либо. Например:

«В городе Тюмени сейчас идёт дождь». Оценочное высказывание содержит

оценку чего-либо или побуждение выполнить что-либо. Примеры: «Хорошо,

что в городе Тюмени сейчас идёт дождь»; «Пойдите и проверьте, кончился

дождь или нет» (здесь наше действие «пойти и проверить» кем-то оценивается

как желаемое).

Описательные высказывания

Описательные высказывания могут быть истинными или ложными.

Описательное высказывание является истинным, если в действительности всё

так, как указывается в этом высказывании. Иначе – высказывание ложно.

Например, высказывание «В городе Тюмени сейчас идёт дождь» является

истинным, если действительно сейчас идёт дождь. Если сейчас дождя нет, то

это высказывание ложно.

Описательное высказывание – это любое повествовательное

предложение, в отношении которого можно однозначно утверждать, что оно

истинно или ложно.

Составные высказывания

Высказывания могут быть простыми и составными.

Простое описательное высказывание утверждает только один какой-

нибудь факт. Например, «Все металлы электропроводны»; «Земля меньше

Солнца»; «Наш дом выше деревьев»…

Составные высказывания строятся из простых путём соединения их между

собой при помощи логических связок: «и», «или», «неверно, что», «либо, либо»,

«если, то», «тогда и только тогда, когда» и некоторых других. Примеры:

«Я завтра пойду в кино и в театр» = «Я завтра пойду в кино» И «Я завтра пойду в

театр»

«Кларнет украли Карл или Клара» = «Кларнет украл Карл» ИЛИ «Кларнет украла

Клара»

«Неверно, что мне уже за 40» = НЕВЕРНО, ЧТО «Мне уже больше 40 лет»

«Я пойду домой либо в 5 часов, либо в 6» =

= ЛИБО «Я пойду домой в 5 часов», ЛИБО «Я пойду домой в 6 часов»

«Если число 8 делится на 4, то оно делится и на 2» =32

= ЕСЛИ «8 делится на 4», ТО «8 делится на 2»

«Число является чётным тогда и только тогда, когда оно делится на 2» =

= «Число является чётным» ТОГДА И ТОЛЬКО ТОГДА, КОГДА «Число делится

на 2»

Для образования составных высказываний можно использовать и

комбинации разных логических связок. Например:

«Если кларнет украли Карл или Клара, тогда Петров и Иванов не виновны» =

= ЕСЛИ «Кларнет украл Карл» ИЛИ «Кларнет украла Клара», ТО НЕВЕРНО,

ЧТО «Петров виновен» И НЕВЕРНО, ЧТО «Иванов виновен»

Алгебра высказываний

Алгебра высказываний была разработана для того, чтобы можно было

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

содержание.

Здесь высказываниям ставятся в соответствие логические переменные.

Логическая переменная – это буква (обычно строчная латинская), с которой

связывается одно из двух значений: либо «истина», либо «ложь». Например:

a = «Два умножить на два равно четырем» = истина

b = «Два умножить на два равно десяти» = ложь

Для краткости значения логических переменных обозначают нулём и

единицей. Истинному высказыванию соответствует 1, ложному 0.

В нашем примере a = 1 и b = 0.

В алгебре высказываний составные высказывания получаются путём

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

Истинность составного высказывания зависит от истинности входящих в

него простых высказываний и использованных логических операций.

Логическая операция – это функция от одной или двух логических

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

Каждой логической связке («и», «или», «неверно, что», «либо, либо», «если,

то», «тогда и только тогда, когда») соответствует определённая логическая

операция.

Таблицы, определяющие значения логических операций при различных

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

истинности.33

Основные логические операции

Конъюнкция, или логическое умножение

Конъюнкция – логическая операция, соответствующая

логической связке «И». Конъюнкция обозначается символами: ,

&, а также словами «и», «and». Как видно из таблицы

истинности, логическое выражение a  b будет равно 1 только

тогда, когда a = 1 и b = 1. На языке логики это означает, что

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

истинно тогда и только тогда, когда истинны оба входящие в него

высказывания.

Дизъюнкция, или логическое сложение

Дизъюнкция – логическая операция, соответствующая логической связке

«ИЛИ».

Дизъюнкция обозначается символом , а также словами

«или», «or». Как видно из таблицы истинности, логическое

выражение a  b будет равно 1, когда a = 1, когда b = 1 или когда

a и b равны 1 одновременно. На языке логики это означает, что

составное высказывание, построенное с использованием

дизъюнкции, будет истинно тогда, когда истинно хотя бы одно из входящих в

него высказываний.

Инверсия, или отрицание

Инверсия – логическая операция, обозначающая логическую

связку «НЕВЕРНО, ЧТО». Инверсия применяется к одной логической

переменной.

Обозначается: крышкой над буквой переменной или над целым

выражением ( a , a  b , a  b ), символом  (a), иногда также символом ~ (~a),

а также словами «не», «not». Как видно из таблицы истинности, инверсия

изменяет значение логической переменной на противоположное. На языке

логики это означает, что составное высказывание, построенное с

использованием инверсии, будет истинно тогда, когда входящее в него

высказывание ложно.

Пример. Высказывание «5 делится на 2 без остатка» ложно. А его инверсия

(его отрицание) будет истинно: «Неверно, что 5 делится на 2 без остатка».

a b a  b

0 0 0

0 1 0

1 0 0

1 1 1

a b a  b

0 0 0

0 1 1

1 0 1

1 1 1

a a

0 1

1 034

Исключающее ИЛИ, или сложение по модулю 2, или

неравнозначность

Исключающее ИЛИ – логическая операция, соответствующая логической

связке «ЛИБО, ЛИБО». Обозначается символами ,  , а также словом «xor».

Как видно из таблицы истинности, логическое выражение a  b

равно 1 тогда, когда ровно одна из исходных переменных имеет

значение 1. На языке логики это означает, что составное

высказывание, построенное с использованием исключающего

или, будет истинно тогда, когда истинно только одно из

входящих в него высказываний.

Пример. «Либо Вы купите автомобиль, либо норковую

шубу». Здесь делается акцент, что сразу оба действия совершены быть не

могут. Если Вам всё же хватило денег и Вы купили как автомобиль, так и шубу,

тогда приведённое высказывание ложно. Оно ложно и в том случае, если Вы

ничего не купите (ни шубу, ни автомобиль).

Логическую операцию ИСКЛЮЧАЮЩЕЕ ИЛИ ещё называют строгой

дизъюнкцией или дизъюнкцией с исключённым третьим. Так, обычная

дизъюнкция имеет три случая истинности: высказывание «Кларнет украли Карл

или Клара» будет истинным в трёх случаях: