Лабораторные работы по дисциплине "Основы теории информации"
учебно-методическое пособие по информатике и икт по теме

Департамент общего и профессионального образования РФ

Государственное бюджетное образовательное учреждение

среднего профессионального образования

«Брянский профессионально-педагогический колледж»

Лабораторные работы

Дисциплина: _Основы теории информации

Для специальности (группы специальностей)  230701  Прикладная информатика (по отраслям)_

Специальности профиля подготовки:   Прикладная информатика (по отраслям)

Брянск

2013

Лабораторная работа №1.

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

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

Методические указания.

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

Все системы счисления делятся на позиционные и непозиционные.

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

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

Количество p различных цифр, употребляемых в позиционной системе определяет название системы счисления и называется основанием системы счисления "p".

В десятичной системе используются десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; эта система имеет основанием число десять.

Задание 1. Запишите развернутую и краткую формы записи любого числа.

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

Двоичная система счисления.  Используется две цифры: 0 и 1.

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

Употребляется в ЭВМ как вспомогательная для записи информации в сокращенном виде. Для представления одной цифры восьмеричной системы используется три двоичных разряда (триада) (Таблица 1).

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

буквами: 10=A,

11=B,

12=C,

13=D,

14=E,

15=F.

Шестнадцатеричная система используется для записи информации в сокращенном виде. Для представления одной цифры шестнадцатеричной системы счисления используется четыре двоичных разряда (тетрада) (Таблица 1).

Таблица 1. Наиболее важные системы счисления.

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

Перевод чисел в десятичную систему осуществляется путем составления

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

подсчитывается значение суммы.

Задание 2.

Перевести 10101101.101 из «2» в «16», «8» и «10» с.с.

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

Задание 3. Переведите самостоятельно.

а) Перевести 703.048 из «10» в «2», затем в «8» и наконец, в «16»

б) Перевести B2E.416 из «16» в «10», затем в «8».

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

Задание 4.

а) Перевести 18110 из «10» в «2».

б) Перевести 62210 из «8» в «2», затем в «10».

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

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

Задание 5. Перевести 0.312510

Замечание. Конечной десятичной дроби в другой системе счисления может  соответствовать бесконечная (иногда периодическая) дробь. В этом случае количество знаков в представлении дроби в новой системе берется в зависимости от требуемой точности.

Задание 6. Перевести 0.6510 из «10» в «2» с.с. Точность 6 знаков.

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

Задание 7.

Перевести 23.12510 из «10» в «2» с.с.

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

Задание 8.

а)Перевести 305.47 из «8» в «10» с.с.

б)Перевести 7B2.E16 из «16» в «10».

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

Задание 9.

а) Перевести 1101111001.1101 из «2» в «8» с.с.

б) Перевести 11111111011.100111 из «2» в «16» с.с.

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

Задание 10.

Перевести 175.248 "16" с.с.

Двоичная арифметика.

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

Задание 11. Выполнить сложение двоичных чисел:

а) X=1101, Y=101;

б) X=1101, Y=101, Z=111;

При вычитании двоичных чисел в данном разряде при необходимости занимается 1 из старшего разряда. Эта занимаемая 1 равна двум 1 данного разряда.

Задание 12. Заданы двоичные числа X=10010 и Y=101. Вычислить X-Y.

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

Пример. 1001* 101=?

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

Пример. 1100.011 : 10.01=

Самостоятельная работа.

Выполнить перевод числа в соответствии с вариантом.

1. Перевести десятичное число А=121 в двоичную систему счисления.

2. Перевести двоичное число А=10001010111,01 в десятичную систему

счисления.

3. Перевести десятичное число А=135,656 в двоичную систему счисления с

точностью до пяти знаков запятой.

4. Перевести двоичное число А=10111011 в десятичную систему счисления

методом деления на основание.

5. Перевести восьмеричное число А=345,766 в двоичную систему счисления.

6. Записать десятичное число А=79,346 в двоичнодесятичной

форме.

7. Перевести десятичную дробь 64

A = 63 9 в двоичную систему счисления.

8. Перевести десятичное число А=326 в троичную систему счисления.

9. Перевести десятичную дробь 40

A = 63 5 в двоичную систему счисления.

10. Перевести десятичное число А=15,647 в двоичную систему счисления.

11. Перевести десятичное число А=1211 в пятеричную систему счисления.

12. Перевести десятичную дробь А=0,625 в двоичную систему счисления.

13. Перевести двоичную дробь А=0,1101 в десятичную систему счисления.

14. Перевести десятичное число А=113 в двоичную систему счисления.

15. Перевести двоичное число А=11001,01 в десятичную систему счисления.

16. Перевести десятичное число А=96 в троичную систему счисления.

Лабораторная работа №2. Измерение количества информации.

Цель работы: научить решать задачи на количественное измерение информационного объема текстовой информации.

Методические указания.

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

Субъективный (содержательный) подход

При данном подходе информация – это сведения, знания, которые человек получает из различных источников. Таким образом,  сообщение информативно (содержит ненулевую информацию), если оно пополняет знания человека.

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

При содержательном подходе возможна качественная оценка информации: достоверность, актуальность, точность, своевременность, полезность, важность, вредность…

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

Субъективный подход основывается на том, что получение информации, ее увеличение, означает уменьшение незнания или информационной неопределенности (определение 2).

Единица измерения количества информации называется бит (bit – binary digit), что означает двоичный разряд.

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

Сообщение, уменьшающее информационную неопределенность (неопределенность знаний) в два раза, несет для него 1 бит информации.

Что же такое «информационная неопределенность»?

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

Пример_1: Книга лежит на одной из двух полок – верхней или нижней. Сообщение о том, что книга лежит на верхней полке, уменьшает неопределенность ровно вдвое  и несет 1 бит информации.

Сообщение о том, что произошло одно событие из двух равновероятных, несет 1 бит информации.

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

Пример_3: Ваш друг живет в 16-ти этажном доме. Сколько информации содержит сообщение о том, что друг живет на 7 этаже.

Решение: Информационная неопределенность (количество возможных результатов события) равна 16. Будем задавать вопросы, на которые можно ответить только «да» или «нет». Вопрос будем ставить так, чтобы каждый ответ приносил 1 бит информации, т.е. уменьшал информационную неопределенность в два раза.

Задаем вопросы: - Друг живет выше 8-го этажа?

• Нет.

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

• Друг живет выше 4-го этажа?
• Да.

Число вариантов уменьшилось еще в два раза, получен еще 1 бит информации.

• Друг живет выше 6-го этажа?
• Да.

После данного ответа осталось два варианта: друг живет или на 7 этаже, или на 8 этаже. Получен еще 1 бит информации.

• Друг живет на 8-м этаже?
• Нет.
• Все ясно. Друг живет на 7-м этаже.

Каждый ответ уменьшал информационную неопределенность в два раза. Всего было задано 4 вопроса. Получено 4 бита информации. Сообщение о том, что друг живет на 7-м этаже 16-ти этажного дома несет 4 бита информации.

Научный подход к оценке сообщений был предложен еще в 1928 году Р. Хартли.

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

2x = N

где x – количество информации или информативность события (в битах);

      N – число равновероятных событий (число возможных выборов).

Данная формула является показательным уравнением относительно неизвестной x. Решая уравнение,  получим формулу определения количества информации, содержащемся в сообщении о том, что произошло одно из N равновероятных событий, которая имеет вид:

x = log2N

логарифм от N по основанию 2.

Если N равно целой степени двойки, то такое уравнение  решается легко, иначе справиться с решением поможет таблица логарифмов.

Если N = 2 (выбор из двух возможностей), то x = 1 бит.

Возвращаясь к примеру_3, если воспользоваться формулой для подсчета количества информации в сообщении о том, что друг живет на 7-м этаже 16-ти этажного дома, то x = log216 = 4 бита.

Пример_4: Какое количество информации несет сообщение о том, что встреча назначена на июль?

Решение: В году 12 месяцев, следовательно, число равновероятных событий или число возможных выборов N = 12. Тогда количество информации x = log212. Чтобы решить это уравнение воспользуемся таблицей логарифмов или калькулятором.

Ответ:  x = 3,58496 бита.

Пример_5: При угадывании целого числа в диапазоне от1 до N было получено 8 бит информации. Чему равно N?

Решение: Для того, чтобы найти число, достаточно решить уравнение N=2x , где x = 8. Поскольку 28 = 256, то N = 256. Следовательно, при угадывании любого целого числа  в диапазоне от 1 до 256 получаем 8 бит информации.

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

Объективный (алфавитный) подход к измерению информации

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

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

Информация рассматривается как последовательность символов, знаков (определение3).

Количество символов в сообщении называется длиной сообщения.

Основой любого языка является алфавит.

Алфавит – это  набор знаков (символов), в котором определен их порядок.

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

Например, мощность алфавита из русских букв равна 33:

мощность алфавита из английских букв равна 26.

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

Каждый символ несет x бит информации. Количество информации x, которое несет один символ в тексте, зависит от мощности алфавита M, которые связаны формулой 2x = M. Следовательно  x = log2M бит.

Количество информации в тексте, состоящем из K символов, равно K*x  или

K* log2M, где x – информационный вес одного символа алфавита.

Удобнее измерять информацию, когда мощность алфавита M равна целой степени числа 2. Для вычислительной системы, работающей с двоичными числами, также более удобно представление чисел в виде степени двойки.

Пример_6, в 2-символьном алфавите каждый символ несет 1 бит информации (2x = 2, откуда x = 1 бит).

Если M=16, то каждый символ несет 4 бита информации, т.к. 24 = 16.

Если M=32, то один символ несет 5 бит информации.

При M=64, один символ «весит» 6 бит и т.д.

Пример_7: Племя “Обезьяны” пишет письма, пользуясь 32-символьным алфавитом. Племя “Слоны” пользуется 64-символьным алфавитом. Вожди племен обменялись письмами. Письмо племени “Обезьяны” содержало 90 символов, а письмо племени “Слоны” – 80 символов. Сравните объем информации, содержащейся в письмах.

Решение: Мощность алфавита племени “Обезьяны” равна 32, информационный вес одного символа алфавита log232 = 5 бит. Количество информации в тексте, состоящем из 90 символов, равно 90*log232 = 450 бит.

Рассуждая аналогично про племя “Слоны”, получим: 80*log264 = 480 бит.

Следовательно, объем информации в письме вождя племени “Слоны” больше объема информации, которую передал в письме вождь племени “Обезьяны”.

Есть алфавит, который можно назвать достаточным. Это алфавит мощностью 256 символов. Алфавит из 256 символов используется для представления текстов в компьютере. В этом алфавите можно поместить практически все необходимые символы: латинские и русские буквы, цифры, знаки арифметических операций, скобки, знаки препинания, знаки псевдографики. Поскольку 256=28, то один символ этого алфавита «весит» 8 бит.

8 бит информации присвоили свое название – байт.

Байт – поле из 8 последовательных бит. Байт широко используется как единица измерения количества информации.

1 байт = 8 бит

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

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

В любой системе единиц измерения существуют основные единицы и производные от них.

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

1 килобайт = 1 Кб = 210 байт = 1024 байта

1 мегабайт = 1 Мб = 210 Кб = 1024 Кб =  1048576 байт

1 гигабайт = 1 Гб = 210 Мб = 1024 Мб =  1048576 Кб = 1073741824 байт

Пример_8: Книга, набранная с использованием текстового редактора,  содержит 70 страниц, на каждой странице 38 строк, в каждой строке 56 символов. Определить объем информации, содержащейся в книге.

Решение: Мощность компьютерного алфавита равна 256 символов. Один символ несет 1 байт информации. Значит 1 страница содержит 38*56=2128 байт информации. Объем всей информации в книге 2128*70=148960 байт.

Если оценить объем  книги в килобайтах и мегабайтах, то

148960/1024 = 145,46875 Кбайт.

145,46875/1024 = 0,142059 Мбайт.

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

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

Контрольные задания

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

Задачи на измерение информации

1. Измерьте информационный объем сообщения «Ура! Скоро Новый год!» в битах, байтах, килобайтах (Кб), мегабайтах (Мб).

Указание: считается, что текст набран с помощью компьютера, один символ алфавита несет 1 байт информации. Пробел – это тоже символ в алфавите мощностью 256 символов.

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

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

3. Сколько таких учебников может поместиться на дискете 1,44 Мб, на винчестере в 1 Гб.

4. В детской игре «Угадай число» первый участник загадывает целое число от 1 до 32. Второй участник задает вопросы: «Загаданное число больше числа ___?». Какое количество вопросов при правильной стратегии гарантирует угадывание?

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

5. Яд находится в одном из 16 бокалов. Сколько единиц информации будет содержать сообщение о бокале с ядом?

6. Сколько бит информации несет сообщение о том, что из колоды в 32 карты достали «даму пик»?

7. Проводят две лотереи: «4 из 32» и «5 из 64» Сообщение о результатах какой из лотерей несет больше информации?

8. Информационное сообщение объемом 1.5 Кбайта содержит 3072 символа. Сколько символов содержит алфавит, при помощи которого было записано это сообщение? (Объяснение решения задачи на доске).

9. Подсчитать в килобайтах количество информации в тексте, если текст состоит из 600 символов, а мощность используемого алфавита – 128 символов.

10. Скорость информационного потока – 20 бит/сек. Сколько времени потребуется для передачи информации объемом в 10 килобайт.

11. Сравните (поставьте знак отношения)

• 200 байт и 0,25 Кбайт.
• 3 байта и 24 бита.
• 1536 бит и 1,5 Кбайта.
• 1000 бит и 1 Кбайт.
• 8192 байта и 1 Кбайт.

12. В барабане для розыгрыша лотереи находится 32 шара. Сколько информации содержит сообщение о первом выпавшем номере (например, выпал номер 15)?

13. При игре в кости используется кубик с шестью гранями. Сколько бит информации получает игрок при каждом бросании кубика?

14. Книга, набранная с помощью компьютера, содержит 150 страниц; на каждой странице — 40 строк, в каждой строке — 60 символов. Каков объем информации в книге?

15. Подсчитайте объем информации, содержащейся в романе А. Дюма "Три мушкетера", и определите, сколько близких по объему произведений можно разместить на одном лазерном диске? (590 стр., 48 строк на одной странице, 53 символа в строке).

16. На диске объемом 100 Мбайт подготовлена к выдаче на экран дисплея информация: 24 строчки по 80 символов, эта информация заполняет экран целиком. Какую часть диска она занимает?

17. В школьной библиотеке 16 стеллажей с книгами. На каждом стеллаже 8 полок. Библиотекарь сообщил Пете, что нужная ему книга находится на пятом стеллаже на третьей сверху полке. Какое количество информации библиотекарь передал Пете?

18. В коробке лежат 7 цветных карандашей. Какое количество информации содержит сообщение, что из коробки достали красный карандаш?

19. Какое количество информации несет сообщение: “Встреча назначена на сентябрь”.

20. Сообщение занимает 3 страницы по 25 строк. В каждой строке записано по 60 символов. Сколько символов в использованном алфавите, если все сообщение содержит 1125 байтов?

21. Юстасу необходимо передать следующее сообщение:

Дорогой Алекс! От всей души поздравляю с

успешной сдачей экзамена по информатике.

Желаю дальнейших успехов. Ваш Юстас.

Пеленгатор определяет место передачи, если она длится не менее 3 минут. С какой скоростью (бит/с) Юстас должен передавать радиограмму?

22. Измерьте информационный объем сообщения “Ура!  Закончились каникулы!!” (с точки зрения технического подхода, то есть не учитывая смысл сообщения). Выразите этот объем в битах, байтах, килобайтах.

23. Измерьте примерную информационную емкость 1 страницы учебника, всего учебника. Сколько таких учебников может поместиться на дискете емкостью 360  Кбайт, 1.44 Мбайт, на винчестере в 420 Мбайт, в 6,4Гбайт ?

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

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

25. Предположим, вероятность того, что вы получите за контрольную работу оценку “5”, равна 0,6; вероятность получения “4” равна 0,2; вероятность получения “3” - 0,2. Определите, сколько бит информации будет нести сообщение о результатах контрольной работы в каждом из возможных случаев.

26. Дано:

Кол-во цветов = 2

Размер картинки = 7*14 точек

I = ?

27. Дано:

Кол-во цветов = 8

Размер картинки = 17*24 точки

I = ?

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

29. (Задание А2  демоверсии 2004 г.)

30. Считая, что каждый символ кодируется одним байтом, оцените информационный объём предложения: «Мой дядя самых  честных правил, Когда не в шутку занемог, Он уважать себя заставил И лучше выдумать не мог.»

31. Шахматная доска состоит из 64  полей: 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?

32. Получено сообщение, информационный объём которого равен 32 битам. Чему равен этот объём в байтах?

33. Каждое показание счётчика, фиксируемое в памяти компьютера, занимает 10 бит. Записано 100 показаний этого датчика. Каков информационный объём снятых значений в байтах?

34. Для хранения растрового изображения размером 128*128 пикселей отвели 4 килобайта памяти. Каково максимально возможное число цветов в палитре изображения?

Решение.

Воспользуемся формулами:

В нашем случае:

Подставив значения (8) и (9) в (5), получим, что: 215 = 214 *i, откуда i=2.

Тогда по формуле (6): <Количество цветов> =N = 2i=22=4, что соответствует ответу №4.

Ответ: 4.

35. Считая, что каждый символ кодируется одним байтом, оцените информационный объём следующего предложения в кодировке КОИ-8 (в байтах):

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

36. Считая, что каждый символ кодируется 16-ю битами, оцените информационный объём следующего предложения в кодировке Unicode (в байтах):

Каждый символ кодируется восемью битами.

37. Сколько существует различных последовательностей из символов «а» и «б» длиной ровно в 10 символов?

38. В зрительном зале две прямоугольные области зрительских кресел: одна 10х12, а другая 17х8. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?

39. Сообщение передано в семибитном коде. Каков его информационный объём в байтах, если известно, что передано 2000 символов?

40. В алфавите формального (искусственного) языка всего два знака-буквы («0» и «Х»). Каждое слово этого языка состоит всегда из пяти букв. Какое максимальное число слов возможно в этом языке?

41. Алфавит племени содержит всего 8 букв. Какое количество информации несет одна буква этого алфавита?

42. Имеется тест, объем которого 20 килобайт (на каждой странице теста 40 строк по 64 символа в строке, 1 символ занимает 8 бит). Определить количество страниц в тесте.

43. Сколько байт в 32 Гбайт?

Творческое задание.

Пусть имеется носитель информации на 1,44 мБайта. Необходимо записать на него фотографию с размерами 1024*768 пикс и глубиной цвета 24 бита. Получится ли сделать это? Если нет, то какую глубину цвета можно использовать? Сколько цветов она будет включать? Решение задачи оформите в среде ЭТ Excel.

Лабораторная работа №3. Шифрование текстовой информации.

Цель работы: исследование простейших методов криптографической зашиты информации.

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

Шифры простой замены

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

Известная фраза Юлия Цезаря

VENI VI D I VICI, где

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

SBKF SFAF SFZF

при смещении на 4 символа влево.

Греческим писателем Полибием за 100 лет до н.э. был изобретен так называемый полибианский квадрат размером 5*5, заполненный алфавитом в случайном порядке. Греческий алфавит имеет 24 буквы, а 25-м символом является пробел. Для шифрования на квадрате находили букву текста и записывали в зашифрованное сообщение букву, расположенную ниже ее в том же столбце. Если буква оказывалась в нижней строке таблицы, то брали верхнюю букву из того же столбца.

Схема шифрования Вижинера. Таблица Вижинера представляет собой квадратную матрицу с n2 элементами, где n — число символов используемого алфавита. На рисунке показана верхняя часть таблицы Вижинера для кириллицы. Каждая строка получена циклическим сдвигом алфавита на символ. Для шифрования выбирается буквенный ключ, в соответствии с которым формируется рабочая матрица шифрования.

Таблица Вижинера 

Осуществляется это следующим образом. Из полной таблицы выбирается первая строка и те строки, первые буквы которых соответствуют буквам ключа. Первой размещается первая строка, а под нею — строки, соответствующие буквам ключа в порядке следования этих букв в ключе шифрования.  Пример  такой  рабочей  матрицы для ключа «книга» приведен на Рис. 3.1.3.

Процесс шифрования осуществляется следующим образом:

1. под каждой буквой шифруемого текста записываются буквы ключа. Ключ при этом повторяется необходимое число раз.

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

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

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

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

книгакнигак  нигакнигак   нигак  нигакниг акнигак ниг  ак нигак

Дальше осуществляется непосредственное шифрование в соответствии со вторым правилом, а именно: берем первую букву шифруемого текста (М) и соответствующую ей букву ключа (К); по букве шифруемого текста (М) входим в рабочую матрицу шифрования и выбираем под ней букву, расположенную в строке, соответствующей букве ключа (К),— в нашем примере такой буквой является Ч; выбранную таким образом букву помещаем в зашифрованный текст. Эта процедура циклически повторяется до зашифрования всего текста.

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

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

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

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

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

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

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

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

 Известны также и многие другие модификации метода.

Алгоритм перестановки

Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов. Рассмотрим некоторые разновидности этого метода, которые могут быть использованы в автоматизированных системах.

Самая простая перестановка — написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы

     ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ.

получится такой шифротекст:

     ИЛЕТО ХЫМКА ККАТТ ЕДУБЪ ТСУП

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

(например, О) до числа, кратного пяти:

     ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительные изменения, будет выглядеть по-другому:

      ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

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

Во время Гражданской войны в США в ходу был такой шифр: исходную фразу писали в несколько строк. Например, по пятнадцать букв в каждой (с заполнением последней строки незначащими буквами).

     П  У  С  Т  Ь  Б  У  Д  Е  Т  Т  А  К  К  А

     К  М  Ы  Х  О  Т  Е  Л  И  К  Л  М  Н  О  П

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

    ПКУМС  ЫТХЬО  БТУЕД  ЛЕИТК  ТЛАМК  НКОАП

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

Шифры сложной замены

Шифр Гронсфельда состоит в модификации шифра Цезаря числовым ключом. Для этого под буквами сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Зашифрованное сообщение получают примерно также, как в шифре Цезаря, но используют не одно жестко заданное смещение а фрагменты ключа.

Пусть в качестве ключа используется группа из трех цифр – 314, тогда сообщение

С О В Е Р Ш Е Н Н О С Е К Р Е Т Н О

3 1 4 3 1 4 3 1 4 3 1 4 3 1 4 3 1 4  

Ф П Ё С Ь З О С С А Х З Л Ф З У С С

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

Каждая строка в этой таблице соответствует одному шифру замены аналогично шифру Цезаря для алфавита, дополненного пробелом. При шифровании сообщения его выписывают в строку, а под ним ключ. Если ключ оказался короче сообщения, то его циклически повторяют. Зашифрованное сообщение получают, находя символ в колонке таблицы по букве текста и строке, соответствующей букве ключа. Например, используя ключ АГАВА, из сообщения ПРИЕЗЖАЮ ШЕСТОГО получаем следующую шифровку:

ПРИЕЗЖАЮ_ШЕСТОГО

АГАВААГАВААГАВАА

ПОИГЗЖЮЮЮШЕПТНГО

Такая операция соответствует сложению кодов ASCII символов сообщения и ключа по модулю 256.

3. Задание

Придумайте 3 фразы, каждая минимум из 7 слов. Реализуйте шифрование этой фразы всеми перечисленными видами шифрования.

Лабораторная работа №4. Кодировка текста. Шифрование текста с помощью таблицы ASCII-кода

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

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

Пример:

Рассмотрим последовательность строчных букв русского алфавита: а, б, в, г, д, е, ё, ж, з, и, й. к, л, м. н. о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, в, э, ю, я. Присвоив каждой букве номер от 0 до 33. получим простейший способ представления символов. Последнее число - 32 в двоичной форме имеет вид 100000, то есть для хранения символа в памяти понадобится 6 бит.Так как с помощью шести бит можно представить число 26 - 1 = 63, то шести бит будет достаточно для представления 64 букв.

Имеются разные стандарты для представления, символов, которые отличаются лишь порядком нумерации символов. Наиболее распространён американский стандартный код для информационного обмена - ASCII [American Standard-Code for Information Interchange] введён в США в 1963г. В 1977 году в несколько модифицированном виде он был принят в качестве всемирного стандарта Международной организации стандартов [International Standards Organization -. ISO] под названием ISO-646. Согласно этому стандарту каждому символу поставлено в соответствие число от 0 до 255. Символы от 0 до 127 - латинские буквы, цифры и знаки препинания - составляют постоянную часть таблицы. Остальные символы используются для представления национальных алфавитов. Конкретный состав этих символов определяется кодовой страницей. В русской версии ОC Windows95 используется кодовая, страница 866. В ОС Linux для представления русских букв более употребительна кодировка КОИ-8. Недостатки такого способа кодировки национального, алфавита очевидны. Во-первых, невозможно одновременное представление русских и ,например, французских букв. Во-вторых, такая кодировка совершенно непригодна для представления, китайских иероглифов. В 1991 году была создана некоммерческая организация Unicode, в которую входят представители ряда фирм (Borland. IBM, Noyell, Sun и др) и которая занимается развитием и внедрением нового стандарта. Кодировка Unicode использует 16 разрядов ,и может содержать 65536 символов. Это символы большинства народов мира, элементы иероглифов, спецсимволы, 5000 – мест для частного использования, резерв из 30000 мест.

Пример:

ASCII-код символа А= 6510 =4116= 010001112;

Unicode-код символа С= 6710=00000000011001112

Задания                                                                                                                        

1. Закодируйте свое имя, фамилию и отчество с помощью одной из таблиц (win-1251, KOI-8)
2. Раскодируйте ФИО соседа
3. Закодируйте следующие слова, используя таблицы ASCII-кодов: ИНФОРМАТИЗАЦИЯ, МИКРОПРОЦЕССОР, МОДЕЛИРОВАНИЕ
4. Раскодируйте следующие слова, используя таблицы ASCII-кодов:

88 AD E4 AE E0 AC A0 E2 A8 AA A0

50 72 6F 67 72 61 6D

43 6F 6D 70 75 74 65 72 20 49 42 4D 20 50 43

5. Текстовый редактор Блокнот

Открыть блокнот.

а) Используя клавишу Alt и малую цифровую клавиатуру раскодировать фразу: 145 170 174 224 174 255 170 160 173 168 170 227 171 235; 

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

б) Используя ключ к кодированию, закодировать слово  – зима;

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

Что вы заметили при выполнении этого задания во время раскодировки? Запишите свои наблюдения.

6. Текстовый процессор  MS Word.

Технология выполнения задания: рассмотрим на примере: представить в различных кодировках слово Кодировка

Решение:

• Создать новый текстовый документ в Word;
• Выбрать  – Команда –  Вставка – Символ.          
  В открывшемся окне «Символ» установить из: Юникод (шестн.),
• В наборе символов находим букву  К и щелкнем на ней левой кнопкой мыши (ЩЛКМ).
• В строке код знака  появится код выбранной буквы 041А (незначащие нули тоже записываем).
• У буквы о код – 043Е и так далее: д – 0434, и – 0438, р – 0440, о – 043Е, в – 0432, к – 043А, а – 0430.
• Установить Кириллица (дес.)
• К – 0202, о – 0238, д – 0228, и – 0232, р – 0240, о – 0238, в –0226, к – 0202, а –0224.

7. Открыть Word.

Используя окно «Вставка символа» выполнить задания: Закодировать слово Forest

а) Выбрать шрифт Courier New, кодировку ASCII(дес.) Ответ: 70 111 114 101 115 116
б) Выбрать шрифт Courier New, кодировку Юникод(шест.) Ответ: 0046 006F 0072 0665 0073 0074

в) Выбрать шрифт Times New Roman, кодировку Кирилица(дес.) Ответ: 70 111 114 101 115 116

г) Выбрать шрифт Times New Roman, кодировку ASCII(дес.) Ответ: 70 111 114 101 115 116

Вывод: _________________________________________________________

Выполнение лабораторной работы оформить в виде таблицы.

8. Буква Z  имеет десятичный код 90, а z – 122. Записать слово «sport» в десятичном коде.

9. С помощью десятичных кодов зашифровано слово «info» 105 110 102 111. Записать последовательность десятичных кодов для этого же слова, но записанного заглавными буквами.

10. Буква Z  имеет десятичный код 90, а z – 122. Записать слово «forma» в десятичном коде.

11. С помощью десятичных кодов зашифровано слово «port» 112 111 114 116. Записать последовательность десятичных кодов для этого же слова, но записанного заглавными буквами. Ответ: 80 79 82 84

Лабораторная работа №5. Кодирование звуковой информации.

Цель работы: научиться вычислять информационный объем звуковых файлов, заданных различными характеристиками; вычислять время звучания звукового файла по его размеру; научиться работать с программой «Звукозапись» ОС Windows.

Методические указания.

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

    Именно звуковая плата (карта) преобразует аналоговый сигнал в дискретную фонограмму и наоборот, «оцифрованный» звук – в аналоговый (непрерывный) сигнал, который поступает на вход динамика.

     При двоичном кодировании аналогового звукового сигнала непрерывный сигнал дискретизируется, т.е. заменяется серией его отдельных выборок - отсчётов. Качество двоичного кодирования зависит от двух параметров: количества дискретных уровней сигнала и количества выборок в секунду. Количество выборок или частота дискретизации в аудиоадаптерах бывает различной: 11 кГц, 22 кГц, 44,1 кГц и др. Если количество уровней равно 65536, то на один звуковой сигнал рассчитано 16 бит (216). 16-разрядный аудиоадаптер точнее кодирует и воспроизводит звук, чем 8-разрядный.

    Количество бит, необходимое для кодирования одного уровня звука, называется глубиной звука. Объём моноаудиофайла (в байтах) определяется по формуле:

    При стереофоническом звучании объём аудиофайла удваивается, при квадрофоническом звучании – учетверяется.

     По мере усложнения программ и увеличения их функций, а также появления мультимедиа-приложений, растёт функциональный объём программ и данных. Если в середине 80-х годов обычный объём программ и данных составлял десятки и лишь иногда сотни килобайт, то в середине 90-х годов он стал составлять десятки мегабайт. Соответственно растёт объём оперативной памяти.

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

а) 44.1 кГц;

б) 11 кГц;

в) 22 кГц;

г) 32 кГц

и разрядностью 16 бит.

Решение.

а) Если записывают моносигнал с частотой 44.1 кГц, разрядностью 16 бит (2 байта), то каждую минуту аналого-цифровой преобразователь будет выдавать 441000 * 2 * 60 = 529 000 байт (около 5 Мб) данных об амплитуде аналогового сигнала, который в компьютере записываются на жесткий диск.

Если записывают стереосигнал, то 1 058 000 байт (около 10 Мб).

Задания.

1. Какой объем памяти требуется для хранения цифрового аудиофайла с записью звука высокого качества при условии, что время звучания составляет 3 минуты?

2.     Какой объем данных имеет моноаудиофайл, длительность звучания которого 1 секунда, при среднем качестве звука (16 бит, 24 кГц)?

3.     Рассчитайте объем стереоаудиофайла длительностью 20 секунд при 20-битном кодировании и частоте дискредитации 44.1 кГц. Варианты: 44,1 Mb, 4.21 Mb, 3,53 Mb.

4. Оцените информационный объем моноаудиофайла длительностью звучания 20 с, если "глубина" кодирования и частота дискретизации звукового сигнала равны соответственно 8 бит и 8 кГц;

5.  Рассчитайте время звучания моноаудиофайла, если при 16-битном кодировании и частоте дискретизации 32 кГц его объем равен 700 Кбайт;

6. Запишите звуковой моноаудиофайл длительностью 20 с, с "глубиной" кодирования 8 бит и частотой дискретизации 8 кГц.

7. Определите качество звука (качество радиотрансляции, среднее качество, качество аудио-CD) если известно, что объем стериоаудиофайла длительностью звучания в 10 сек. Равен 940 Кбайт;

8. Оцените информационный объем стериоаудиофайла длительностью звучания 30 с, если "глубина" кодирования и частота дискретизации звукового сигнала равны соответственно 8 бит и 8 кГц;

9. Запишите звуковой файл длительностью 30с с "глубиной" кодирования 8бит и частотой дискретизации 8 кГц. Вычислите его объем и сверьтесь с полученным на практике значением.

10. Аналоговый звуковой сигнал был дискретизирован сначала с использованием 256 уровней интенсивности сигнала (качество звучания радиотрансляции), а затем с использованием 65536 уровней интенсивности сигнала (качество звучания аудио-CD). Во сколько раз различаются информационные объемы оцифрованного звука?

11. Оцените информационный объем моноаудиофайла длительностью звучания 1 мин. если "глубина" кодирования и частота дискретизации звукового сигнала равны соответственно:

16 бит и 48 кГц.

12. Запишите звуковой моноаудиофайл длительностью 1 минута с "глубиной" кодирования 16 бит и частотой дискретизации 48 кГц.

13. Подсчитать объем файла с 10 минутной речью записанного с частотой дискретизации 11025 Гц при 4 разрядном кодировании

14. Подсчитать время звучания звукового файла объемом 3.5 Мбайт содержащего стерео запись с частотой дискретизации 44100 Гц, 16-ти разрядном кодировании.

15. Определите количество уровней звукового сигнала при использовании 8-битных звуковых карт. Варианты: 256, 512,1024, 65 536.

16. Приведите пример:

а) аналогового способа представления звуковой информации;

б) дискретного способа представления звуковой информации.

17. Подготовить презентацию, демонстрирующую возможности звуковых форматов midi, wav, mp3, mod.

18. Перечислите параметры, от которых зависит качество двоичного кодирования звука.

Лабораторная работа №6. Кодирование графической информации.

Цель: научиться кодировать растровые графические файлы; научиться измерять информационный объем графических файлов.

Методические указания.

Графическая информация на экране дисплея представляется в виде изображения, которое формируется из точек (пикселей). Всмотритесь в газетную фотографию, и вы увидите, что она тоже состоит из мельчайших точек. Если это только чёрные и белые точки, то каждую из них можно закодировать 1 битом. Но если на фотографии оттенки, то два бита позволяет закодировать 4 оттенка точек: 00 - белый цвет, 01 - светло-серый, 10 - тёмно-серый, 11 - чёрный. Три бита позволяют закодировать 8 оттенков и т.д.

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

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

    Цветные изображения могут иметь различные режимы: 16 цветов, 256 цветов, 65536 цветов (high color), 16777216 цветов (true color). На одну точку для режима high color необходимо 16 бит или 2 байта.

    Наиболее распространённой разрешающей способностью экрана является разрешение 800 на 600 точек, т.е. 480000 точек. Рассчитаем необходимый для режима high color объём видеопамяти: 2 байт *480000=960000 байт.

    Для измерения объёма информации используются и более крупные единицы:

Следовательно, 960000 байт приблизительно равно 937,5 Кбайт. Если человек говорит по восемь часов в день без перерыва, то за 70 лет жизни он наговорит около 10 гигабайт информации (это 5 миллионов страниц - стопка бумаги высотой 500 метров).

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

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

Задачи:

1. Известно, что видеопамять компьютера имеет объем 512 Кбайт. Разрешающая способность экрана 640 на 200. Сколько страниц экрана одновременно разместится в видеопамяти при палитре: а) из 8 цветов,  б) 16 цветов; в) 256 цветов?
2.  Сколько бит требуется, чтобы закодировать информацию о 130 оттенках?
3. Подумайте, как уплотнить информацию о рисунке при его записи в файл, если известно, что: а) в рисунке одновременно содержится только 16 цветовых оттенков из 138 возможных; б) в рисунке присутствуют все 130 оттенков одновременно, но количество точек, закрашенных разными оттенками, сильно различаются.
4. Найдите в сети Интернет информацию на тему «Цветовые модели HSB, RGB, CMYK» и создайте на эту тему презентацию. В ней отобразите положительные и отрицательные стороны каждой цветовой модели, принцип ее функционирования и применение.
5. В приложении «Точечный рисунок» создайте файл размером (по вариантам):

А) 200*300, (№ по списку 1, 8, 15, 22, 29)

Б) 590*350, (№ по списку 2, 9, 16, 23, 30)

В) 478*472, (№ по списку 3, 10, 17, 24, 31)

Г)190*367, (№ по списку 4, 11, 18, 25, 32)

Д) 288*577; (№ по списку 5, 12, 19, 26, 33)

Е) 100*466, (№ по списку 5, 13, 20, 27, 34)

Ж) 390*277. (№ по списку  6, 14, 21, 28)

Сохраните его под следующими расширениями:

- монохромный рисунок,

- 16-цветный рисунок,

- 256-цветный рисунок,

- 24-битный рисунок,

- формат JPG.

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

6. На бумаге в клетку (или в приложении Excel) нарисуйте произвольный рисунок 10*10 клеток. Закодируйте его двоичным кодом (закрашена клетка – 1, не закрашена - 0). Полученный код отдайте одногруппнику для раскодирования и получения изображения.

Лабораторная работа №7. Сжатие текстовой информации. Алгоритм Хаффмана.

Цель работы: научиться сжимать информацию с помощью метода Хаффмана и метода RLE.

Методические указания:

Код Хаффмана

Определение 1: Пусть A={a1,a2,...,an} - алфавит из n различных символов, W={w1,w2,...,wn} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c1,c2,...,cn}, такой что:

называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.

Замечания: 

1. Свойство (1) называется свойством префиксности. Оно позволяет однозначно декодировать коды переменной длины.
2. Сумму в свойстве (2) можно трактовать как размер закодированных данных в битах. На практике это очень удобно, т.к. позволяет оценить степень сжатия не прибегая непосредственно к кодированию.
3. В дальнейшем, чтобы избежать недоразумений, под кодом будем понимать битовую строку определенной длины, а под минимально-избыточным кодом или кодом Хаффмана - множество кодов (битовых строк), соответствующих определенным символам и обладающих определенными свойствами.

Известно, что любому бинарному префиксному коду соответствует определенное бинарное дерево.

Определение 2: Бинарное дерево, соответствующее коду Хаффмана, будем называть деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Приведем общую схему построения дерева Хаффмана:

1. Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).
2. Из списка выберем 2 узла с наименьшим весом.
3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.
4. Добавим сформированный узел к списку.
5. Если в списке больше одного узла, то повторить 2-5.

Приведем пример: построим дерево Хаффмана для сообщения S="A H F B H C E H E H C E A H D C E E H H H C H H H D E G H G G E H C H H".

Для начала введем несколько обозначений:

1. Символы кодируемого алфавита будем выделять жирным шрифтом: A, B, C.
2. Веса узлов будем обозначать нижними индексами: A5, B3, C7.
3. Составные узлы будем заключать в скобки: ((A5+B3)8+C7)15.

Итак, в нашем случае A={A, B, C, D, E, F, G, H}, W={2, 1, 5, 2, 7, 1, 3, 15}.

1. A2 B1 C5 D2 E7 F1 G3 H15 
2. A2 C5 D2 E7 G3 H15 (F1+B1)2 
3. C5 E7 G3 H15 (F1+B1)2 (A2+D2)4 
4. C5 E7 H15 (A2+D2)4 ((F1+B1)2+G3)5 
5. E7 H15 ((F1+B1)2+G3)5 (C5+(A2+D2)4)9 
6. H15 (C5+(A2+D2)4)9 (((F1+B1)2+G3) 5+E7)12 
7. H15 ((C5+(A2+D2)4) 9+(((F1+B1)2+G3) 5+E7)12)21 
8. (((C5+(A2+D2)4) 9+(((F1+B1)2+G3) 5+E7)12)21+H15)36 

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

ROOT

/\

0  1

/    \

/\     H

/  \

/    \

/      \

0        1

/          \

/            \

/              \

/                \

/\                /\

0  1              0  1

/    \            /    \

C     /\          /\     E

0  1        0  1

/    \      /    \

A      D    /\     G

0  1

/    \

F      B

Листовые узлы дерева Хаффмана соответствуют символам кодируемого алфавита. Глубина листовых узлов равна длине кода соответствующих символов.

Путь от корня дерева к листовому узлу можно представить в виде битовой строки, в которой "0" соответствует выбору левого поддерева, а "1" - правого. Используя этот механизм, мы без труда можем присвоить коды всем символам кодируемого алфавита. Выпишем, к примеру, коды для всех символов в нашем примере:

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

S/="0010 1 01000 01001 1 000 011 1 011 1 000 011 0010 1 0011 000 011 011 1 1 1 000 1 1 1 0011 011 0101 1 0101 0101 011 1 000 1 1".

Оценим теперь степень сжатия. В исходном сообщении S было 36 символов, на каждый из которых отводилось по [log2|A|]=3 бита (здесь и далее будем понимать квадратные скобки [] как целую часть, округленную в положительную сторону, т.е. [3,018]=4). Таким образом, размер S равен 36*3=108 бит

Размер закодированного сообщения S/ можно получить воспользовавшись замечанием 2 к определению 1, или непосредственно, подсчитав количество бит в S/. И в том и другом случае мы получим 89 бит.

Итак, нам удалось сжать 108 в 89 бит.

Теперь декодируем сообщение S/. Начиная с корня дерева будем двигаться вниз, выбирая левое поддерево, если очередной бит в потоке равен "0", и правое - если "1". Дойдя до листового узла мы декодируем соответствующий ему символ.

Ясно, что следуя этому алгоритму мы в точности получим исходное сообщение S.

Метод RLE.

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.

1. Сжатие методом Хаффмана

«Какая зима золотая!
Как будто из детских времен...
Не надо ни солнца, ни мая –
пусть длится торжествениый сон.

Пусть я в этом сне позабуду
когда-то манивший огонь,
И лето предам, как Иуда,
за тридцать снежинок в ладонь.

Затем, что и я холодею,
тепло уже страшно принять:
я слишком давно не умею
ни тлеть, ни гореть, ни сжигать…

Все чаще, все дольше немею:
К зиме уже дело, к зиме...
И только того отогрею,
кому холоднее, чем мне»

2. С помощью сжатия по методу RLE.

1 последовательность:

ssssoooeeerroooaayyyyyddddoeuuuuuwwwwjjjorruuuuuuuuuuxxxkhhhhhhmmmmmmgggllllllljjjj

2 последовательность:

FFFFFFFFKKKKKSSSSUURERRRRRRRRRPPPPPPPPDDDDKKKKKKGLDDDDDDDDKKKKKKKKGGGGMGMMMM

3. Создайте презентацию по теме «Алгоритмы сжатия изображений». Используйте ресурсы Интернет.

Лабораторная работа №8. Приемы работы с информацией в сети Интернет. Поисковые алгоритмы.

Цель работы: научиться работать с большими массивами информации в сети Интернет, быстро находить нужную информацию.

Методические указания:

В Интернете с каждым днём скапливается всё больше информации когда-либо созданной и вновь создаваемой людьми. Равнодоступность большей части информации в Интернете уравнивает возможности доступа к этой информации как обычных пользователей Интернета и журналистов локальных СМИ, так и сотрудников мировых информационных агентств. Следовательно, уровень монополизации информационных источников снижается по мере роста и распространения Интернета.

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

До недавнего времени ограничения в прямой коммуникации между людьми, порождаемые пространством и временем, во многом определяли потребность людей в услугах журналистов. По мере роста общего количества пользователей Интернета, а среди них - числа владеющих английским языком, эти ограничения всё в большей степени снимаются, что закономерно ведёт к уменьшению спроса на услуги журналистов. Одновременно с этим растёт объем "сырой" информации, доступной каждому отдельному пользователю Интернета, что актуализирует проблему её отбора и редактирования. Последнее всегда входило в перечень функций журналистики, но с ростом числа пользователей Интернета начинает приобретать всё большую значимость в журналистской деятельности. Журналисты всё больше становятся похожими на "поисковые машины", отбирающие, редактирующие и предлагающие полученный при этом информационный продукт своим читателям.

Для того, чтобы найти в Интернете требуемую информацию, необходимо знать либо адрес её местоположения (например, адрес html-страницы или файла), либо пользователя Интернета, который может предоставить информацию. Если мы не знаем ни адреса, ни человека, который мог бы нам помочь, то следует перейти к вопросам "Как можно узнать адрес размещения информации?" или "Как найти человека, который мог бы нам помочь с поиском информации?". При этом не следует переоценивать возможности Интернета. Лучшие результаты может дать совмещение онлайновых и офлайновых методов поиска информации.

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

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

Таким образом, планирование поиска сводится к трём вопросам: "Что ищем?", "Где ищем?", "Как ищем?".

Что ищем?

Поисковые запросы бывают явные и неявные. В явных вопросах конкретно указывается объект поиска. В неявных вопросах, например, «какая сегодня погода», «происходит ли сейчас что-то важное», «можно ли проехать по городу», или у А. С. Пушкина в «Сказке о мертвой царевне и о семи богатырях»:
Свет мои, зеркальце! Скажи

Да всю правду доложи:

Я ль на свете всех милее,

Всех румяней и белее?

объект поиска конкретно не указывается.

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

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

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

Надо определиться и с возможными форматами файлов в которых может содержаться требуемая информация. Это может быть html-страница, текстовый документ в форматах txt, rtf, odt, doc или docx, документ pdf, презентация в форматах odp, ppt или pptx, электронная таблица в форматах ods, xls или xlsx, аудио в формате mp3, flash-ролик формата swf, видео в формате avi и т. д.

• Типы информации;
• Оценка информации;
• Поиск файлов;
• Поиск файлов с расширением rtf;
• Поиск файлов с расширением doc;
• Поиск файлов с расширением ppt;
• Поиск файлов с расширением xls;
• Поиск файлов с расширением pdf;
• Поиск файлов с расширением mp3;
• Поиск файлов с расширением mpeg4;
• Поиск файлов с расширением swf;
• Поиск файлов с расширением ps;
• Поиск файлов с расширением dwf;
• Поиск файлов с расширением kml;
• Поиск файлов с расширением kmz;
• Поиск файлов с расширением avi;
• Поиск программного обеспечения;
• Поиск законодательного акта;
• Поиск вакансий;
• Поиск работников;
• Поиск реферата;
• Поиск человека.

Где ищем?

Информация может размещаться на веб-серверах, на ftp-серверах, в блогах, в новостях, в книгах, в словарях, в товарах, на географических картах, в справочниках адресов организаций, среди афиш театров и музеев, в телепрограммах, в каталогах, в Википедии, в архивах Интернета, в пиринговых сетях, в базах данных, в веб-закладках или в рейтинговых системах. Поэтому лучше заранее определиться где мы начнём свой поиск.

• Источники информации;
• Поиск по блогам;
• Поиск в новостях;
• Новости Google;
• Яндекс.Новости;
• Поиск книг и в книгах;
• Поиск в словарях;
• Поиск в картинках;
• Поиск в товарах;
• Поиск по карте;
• Поиск адресов;
• Поиск афиши;
• Поиск по объявлениям;
• Поиск информации о погоде;
• Поиск телепрограммы;
• Поиск в каталогах;
• Поиск в Википедии;
• Поиск в архивах Интернета;
• Поиск через пиринговые системы;
• Поиск в базах данных;
• Поиск в интернет-версиях правовых систем;
• Сервис закладок;
• Поиск через рейтинговые системы.

Как ищем?

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

• Карты поиска информации;
• Поисковые индексы;
• Язык запросов в поисковых индексах;
• Собственная публикация как источник информации;
• Поиск через экспертов;
• Поиск на сайтах правовых систем;
• Поисковые системы;
• Google;
• Yahoo!;
• Апорт;
• Rambler;
• Яндекс;
• Microsoft Live Search

Задания:

1. Найдите в сети Интернет информацию об алгоритме поиска в поисковых системах Яндекс, Рамблер и Google. Создайте таблицу, отражающую плюсы и минусы каждого из них.
2. Наберите в строке запроса Орский индустриальный колледж в Яндексе, Рамблере, Google. На каких местах в первой десятке страниц будет страница ОИК?
3. Наберите в строке запроса Орск в Яндексе, Рамблере, Google. С помощью какого поисковика можно быстрее всего найти карту Орска?
4. Наберите в строке запроса Орский индустриальный колледж в Яндексе, Рамблере, Google. В каком поисковике сколько картинок, связанных с колледжем, будет отображаться?
5. Опишите правила формирования запросов в Яндексе.
6. Создайте презентацию о Рунете.

Лабораторная работа №9. Представление числовой информации в ЭВМ.

Цель работы: познакомиться с алгоритмами представления десятичных целых, отрицательных и вещественных чисел в памяти ЭВМ.

Методические указания.

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

Для представления чисел в памяти ПК используются два формата:

-формат с фиксированной точкой (запятой) целые числа;

-формат с плавающей точкой (запятой) вещественные числа.

Представление целых чисел

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

Для целых чисел существуют два представления:

-беззнаковое;

-со знаком.

В К-разрядной ячейке может храниться 2к различных значений целых чисел.

Диапазон значений целых беззнаковых чисел (только положительные):

от 0 до 2к - 1

для 16-разрядной ячейки от 0 до 65535

для 8-разрядной ячейки от 0 до 255

Диапазон значений целых чисел со знаком (и отрицательные, и положительные в равном количестве):

от -2к-1 до 2к-1-1

для 16-разрядной ячейки от -32768 до 32767

для 8-разрядной ячейки от -128 до 127

Чтобы получить внутреннее представление целого положительного числа N, хранящегося в К-разрядной ячейке, необходимо:

1. перевести число N в двоичную систему счисления;

2. полученный результат дополнить слева незначащими нулями до К разрядов.

Пример:

Получить внутреннее представление целого числа 1607 в 2-х байтовой ячейке.

Решение:

N=1607=110010001112.

Внутреннее представление этого числа будет: 0000 0110 0100 0111. Шестнадцатеричная форма внутреннего представления числа: 0647.

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

Дополнительным кодом двоичного числа X в N-разрядной ячейке является число, дополняющее его до значения 2N.

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

1. получить внутреннее представление положительного числа N (прямой код);

2. получить обратный код этого числа заменой 0 на 1 или 1 на 0 (обратный код);

3. к полученному числу прибавить 1.

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

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

A-B=A+(-B).

Процессору достаточно уметь лишь складывать числа.

Старший, К-й разряд во внутреннем представлении любого положительного числа равен 0, отрицательного числа равен 1. Поэтому этот разряд называется знаковым разрядом 

Пример:

Получить внутреннее представление целого отрицательного числа - 1607.

Решение:

1. Внутреннее представление положительного числа: 000 0110 0100 0111;

2. Обратный код: 1111 1001 1011 1000;

3. Дополнительный код: 1111 1001 1011 1001 - внутреннее двоичное представление числа.

16-ричная форма: F9B9.

Представление вещественных чисел

Вещественные числа представляются в ПК в форме с плавающей точкой.

Этот формат использует представление вещественного числа R в виде произведения мантиссы m на основание системы счисления p в некоторой целой степени n которую называют порядком:

R=m*pn

Представление числа в форме с плавающей точкой неоднозначно.

Например: 25.324=25324*101=0.0025324*104=2532.4*10-2

В ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса в нормализованном представлении должна удовлетворять условию: 0.1p m<1p

Иначе говоря, мантисса меньше 1 и первая значащая цифра - не 0.

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

Например: 4-x байтовая ячейка памяти. В ячейке должна содержаться следующая информация о числе:

- знак числа;

- порядок;

- значащие цифры мантиссы.

В старшем бите 1-го байта хранятся знак числа: 0 обозначает плюс, 1 - минус.

Оставшиеся 7 бит 1-го байта содержат машинный порядок. В следующих трех байтах хранятся значащие цифры мантиссы (24 разряда).

В семи двоичных разрядах помещаются двоичные числа в диапазоне от 0000000 до 1111111. Значит, машинный порядок изменяется в диапазоне от 0 до 127 (в десятичной системе счисления). Всего 128 значений. Порядок, очевидно, может быть как положительным так и отрицательным. Разумно эти 128 значений разделить поровну между положительным и отрицательным значениями порядка: от -64 до 63.

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

Связь между машинным порядком (Мр) и математическим (р) в рассматриваемом случае выражается формулой:

Мр = р + 64

Полученная формула записана в десятичной системе. В двоичной системе формула имеет вид: Mp2=p2+10000002 

Для записи внутреннего представления вещественного числа необходимо:

1) перевести модуль данного числа в двоичную систему счисления с 24 значащими цифрами;

2) нормализовать двоичное число;

3) найти машинный порядок в двоичной системе счисления;

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

Пример

Записать внутреннее представление числа 250,1875 в форме с плавающей точкой.

Решение:

1) Приведем его в двоичную систему счисления с 24 значащими цифрами: 250.187510=11111010, 0011000000000000002.

2) Запишем в форме нормализованного двоичного числа с плавающей точкой: 0,111110100011000000000000*1021000. Здесь мантисса, основание системы счисления (210=102) и порядок (810=10002) записаны в двоичной системе.

3) Вычислим машинный порядок в двоичной системе счисления: Mp2= 1000 + 100 0000 =100 1000.

4) Запишем представление числа в 4-х байтовой ячейке памяти с учетом знака числа:

Шестнадцатеричная форма: 48FA3000.

Пример.

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

Решение: 1) Перейдем к двоичному представлению числа в 4-х байтовой ячейке, заменив каждую шестнадцатеричную цифру 4-мя двоичными цифрами:

1100 1001 1000 0001 0001 0000 0000 0000

2) Заметим, что получен код отрицательного числа, поскольку в старшем разряде с номером 31 записана 1. Получим порядок числа: р=10010012 -10000002=10012=910.

3) Запишем в форме нормализованного двоичного числа с плавающей точкой с учетом знака числа:

-0,100000010001000000000000 *21001

4) Число в двоичной системе счисления имеет вид: -100000010.0012.

5) Переведем число в десятичную систему счисления:

-100000010.0012= -(1*28+1*21+1*2-3)= -258.12510

Задание для решений №1

1) Получить двоичную форму внутреннего представления целого числа в 2-х байтовой ячейке.

2) Получить шестнадцатеричную форму внутреннего представления целого числа 2-х байтовой ячейке.

3) По шестнадцатеричной форме внутреннего представления целого числа в 2-х байтовой ячейке восстановить само число.

Задание для решений №2

1) Получить шестнадцатеричную форму внутреннего представления числа в формате с плавающей точкой в 4-х байтовой ячейке.

2) По шестнадцатеричной форме внутреннего представления вещественного числа в 4-х байтовой ячейке восстановить само число.