Контрольная работа по Информатике 6
Работа добавлена на сайт bukvasha.net: 2015-10-25Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Вариант 6
Измерение информации
№1.
В корзине лежат красные и черные клубки шерсти. Красных клубков 6. Сообщение о том, что достали черный клубок, несет 2 бита информации. Сколько всего клубков в корзине?
Решение:
N = 2 I I – количество информации
Iч = 2 бита
Nч = 22 = 4 черных клубка
6+4 = 10
Ответ: N = 10 клубков шерсти.
№2.
Сколько следует задать вопросов и как их следует формулировать, чтобы оценить сообщение о том, что вагон стоит на одном из 16 путей?
Решение:
Начальная неопределенность знаний составляет 16 возможных событий (вариантов путей). Для оптимального решения необходимо интервал постоянно делить пополам, т.е. задавать вопрос, на который можно ответить «да» или «нет», при ответе неопределенность будет уменьшаться в 2 раза и, следовательно, мы будем получать 1 бит информации.
Вагон находится на пути с номером больше 8? – Да (значит 9 10 11 12 13 14 15 16)
Вагон находится на пути с номером больше 12? - Да (значит 13 14 15 16)
Вагон находится на пути с номером больше 14? – нет (значит 13 14)
Вагон находится на пути с номером 13? - нет (значит вагон находится на 14 пути)
Мы задали 4 вопроса, получили 4 бит информации.
Если мы будем область поиска делить точно по полам мы обязательно найдем ответ с помощью 4 вопросов.
Если бы мы угадывали номер пути произвольно, то при большом везении (вероятность этого мала) нам потребовалось бы всего 1 вопрос, при невезении не меньше 4 вопросов
На вопрос задачи «Сколько следует задать вопросов, чтобы оценить сообщение о том, вагон стоит на одном из 16 путей», угадывающий мог дать 16 вариантов ответа. Когда мы получаем ответ на вопрос, имеющий 16 вариантов ответа, наша неопределенность уменьшается в 16 раз, и мы получаем информацию (по формуле Хартли) в количестве Н =log2 16 = 4 ,0000
Значит, мы можем сразу, не придумывая вопросы, пользоваться формулой Хартли при решении подобных задач.
№3.
Имеются два ящика, в каждом из которых по 12 шаров. В первом – 3 белых, 3 черных и 6 красных; во втором – каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов?
Решение:
Первый ящик
H1 = -3/12* log2 3/12-3/12* log2 3/12-6/12* log2 6/12 = 1,85 бит
Второй ящик
если символы встречаются с равными вероятностями;
Формула Хартли N=4,
Н2 = log2 N = log2 4 = 0,6 бит
Ответ: Для второго ящика исход опыта более определен
№4.
Измерьте информационный объем компьютерного текста “Ура! Закончились каникулы!!” (с точки зрения технического подхода, то есть не учитывая смысл сообщения). Выразите этот объем в битах, байтах, килобайтах.
Решение:
1 символ =8 бит = 1 байт. Всего, включая пробелы - 27 символов
27*8=216 бит
27/1024= 0,026 Кбайт
Ответ: 216 бит, 27 байт, 0,026 Кбит
Системы счисления
№5. Перевести данное число из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную.
444,125(10)
Переведем данное число в двоичную систему:
444,125(10) → (2)
Сначала переведем целую часть
444 | 2 | | | | | | | |
444 | 222 | 2 | | | | | | |
0 | 222 | 111 | 2 | | | | | |
| 0 | 110 | 55 | 2 | | | | |
| | 1 | 54 | 27 | 2 | | | |
| | | 1 | 26 | 13 | 2 | | |
| | | | 1 | 12 | 6 | 2 | |
| | | | | 1 | 6 | 3 | 2 |
| | | | | | 0 | 2 | 1 |
| | | | | | | 1 | |
| | | | | | | | |
Записываем с результат нижней цифры: 444 (10) = 110111100(2)
Для перевода дробных чисел из десятичной системы счисления
в систему счисления с основанием 2, нужно последовательно умножать дробь на 2, при этом перемножаются только дробные части. Дробь записывается в виде целых частей получающихся произведений, начиная с первого.
0,125 (10) → (2)
| 0 | 125 |
| | 2 |
| 0 | 25 |
| | 2 |
| 0 | 5 |
| | 2 |
| 1 | 0 |
Записываем с верхнего разряда под чертой: 0,125 (10) → 0,001(2)
Записываем полный ответ
444,125(10) → 110111100,001 (2)
Переведем данное число в восьмеричную систему:
444,125(10) → (8)
Сначала переведем целую часть
444 | 8 | |
440 | 55 | |
4 | 48 | 8 |
| 7 | 6 |
| | |
Записываем с нижней цифры: 444(10) = 674(8)
Для перевода дробных чисел из десятичной системы счисления
в систему счисления с основанием 8, нужно последовательно умножать дробь на 8, при этом перемножаются только дробные части. Дробь записывается в виде целых частей получающихся произведений, начиная с первого.
0,125(10) → (8)
0 | 125 |
| 8 |
1 | 0 |
Записываем с верхнего разряда под чертой: 0,125 (10) → 0,1(8)
Записываем полный ответ
444,125(10) → 674,1(8)
Переведем данное число в шестнадцатеричную систему:
444,125(10) → (16)
Сначала переведем целую часть
444 | 16 | |
432 | 27 | 16 |
12(С) | 16 | 1 |
| 11(В) | |
Записываем с нижней цифры: 444 (10) = 1ВС(16)
Для перевода дробных чисел из десятичной системы счисления
в систему счисления с основанием 16, нужно последовательно умножать дробь на 16, при этом перемножаются только дробные части. Дробь записывается в виде целых частей получающихся произведений, начиная с первого.
0,6875(10) → (16)
0 | 125 |
| 16 |
2 | 0 |
Записываем с верхнего разряда под чертой: 0,125 (10) → 0,2(16)
Записываем полный ответ
444,125(10) → 1ВС,2(16)
Ответ: 444,125(10) = 110111100,001 (2), 674,1(8), 1ВС,2(16)
№6. Выполнить вычитание в двоичной, восьмеричной и шестнадцатеричной системах счисления.
а) 1000101001,1(2) – 1111101,1(2);
1000101001,1(2)
– 1111101,1(2)
110101100,0(2)
Проверим правильность вычислений переводом исходных данных и результатов в десятичную систему счисления:
Переведем в десятичную систему счисления первое исходное число:
19080706150413020110,1-1(2) →(10)
1*2-1+1*20+0*21+0*22+1*23+0*24+1*25+0*26+0*27+0*28+1*29= =0,5+1+8+32+512=553,5(10)
Переведем в десятичную систему счисления второе исходное число:
161514131201101-1 (2) →(10)
1*2-1 +1*20+0*21+1*22+1*23+1*24+1*25+1*26=0,5+1+4+8+16+32+64=125,5(10)
Переведем в десятичную систему счисления результат вычитаний двух исходных чисел:
110101100
181706150413120100(2) →(10)
0*20+0*21+1*22+1*23+0*24+1*25+0*26+1*27+1*28=0+0+4+8+0+32+0+128+256=428(10)
Проверка:
553,59(10) – 125,5(10)= 428(10)
б)1265,2(8) – 610,2(8);
1265,2(8)
–610,2(8)
455,0(8)
Проверим правильность вычислений переводом исходных данных и результатов в десятичную систему счисления:
Переведем в десятичную систему счисления первое исходное число:
13226150,2-1 (8) →(10)
2*8-1+5*80+6*81+2*82+1*83= 0,25+5+48+128+512=693,25(10)
Переведем в десятичную систему счисления второе исходное число:
621100,2-1 (8) →(10)
2*8-1+0*80+1*81+6*82=392,25(10)
Переведем в десятичную систему счисления результат вычитания двух исходных чисел:
425150 (8) →(10)
4*82+5*81+5*80= 301(10)
Проверка:
693,25(10) – 392,25(10)= 301(10)
в) 409,4(16) – 270,4(16)
409,4(16)
– 270,4(16)
199,0(16)
Проверим правильность вычислений переводом исходных данных и результатов в десятичную систему счисления:
Переведем в десятичную систему счисления первое исходное число:
420190,4-1 (16) →(10)
4*16-1+9*160+0*161+4*162= 0,25+9+1024=1033,25(10)
Переведем в десятичную систему счисления второе исходное число:
227100,4-1 (16) →(10)
4*16-1+0*160+7*161+2*162= 0,25+0+112+512= 624,25(10)
Переведем в десятичную систему счисления результат вычитания двух исходных чисел:
129190 (16) →(10)
9*160+9*161+1*162=9+144+256= 409(10)
Проверка:
1033,25(10) – 624,25(10)= 409(10)
№7. Выполнить умножение в двоичной, восьмеричной и шестнадцатеричной системах счисления. Проверить правильность вычислений переводом исходных данных и результатов в десятичную систему счисления.
а) 111010(2) ´ 1100000(2);
1100000(2)
´ 111010(2)
0000000
1100000
+ 0000000
1100000
1100000
1100000
1010111000000 (2)
Проверим правильность вычислений переводом исходных данных и результатов в десятичную систему счисления:
Переведем в десятичную систему счисления первое исходное число:
151413021100 (2) →(10)
0*20+1*21+0*22+1*23+1*24+1*25=0+2+0+8+16+32=58(10)
Переведем в десятичную систему счисления второе исходное число:
1403021110(2)→(10)
0*20+0*21+0*22+0*230*24+1*25+1*26=32+64=96(10)
Переведем в десятичную систему счисления результат умножения двух исходных чисел:
11201111009181716050403020100 (2) →(10)
=5568 (10)
Проверка:
58(10) * 69(10) = 5568(10)
Представление информации в памяти ЭВМ
№8 Закодировать данный текст, используя таблицу ASCII-кодов.
компьютеризация
Решение:
Слово компьютеризация по кодировочной таблице ASCII будет выглядеть в следующем виде:
AA AE AC AF EC EE E2 A5 E0 A8 A7 A0 E6 A8 EF
№9. Записать дополнительный код числа, интерпретируя его как восьмибитовое целое со знаком.
55
Решение:
Переводим данное число в двоичное.
55 | 2 | | | | | | | |
54 | 27 | 2 | | | | | | |
1 | 26 | 13 | 2 | | | | | |
| 1 | 12 | 6 | 2 | | | | |
| | 1 | 6 | 3 | 2 | | | |
| | | 0 | 2 | 1 | | | |
| | | | 1 | | | | |
110111
Так как длина двоичного числа меньше 8, то слева добавляем нужное количество нулей (чтобы длина кода стала равна 8 бит)
00110111
Дополнительный прямой код целого положительного числа совпадает с его прямым кодом
Ответ : 00110111
№10. Записать дополнительный код числа, интерпретируя его как шестнадцатибитовое целое со знаком.
–26686
Решение:
Переводим данное число в двоичное.
26686 | 2 | | | | | | | | | | | | | |
26686 | 13343 | 2 | | | | | | | | | | | | |
0 | 13342 | 6671 | 2 | | | | | | | | | | | |
| 1 | 6670 | 3335 | 2 | | | | | | | | | | |
| | 1 | 54 | 1667 | 2 | | | | | | | | | |
| | | 1 | 1666 | 833 | 2 | | | | | | | | |
| | | | 1 | 832 | 416 | 2 | | | | | | | |
| | | | | 1 | 4016 | 208 | 2 | | | | | | |
| | | | | | 0 | 208 | 104 | 2 | | | | | |
| | | | | | | 0 | 104 | 52 | 2 | | | | |
| | | | | | | | 0 | 52 | 26 | 2 | | | |
| | | | | | | | | 0 | 26 | 13 | 2 | | |
| | | | | | | | | | 0 | 12 | 6 | 2 | |
| | | | | | | | | | | 1 | 6 | 3 | 2 |
| | | | | | | | | | | | 0 | 2 | 1 |
| | | | | | | | | | | | | 1 | |
110100000111110 – двоичный код
Записываем шестнадцатибитное целое:
0110 1000 0011 1110 – прямой код
Инвертируем его:
1001 0111 1100 0001
Прибавляем к инвертируемому коду единицу
1001 0111 1100 0001
+ 1
1001 0111 1100 0010
Ответ : 1001 0111 1100 0010
№11. Записать в десятичной системе счисления целое число, если дан его дополнительный код
0000010101011010
Решение:
Поскольку в старшем разряде записан нуль, то результат будет положительным. Переводим двоичное число:
0*215+0*214+0*213+0*212+0*211+1*210+0*29+1*28+0*27+1*26+0*25+1*24+1*23+0*22+1*21+0*20=1370(10)
Ответ: 1370(10)
№12. Записать в десятичной системе счисления целое число, если дан его дополнительный код
1001110100001011
Решение:
Здесь записан код отрицательного числа. Исполняем алгоритм
1) Вычитаем из кода число 1
1001110100001011(2) – 1(2)= 1001110100001010(2)
2) Инвертируем код
0110001011110101
0*215+1*214+1*213+0*212+0*211+0*210+1*29+0*28+1*27+1*26+1*25+1*24+0*23+1*22+0*21+1*20=6901(10)
Ответ: 6901(10)
№ 13. Записать код вещественного числа, интерпретируя его как величину типа Double
–434,15625
1) Переведем модуль данного числа в двоичную систему счисления:
Двоичная запись модуля этого числа имеет вид 110110010,00101
2) нормализуем двоичное число, т.е. запишем в виде M × 2p, где M — мантисса (ее целая часть равна 1(2)) и p — порядок, записанный в десятичной системе счисления;
Имеем 110110010,00101 = 1, 1011001000101 × 28.
3) прибавим к порядку смещение, и переведем смещенный порядок в двоичную систему счисления;
Получаем смещенный порядок 8 + 1023 = 1031. Далее имеем 1031(10) = 10000000111(2).
4) учитывая знак заданного числа (0 — положительное; 1 — отрицательное), выписываем его представление в памяти ЭВМ.
S | Смещенный порядок | Мантисса | |
1 | 10000000111 | | |
63 | 52 | 0 |
Компактно полученный код стоит записать следующим образом: 407B228000000000 (16).
№ 14. Дан код величины типа Double. Преобразовать его в число.
C086EB0000000000
Решение:
C086EB0000000000 или
S | Смещенный порядок | Мантисса | |
1 | 10000001000 | | |
63 | 52 | 0 |
1) Прежде всего замечаем, что это код отрицательного числа, поскольку в разряде с номером 63 записана единица. Получим порядок этого числа: 10000001000 (2) = 1032(10); 1032 – 1023 = 9.
2) Число имеет вид 1,011011101011 * 29 или 1011011101,0110
3) Переводом в десятичную систему счисления получаем 733,375(10)
Ответ: 733,375(10)
Кодирование сообщений
Задано сообщение, состоящее из букв алфавита {a, b, c, d, e, f, g, h, i}.
Сообщение: aaaaaaabbbbbbccccdddeefffggghhi
Для данного алфавита:
№ 15. Построить равномерный код.
Решение:
Построим для данного алфавита равномерный код
0 1 2 3 4 5 6 7 8 | a b c d e f g h i | 0000 0001 0010 0011 0100 0101 0110 0111 1000 |
№ 16. Построить код Шеннона – Фано.
Символ | Частота встречаемости |
a b c d e f g h i | P(a)=7/31=0,225806 P(b)=6/31=0,193548 P(c)=4/31=0,120329 P(d)=3/31=0,096774 P(e)=2/31=0,064516 P(f)=3/31=0,096774 P(g)=3/31=0,096774 P(h)=2/31=0,064516 P(i)=1/31=0,032258 |
Сортируем последовательность по убыванию вероятности появления
Символ | Частота встречаемости | Разряды | Кодовая комбинация | |||||
1 | 2 | 3 | 4 | 5 | 6 | |||
a | 0,225806 | 0 | 0 | | | | | 00 |
b | 0,193548 | 0 | 1 | | | | | 01 |
c | 0,120329 | 1 | 0 | 0 | | | | 100 |
d | 0,096774 | 1 | 0 | 1 | | | | 101 |
f | 0,096774 | 1 | 1 | 0 | | | | 110 |
g | 0,096774 | 1 | 1 | 1 | 0 | | | 1110 |
e | 0,064516 | 1 | 1 | 1 | 1 | 0 | | 11110 |
h | 0,064516 | 1 | 1 | 1 | 1 | 1 | 0 | 111110 |
i | 0,032258 | 1 | 1 | 1 | 1 | 1 | 1 | 111111 |
Разбиваем последовательность на 2 по возможности равновероятные группы
Точно пополам поделить не возможно. Есть два варианта разбиения:
a,b,c (0,544)/d,f,g,e,h,i(0,42) и a,b (0,42) / c,d,f,g,e,h,i (0,55). Остановимся на втором варианте.
В идеальном случае отношение этих вероятностей должно быть равным единице. Для первого варианта разбиения отношение меньшей вероятности к большей равно 0,55/0,42 = 1,31. Для второго варианта разбиения это отношение равно 0,42/0,55= 0,76.
Первому разряду кода символов первой группы присваивается значение 0, первому разряду кода символов второй группы - 1.
Далее для каждой из 2х групп выполняем шаги 1)-3)
№ 17. Построить код Хаффмана.
Строим кодовое дерево
| | | | | | | | | | | | | | | | |
| | | | | | 1 | | | | | | | | | | |
| | 0 | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
| | 0,645 | 1 | | | | | | | 1 | | | | | | |
| | | | 0,226 | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
| 0 | | | | | | | | 0,355 | | | | | 1 | | |
| | | | | | | | 0 | | 1 | | | | | | |
| 0,419 | | | 0 | | | 0,194 | | | | 0,161 | | | | 0,097 | |
0 | | 1 | | | | 0 | | 1 | | 0 | | 1 | | 0 | | 1 |
0,226 | | 0,194 | | 0,129 | | 0,097 | | 0,097 | | 0,097 | | 0,065 | | 0,065 | | 0,032 |
a | b | c | d | f | g | e | h | i | ||||||||
| | | | | | | | | | | | | | | | |
a b c d e f g h i | 000 001 010 100 111 101 110 0110 0111 |
№ 18. Найти избыточность равномерного кода и кода Хаффмана
№ 19. Закодировать первые два символа сообщения кодом Хаффмана и построить для полученного двоичного сообщения код Хемминга.
Проектирование конечного автомата
№ 20. Для заданного конечного автомата построить:
- Описание множества входных, выходных сигналов, и множества возможных состояний.
- Функцию переходов состояний и функцию выходов
- Граф переходов
- Закодированную таблицу реализации конечного автомата
Автомат: Телевизор
Машина Поста
№ 21. Решить данную задачу с помощью эмулятора Машины Поста. Решение предоставить в виде файла Фамилия_номер_варианта.pst.
Задача:
На ленте машины Поста расположен массив из 2*N отмеченных секций. Составить программу, по которой машина Поста раздвинет на расстояние в 1 секцию две половины данного массива. Каретка находится над крайней правой меткой массива
Распознавание образов
№ 22. Построить классы объектов для распознавания:
- выделить существенные (определяющие) признаки классифицируемых объектов
- провести идентификацию классов (определить названия и признаки классов)
- привести пример распознавания
Объекты: легковые автомобили
№ 23. Построить граф перехода конечного автомата распознавателя (распознающую грамматику) и синтаксическую диаграмму (порождающую грамматику) для алфавита и соответствующего ему языка
Алфавит и язык: V ={a, b, c}; L = {сac, cbc, ca}
Информационное моделирование
№ 24. Разработать информационную модель объекта
- Определить субъекта моделирования (кто создает модель)
- Сформулировать цель моделирования (зачем создается модель)
- 3 моделирования)
- Представить модель в 2х различных формах (формы: текстовое описание, график, формула, граф, таблица, схема, рисунок и т.д.)
- Классифицировать созданную модель в соответствии с классификацией приведенной на лекции.
Результаты предоставить в виде компьютерной презентации.
Объект моделирования: Снегопад