Подготовка к экзамену по информатике 2013_2014

Кафедра

Кафедра

информатики

информатики

УГАТУ

Тема: Измерение количества информации

УГАТУ

Формулу для расчета количества информации в случае

равновероятных состояний системы предложил

американский математик Р. Хартли в 1928 году.

Поэтому ее

Подготовка к экзамену

I = log2 N

называют формулой Хартли.

.

За единицу измерения информации берется то количество

информации, которое снимает неопределенность

наших знаний о системе в случае ее равновероятных

состояний ровно в два раза.

Эта единица получила название бит.

Информатика курс 1, семестр 1, 2013-2014 г.

2

Кафедра

Кафедра

информатики

информатики

Тема: Измерение количества информации УГАТУ

Тема: Измерение количества информации

УГАТУ

Пример. Пусть нужно передать информацию об исходе

Пример. Сколько бит информации будет получено при

бросания монеты. До момента бросания монеты

бросании пирамидки (четыре грани N = 4) и кубика (шесть

имеется неопределенность исхода данного события,

граней N = 6), при условии, что пирамидка и кубик

при этом потенциально возможны два варианта

симметричны и однородны, т.е. исходы N событий для

равновероятных исходов бросания.

Вероятность

них равновероятны.

каждого события р1=р2=0,5.

Решение. Согласно формуле Хартли:

Любое из двух сообщений о результате бросания монеты

I = log2 N

уменьшает неопределенность ровно в два раза.

Это и есть количество информации в 1 бит.

Действительно, согласно формуле Хартли

I = log 22 = 1 бит

Информатика курс 1, семестр 1, 2013-2014 г.

3

Информатика курс 1, семестр 1, 2013-2014 г.

4

Кафедра

Кафедра

информатики

информатики

Тема: Измерение количества информации

Тема: Измерение количества информации

УГАТУ

УГАТУ

Если взять два объекта: один может находится в 1,…,m1

Пример. В корзине 10 белых грибов, 18 подберезовиков и

равновероятных состояниях, а второй в 1, …, m2

22 подосиновика. Сколько информации несет

равновероятных состояниях.

сообщение о том, что из корзины достали подберезовик

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

или подосиновик.

50

объекте?

Ответ:

I = log

2

= 0,3219 бит

По закону аддитивности информации:

40

I = log(m1

m1 + m2

+ m2 ) − log m1 = log

m1

Пример. В корзине 8 белых грибов и 24 подосиновика.

Сколько бит информации несет сообщение о том, что

из корзины достали белый гриб.

64

64

32

log2

= 2

= 4 A = 48

I = log 2

= log 2 ( 4) = 2 бита

Ответ: 4

64 − A

64 − A

8

Информатика курс 1, семестр 1, 2013-2014 г.

5

Информатика курс 1, семестр 1, 2013-2014 г.

6

Кафедра

Кафедра

Тема: Измерение объема информации

информатики

информатики

Тема: Измерение количества информации

УГАТУ

УГАТУ

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

называется алфавитом.

Полное количество символов в алфавите называется

I = log2 N

мощностью (размером) алфавита.

N = 2I

Пример. Мощность компьютерного алфавита 256 символов.

Для кодирования одного символа необходимо ______

log 2 256 = 8 бит

Ответ:

N = 27 = 128

Пример. Для кодирования символов некоторого алфавита

выделено 6 битов.

Мощность этого алфавита равна _______

26 = 64

символа

Информатика курс 1, семестр 1, 2013-2014 г.

7

Информатика курс 1, семестр 1, 2013-2014 г.

8

Кафедра

Тема: Измерение объема информации

Кафедра

Тема: Измерение объема информации

информатики

информатики

УГАТУ

УГАТУ

С

Объем сообщения составил 2 Mбайта. На одной

странице помещается 32 строки по 128 символов в каждой.

Число страниц, которое занимает сообщение, равно 512.

Алфавит, с помощью которого записано сообщение,

содержит _____ символов.

Решение:

Решение:

Алфавит содержит 16 символов, значит для кодирования

одного символа необходимо 4 бита.

Общее число символов: 128 × 32 × 512 = 27 × 25 × 29 = 221

Объем сообщения в битах 2 × 210 × 210 × 23 = 224

Общее число символов: 64 × 16 × 64 = 26 × 24 × 26 = 216

Значит один символ кодируется 224 / 221 = 23 = 8 битами

Объем сообщения в битах 22 × 216 = 218

Таким количеством битов можно закодировать 28 различных

Объем сообщения в Кбайтах 218 / 23 /210= 25 = 32 Кбайт

символов

Ответ: 256

Ответ: 32 Кбайт

Информатика курс 1, семестр 1, 2013-2014 г.

9

Информатика курс 1, семестр 1, 2013-2014 г.

10

Кафедра

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

Кафедра

Тема: Измерение объема информации

информатики

информатики

УГАТУ

УГАТУ

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

дискретизации и разрядностью аудиоадаптера.

Частота дискретизации – это количество измерений

входного сигнала за 1 секунду (Гц).

Разрядность (глубина кодирования звука) – число бит в

регистре аудиоадаптера.

Информационный объем звукового файла в битах

D = V × i × t × k,

где V – частота дискретизации в Гц,

i – разрядность аудиоадаптера в битах,

t – длительность звучания в сек

Ответ: 3

k – количество дорожек (1 для моно; 2 для стерео).

Информатика курс 1, семестр 1, 2013-2014 г.

11

Информатика курс 1, семестр 1, 2013-2014 г.

12

Кафедра

Тема: Измерение объема информации

Кафедра

Тема: Измерение объема информации

информатики

информатики

УГАТУ

УГАТУ

С

При переводе в дискретную форму аналогового

сигнала длительностью 4 минуты 16 секунд

использовались частота дискретизации v = 64 Гц и

32

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

Кбайтах равен ____.

Решение:

Решение:

Время переводится в секунды 4 × 60 + 16 = 256

Размер кода в битах равен 2 × 210 × 23 = 214 бит

Время переводится в секунды 4 × 60 + 16 = 256

Разрядность аудиоадаптера 214 / 24/ 28 = 4 бита

Чтобы обеспечить 32 уровня дискретизации необходим

Это обеспечивает 16 уровней дискретизации

аудиоадаптер с разрядностью 5 битов (log232).

Размер кода равен 5 × 64 × 256 = 5 × 26 × 28 = 5 × 214 бит

Перевод в Кбайты: 5 × 214 / 23 / 210 = 10 Кбайт

Ответ: 10 Кбайт

Ответ: 16 уровней

Информатика курс 1, семестр 1, 2013-2014 г.

13

Информатика курс 1, семестр 1, 2013-2014 г.

14

Кафедра

Тема: Измерение объема информации

Кафедра

Тема: Измерение объема информации

информатики

информатики

УГАТУ

УГАТУ

Пиксель – наименьший элемент изображения на экране

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

в видеопамяти. Видеопамять – это электронное

(точка на экране).

энергозависимое запоминающее устройство, в котором

Растр – прямоугольная сетка пикселей на экране.

хранится изображение во время воспроизведения его на

Разрешающая способность монитора – М × N, где N –

экране.

число строк сетки растра, М – число точек в строке.

Размер видеопамяти зависит от разрешающей

Битовая глубина цвета (k) – количество битов выделенных

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

Но ее минимальный объем определяется так, чтобы

на кодирование цвета одной точки.

поместился один кадр (одна страница) изображения, т.е.

Число цветов, воспроизводимых на экране монитора N = 2k.

как результат произведения разрешающей способности

Объем памяти, необходимой для хранения растрового

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

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

Страница видеопамяти – раздел видеопамяти,

(пикселей), составляющих изображение, на

вмещающий информацию об одном образе экрана. В

информационный объем одной точки.

видеопамяти может храниться сразу несколько страниц.

Информатика курс 1, семестр 1, 2013-2014 г.

15

Информатика курс 1, семестр 1, 2013-2014 г.

16

Кафедра

Тема: Измерение объема информации

Кафедра

Тема: Измерение объема информации

информатики

информатики

УГАТУ

УГАТУ

С

Изображение на экране содержит 256 × 256 точек.

Каждая точка может иметь один из 256 оттенков

цвета. Минимальный объем памяти, необходимый для

хранения этого изображения в Кбайтах равен ____.

Решение:

Решение:

Объем изображения в битах равен 2 × 3 × 210 × 210 × 23

Для хранения 256 оттенков цвета необходимо 8 бит (log2256)

Объем изображения состоит из точек 210 × 28 × 3 × 24

Объем изображения в битах равен 8 × 256 × 256 = 219

Для кодирования цвета одной точки необходимо

Перевод в Кбайты: 219 / 23 / 210 = 64 Кбайт

(3 × 224 ) / (222 × 3) = 4 бит

Ответ: 64

Ответ: 4 бита

Информатика курс 1, семестр 1, 2013-2014 г.

17

Информатика курс 1, семестр 1, 2013-2014 г.

18

Кафедра

Тема: Измерение объема информации

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

C

Система счисления (СС) – принятый способ наименования

и записи чисел с помощью символов, имеющих

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

В любой системе счисления выбирается алфавит,

(совокупность некоторых символов – слов или знаков), с

помощью которого можно представить любое количество

чего-либо.

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

символы алфавита – цифрами.

Информатика курс 1, семестр 1, 2013-2014 г.

19

Информатика курс 1, семестр 1, 2013-2014 г.

20

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

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

В позиционной системе счисления количественное

класса: непозиционные и позиционные.

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

в числе.

Самый известный пример непозиционной СС – римская,

в которой используется 7 знаков:

2 3 , 4 3 1 0

число единиц

число сотых долей единицы

Например,

III (три), LIX (59), DLV (555)

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

не зависит от места, которое он занимает в числе.

Информатика курс 1, семестр 1, 2013-2014 г.

21

Информатика курс 1, семестр 1, 2013-2014 г.

22

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Количество используемых знаков в позиционной системе

С

Число 1BE6,12(16) в десятичной системе счисления

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

равно _____

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

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

разделителя использовать запятую)

Решение:

1 163 +11 162 +14 161 + 6 160 +1 16−1 + 2 16−2 = 7142,07

Ответ: 7142,07

Информатика курс 1, семестр 1, 2013-2014 г.

23

Информатика курс 1, семестр 1, 2013-2014 г.

24

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

С

Число

121,51010 в двоичной системе счисления

A

Расположите числа

равно

А =

341(9)

В = 13B(16)

С = 2002(3)

в порядке возрастания

121 div 2 =

60

(1)

0,51 × 2 = 1,02

(1)

1) А, В, С

2) В, С, А

3) С, А, В

60 div 2 =

30

(0)

0,02 × 2 = 0,04

(0)

4) С, В, А

5) А, С, В

30 div 2 =

15

(0)

15 div 2 =

7

(1)

Решение:

7 div 2 =

3

(1)

3 div 2 =

1

(1)

A = 341(9) = 3 × 92 + 4 × 9 + 1 = 243 + 36 + 1 = 280(10)

1 div 2 =

0

(1)

B = 13B(16) = 1 × 162 + 3 × 16 + 11 = 256 + 48 + 1 = 315(10)

Ответ: 1111001,1

C = 2002(3) = 2 × 33 + 2 = 56(10)

Ответ: (3)

Информатика курс 1, семестр 1, 2013-2014 г.

25

Информатика курс 1, семестр 1, 2013-2014 г.

26

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Таблица сложения в двоичной СС

Для перевода целого двоичного числа в восьмеричное

(шестнадцатеричное) необходимо:

- разбить это число справа налево на группы по 3 (4) цифры –

двоичные триады (тетрады). При этом самая левая группа

При двоичном сложении 1 + 1 возникает перенос 1 в

может содержать менее трех (четырех) двоичных цифр.

- каждой группе поставить в соответствие ее восьмеричный

старший разряд, как и в десятичной арифметике.

(шестнадцатеричный) эквивалент.

Например,

Информатика курс 1, семестр 1, 2013-2014 г.

27

Информатика курс 1, семестр 1, 2013-2014 г.

28

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

11011001 = 011 011 001 = 331(8)

С Сумма чисел 11111111(2) и 10101(2) в шестнадцатеричной

системе счисления равна _________

(в ответе шестнадцатеричные цифры 10, 11, 12, 13, 14, 15

набираются большими латинскими буквами A, B, C, D, E, F

соответственно)

011 = 0 + 2 + 1 = 3

001 = 0 + 0 + 1 = 1

1100011011001 = 0001 1000 1101 1001 = 18D9(16)

1

1

4

0001 = 0 + 0 + 0 + 1 = 1

1101 = 8 + 4 + 0 + 1 = 13 (D)

1000 = 8 + 0 + 0 + 0 = 8

1001 = 8 + 0 + 0 + 1 = 9

Ответ: 11416

Информатика курс 1, семестр 1, 2013-2014 г.

29

Информатика курс 1, семестр 1, 2013-2014 г.

30

Кафедра

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

Кафедра

информатики

УГАТУ

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

УГАТУ

Целые со знаком:

Правило получения дополнительного кода:

1. Старший бит выделен для обозначения знака числа:

• Десятичное число записывается в прямом коде.

0 – соответствует знаку '+' ;

В старшем бите записывается 1, если число

1 – соответствует знаку '-' .

отрицательное, 0 – если положительное.

Остальные биты – для значения числа.

2.

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

• Все разряды прямого кода кроме знакового (старшего

3.

Отрицательные значения – в дополнительном коде.

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

Если для хранения числа выделено n бит (8,16,32, …) и

• К младшему разряду обратного кода прибавляется

старший бит используется для знака, тогда

единица по правилам сложения двоичных чисел –

Минимальное значение числа =

(- 2 n-1)

Максимальное значение числа =

+ (2 n-1 – 1)

получается дополнительный код.

Количество различных чисел = 2 n

Информатика курс 1, семестр 1, 2013-2014 г.

31

Информатика курс 1, семестр 1, 2013-2014 г.

32

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

С

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

С

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

знаком с обратным кодом 11001111 имеет вид

знаком с дополнительным кодом 10000111 имеет вид

1 0000111 – дополнительный код

Знаковый

1 1001111 – обратный код

1 0000110 – обратный код

разряд

1 0110000 – прямой код

1 1111001 – прямой код

0110000

2

= 1×25 + 1×24 = 48

10

1111001 2 = 1×26 + 1×25 + 1×24 + 1×23 + 1×20 = 2110

Ответ: - 48

Ответ: - 21

Информатика курс 1, семестр 1, 2013-2014 г.

33

Информатика курс 1, семестр 1, 2013-2014 г.

34

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Алгебра логики – раздел математики, изучающий

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

высказывания, рассматриваемые со стороны их

логические операции любое высказывание можно

логических значений (истинности или ложности) и

формализовать, т.е. заменить логической формулой.

логических операций над ними.

Приоритеты выполнения логических операций в логических

Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем

выражениях:

как попытка изучения логики мышления человека математическими

1. отрицание или инверсия (НЕ A, not A, ¬ A,

);

методами.

Высказывание в алгебре логики – это повествовательное

2. логическое произведение или конъюнкция (И, and, , , , &);

предложение, в котором что-либо утверждается или

3. логическое сложение или дизъюнкция (ИЛИ, or, , +),

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

исключающее или (xor, , );

однозначно сказать истинно оно или ложно.

4. импликация или следование ( , →),

эквиваленция или равнозначность ( , ≡, =, ↔, ~).

Примеры высказываний: «Трава зеленая»; «2≠5»; «Я – студент УГАТУ»; «10<5».

Скобки меняют порядок выполнения операций.

«Коля дома и смотрит телевизор»; «Мама на работе или уже дома».

Информатика курс 1, семестр 1, 2013-2014 г.

35

Информатика курс 1, семестр 1, 2013-2014 г.

36

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Для удобства и наглядности отражения сути логических

Для каждой логической функции Y = F(X1,X2,…,Xn) можно

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

построить таблицу истинности.

принято использовать таблицы истинности.

В таблицах истинности записываются все возможные

Количество строк в этой таблице будет равно числу

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

возможных комбинаций значений логических

соответствующие им значения логической функции.

переменных, т.е. 2N, где N – число логических

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

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

Количество столбцов в таблице истинности равно сумме

количества логических переменных и количества

логических операций в логическом выражении, т.е. N+M,

где M – число логических операций.

Информатика курс 1, семестр 1, 2013-2014 г.

37

Информатика курс 1, семестр 1, 2013-2014 г.

38

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Пример. Составить таблицу истинности для логической функции

F ( A, B, C ) = (B or C ) and A

Количество строк, в таблице равно 8 (23), количество столбцов 3 + 3=6.

A (B + C)

Последняя колонка полученной таблицы является ответом на

Ответ: 1

поставленную задачу.

Информатика курс 1, семестр 1, 2013-2014 г.

39

Информатика курс 1, семестр 1, 2013-2014 г.

40