Лабораторная работа №1
По информатике
Информация и информационные процессы
Решая различные задачи, человек вынужден использовать информацию об окружающем нас мире. И чем более полно и подробно человеком изучены те или иные явления, тем подчас проще найти ответ на поставленный вопрос. Так, например, знание законов физики позволяет создавать сложные приборы, а для того, чтобы перевести текст на иностранный язык, нужно знать грамматические правила и помнить много слов.
Часто приходится слышать, что сообщение или несет мало информации или, наоборот, содержит исчерпывающую информацию. При этом разные люди, получившие одно и то же сообщение (например, прочитав статью в газете), по-разному оценивают количество информации, содержащейся в нем. Это происходит оттого, что знания людей об этих событиях (явлениях) до получения сообщения были различными. Поэтому те, кто знал об этом мало, сочтут, что получили много информации, те же, кто знал больше, чем написано в статье, скажут, что информации не получили вовсе. Количество информации в сообщении, таким образом, зависит от того, насколько ново это сообщение для получателя.
Однако иногда возникает ситуация, когда людям сообщают много новых для них сведений, а информации при этом они практически не получают (в этом нетрудно убедиться во время опроса или контрольной работы). Происходит это оттого, что сама тема в данный момент слушателям не представляется интересной. Смысловая составляющая информации во многом индивидуальна. Большинство россиян не способны извлечь никакой информации из текста на японском языке. Многие взрослые, взяв учебник для начальных классов, также не сочтут его заслуживающей своего внимания информацией, хотя, в отличие от предыдущего случая, понимают что там написано. Химика редко интересуют сообщения об археологических открытиях, а большая часть литераторов активно игнорирует любые сведения из области математики. Наконец, многие образованные люди не верят в статьи, опубликованные в бульварной прессе, заранее считая их недостоверными. Таким образом, информативность любых сведений и сообщений существенно зависит от воспринимающего их человека, его предыдущих знаний, опыта, интересов, отношения к источнику информации и множества других факторов личного характера, т.е. по своей сути является субъективной.
Как же все-таки измерить информацию? Общепринятым на данный момент решением проблемы является измерение объема информации при полном игнорировании ее смысла. Такой подход, несмотря на кажущуюся бессмысленность, оказывается необычайно полезным и широко применяется на практике.
Если подбросить монету и проследить, какой стороной она упадет, то мы получим определенную информацию. Обе стороны монеты “равноправны”, поэтому одинаково вероятно, что выпадет как одна, так и другая сторона. В таких случаях говорят, что событие несет информацию в 1 бит. Если положить в мешок два шарика разного цвета, то, вытащив вслепую один шар, мы также получим информацию о цвете шара в 1 бит. В качестве единицы информации принять один бит (англ. bit — binary digit — двоичная цифра) предложил американский учёный Клод Шеннон. Бит в теории информации — количество информации, необходимое для различения двух равновероятных сообщений.
В компьютерной технике бит соответствует физическому состоянию носителя информации: намагничено – не намагничено, есть отверстие – нет отверстия. При этом одно состояние принято обозначать цифрой 0, а другое – цифрой 1.
В информатике часто используется величина, называемая байтом (byte) и равная 8 битам. И если бит позволяет выбрать один вариант из двух возможных, то байт, соответственно, 1 из 256 (28).
Наряду с байтами для измерения количества информации используются более крупные единицы:
1 Килобайт (Кб) = 210 байт = 1024 байта;
1 Мегабайт (Мб) = 210 Кбайт = 1024 Кбайта;
1 Гигабайт (Гб) = 210 Мбайт = 1024 Мбайта.
1 Терабайт (Тб) = 210 Гбайт = 1024 Гбайта,
1 Петабайт (Пб) = 210 Тбайт = 1024 Тбайта.
Определить понятие «количество информации» довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно.
Содержательный подход к измерению информации
Другое название содержательного подхода – вероятностный. Вероятность – степень возможности появления какого-либо определенного события в тех или иных условиях. Два события называются равновероятными (или равновозможными), если нет никаких объективных причин считать, что одно из них может наступить чаще, чем другое.
Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.
Рассмотрим в качестве примера опыт, связанный с бросанием правильной игральной кости, имеющей N граней. Результаты данного опыта могут быть следующие: выпадение грани с одним из следующих знаков: 1, 2, . . . N.
Введем в рассмотрение численную величину, измеряющую неопределенность — энтропию (обозначим ее H). Согласно развитой теории, в случае равновероятного выпадания каждой из граней величины N и H связаны между собой формулой Хартли
H = log2 N.
Важным при введении какой-либо величины является вопрос о том, что принимать за единицу ее измерения. Очевидно, H будет равно единице при N = 2. Иначе говоря, в качестве единицы принимается количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов (примером такого опыта может служить бросание монеты при котором возможны два исхода: «орел», «решка»). Такая единица количества информации и является «битом».
Приведем примеры равновероятных сообщений: при бросании монеты: “выпала решка”, “выпал орел”; на странице книги: “количество букв чётное”, “количество букв нечётное”.
Определим теперь, являются ли равновероятными сообщения “первой выйдет из дверей здания женщина” и “первым выйдет из дверей здания мужчина”. Однозначно ответить на этот вопрос нельзя. Все зависит от того, о каком именно здании идет речь. Если это, например, станция метро, то вероятность выйти из дверей первым одинакова для мужчины и женщины, а если это военная казарма, то для мужчины эта вероятность значительно выше, чем для женщины.
Для задач такого рода американский учёный Клод Шеннон предложил в 1948 г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе.
Формула Шеннона:
I = — ( p1log2 p1 + p2 log2 p2 + . . . + pN log2 pN),
где pi — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.
Вероятность события А определяется формулой:
P(A) = m/n,
где m – число элементарных исходов, благоприятствующих А;
n – число всех возможных элементарных исходов испытания.
Легко заметить, что если вероятности p1, …, pN равны, то каждая из них равна 1 / N, и формула Шеннона превращается в формулу Хартли.
Рассмотрим следующий пример. Пусть при бросании несимметричной четырехгранной пирамидки вероятности выпадения граней будут следующими: p1=1/2, p2=1/4, p3=1/8, p4=1/8, тогда количество информации, получаемое после броска, можно рассчитать по формуле:
Для симметричной четырехгранной пирамидки количество информации будет: H=log24=2(бит).
Заметим, что для симметричной пирамидки количество информации оказалось больше, чем для несимметричной пирамидки. Максимальное значение количества информации достигается для равновероятных событий.
Примеры Вероятностный подход
1.Какое количество информации несет в себе сообщение о том, что нужная вам программа находится на одной из восьми дискет?
Дано: N=8 – количество дискет (число событий)
Решение:
N = 2I
8 = 2I
Ответ: 3 бита
2.Какое количество информации получит второй игрок при игре в крестики-нолики на поле 8х8 после первого хода первого игрока, играющего крестиками?
Дано:
N=64 – количество полей
Решение:
N = 2I
64 = 2I
Ответ: 6 бит
3.Сообщение о том, что ваш друг живет на десятом этаже несет в себе 4 бита информации. Сколько этажей в доме?
Дано:
i=4 бита
Решение:
N = 2I
N = 24
Ответ: 16
4.В коробке 5 синих и 15 красных шариков. Какое количество информации несет сообщение, что из коробки достали синий шарик?
Дано:
N1=5, N2=15
Решение:
N=N1+N2
N=15+5=20 всего шариков
K=5 – синих (его достали)
N/K=20/5=4
2i=4
i=2 бита
Ответ: 2 бита.
5.Какое количество информации о цвете вынутого шарика будет получено, если в непрозрачном пакете хранятся: 10 белых, 20 красных, 30 синих и 40 зеленых шариков?
Дано:
K=10+20+30+40=100 – общее количество шариков
N1=10; N2=20; N3=30; N4=40;
Решение:
Pбел. = 10/100 = 0,1
Pкрасн. = 20/100 = 0,2
Pсин. = 30/100 = 0,3
Pзел. = 40/100 = 0,4
I = – (0,1•log20,1 + 0,2•log20,2 + 0,3•log20,3 + 0,4•log20,4) ? 1,85 бита
Ответ: 1,85 бита
6.Студенты группы изучают один из трех языков: английский, немецкий или французский. Причем 12 студентов не учат английский. Сообщение, что случайно выбранный студент Петров изучает английский, несет log23 бит информации, а что Иванов изучает французский – 1 бит. Сколько студентов изучают немецкий язык?
Дано:
Y – учат французский
X – учат английский, 12 не учат английский. Всего 12+X студентов
N=12+X
K1=X
i1=log23 бит
i2=1 бит
Решение:
(12+X)/X=2log23
12+X=3X
X=6
N=12+6=18
K2=Y
18/Y=21
Y=9
18-X-Y=18-6-9=3 студента изучают немецкий.
Ответ: 3
Алфавитный подход к измерению информации
Если информация представлена в виде дискретного сообщения, то логично считать количеством информации его длину, то есть общее число знаков в сообщении. Но длина сообщения зависит не только от содержащейся в нем информации. На нее влияет мощность алфавита используемого языка. Чем меньше знаков в используемом алфавите, тем длиннее сообщение. Так, например, в алфавите азбуки Морзе всего три знака (точка, тире, пауза), поэтому для кодирования каждой русской или латинской буквы нужно использовать несколько знаков, и текст, закодированный по Морзе, будет намного длиннее, чем при обычной записи.
Пример: Сигнал SOS: 3 знака в латинском алфавите;
11 знаков в алфавите Морзе: *** пауза – – – пауза ***.
Для упорядочивания измерений информационный объем сообщений принято измерять в битах. Один бит соответствует одному знаку двоичного алфавита. Итак, чтобы измерить длину сообщения, его нужно представить в двоичном виде и подсчитать количество двоичных знаков – битов. При этом совсем не обязательно уметь интерпретировать сообщения.
Пример. Пусть сообщение в двоичном алфавите выглядит следующим образом: 000100010001. Мы не знаем, какая информация была заложена в этом сообщении, но можем легко подсчитать его длину – 12 двоичных знаков, следовательно, его информационный объем равен 12-ти битам.
Такой способ измерения количества информации называется алфавитным подходом. При этом измеряется не содержание информации с точки зрения его новизны и полезности, а размер несущего информацию сообщения. При алфавитном подходе к определению количества информации одни и те же сведения, закодированные по-разному, будут иметь различный информационный объем. Сообщения одинаковой длины могут нести совершенно как совершенно бесполезные сведения, так и нужную информацию. Пример: Применяя алфавитный подход, получаем, что информационный объем слов “фыырпбьощ” и “компьютер” совершенно одинаков, а слов “ученик” и “учащийся” – различен.
Если алфавит содержит 2i знаков, то каждый из его знаков можно закодировать с помощью i знаков двоичного алфавита. Таким образом, объем информации I, содержащейся в сообщении длиной k при использовании алфавита мощностью 2i, равен
I=k*i бит.
Пример. Найдем информационный объем слова SOS, записанного в компьютерной кодировке. При кодировании букв в компьютере используется либо алфавит ASCII (American Standard Code for Information Interchange — американский стандартный код обмена информацией), состоящий из 28=256 знаков, либо алфавит Unicode, мощность которого 216 = 65536. В слове SOS три буквы, следовательно, его информационный объем 3*8=24 или 3*16=48 бит, в зависимости от используемой кодировки.
При алфавитном подходе к измерению информации количество информации зависит не от содержания, а от размера текста и мощности алфавита. При использовании двоичной системы (алфавит состоит из двух знаков: 0 и 1) каждый двоичный знак несет 1 бит информации. Сама единица измерения информации «бит» получила свое название от английского сочетания «binary digit» – «двоичная цифра».
Если допустить, что все символы алфавита встречаются в тексте с одинаковой частотой (равновероятно), то количество информации, которое несет каждый символ, вычисляется по формуле: i=log2N, где – N мощность алфавита.
Применение алфавитного подхода удобно прежде всего при использовании технических средств работы с информацией. В этом случае теряют смысл понятия «новые — старые», «понятные — непонятные» сведения. Алфавитный подход является объективным способом измерения информации в отличие от субъективного содержательного подхода.
Ограничения на максимальный размер алфавита теоретически не существует. Однако есть алфавит, который можно назвать достаточным. Это алфавит мощностью 256 символов. В алфавит такого размера можно поместить все практически необходимые символы: латинские и русские буквы, цифры, знаки арифметических операций, всевозможные скобки, знаки препинания….
Поскольку 256 = 28, то один символ этого алфавита «весит» 8 бит.
Компьютерные редакторы, в основном, работают с алфавитом размером 256 символов. В этом случае легко подсчитать объем информации в тексте. Если 1 символ алфавита несет 1 байт информации, то надо просто сосчитать количество символов; полученное число даст информационный объем текста в байтах.
Пусть небольшая книжка, сделанная с помощью компьютера, содержит 150 страниц; на каждой странице — 40 строк, в каждой строке — 60 символов. Значит, страница содержит 40×60=2400 байт информации. Объем всей информации в книге: 2400 х 150 = 360 000 байт.
информационный алфавитный компьютерный кодировка
Практические задания с решениями
1. Найти объем информации, содержащейся в тексте из 3000 символов, написанном русскими буквами.
Дано: K=3000
Решение:
Найдем мощность алфавита:
N = 33 русских прописных буквы + 33 русских строчных букв + 21 специальный знак = 87 символов. Подставим в формулу и рассчитаем количество информации:
I = log287 = 6,4 бита.
Такое количество информации – информационный объем – несет один символ в русском тексте. Теперь, чтобы найти количество информации во всем тесте, нужно найти общее количество символов в нем и умножить на информационный объем одного символа. Пусть в тексте 3000 символов.
Значит: 6,4*3000 =19140 бит.
Ответ: 19140 бит.
2.Для записи письма был использован алфавит мощностью в 16 символов. Письмо состояло из 25 строк. В каждой строке вместе с пробелами было 64 символа. Сколько байт информации содержало письмо?
Дано:
N=16 – мощность алфавита;
Решение:
Найдём количество информации содержащееся в одном символе:
i=log216=4 бит;
Найдём общее количество символов в письме, перемножив количество строк на количество символов в одной строке:
K=25*64=1600
Теперь можем найти сколько байт содержало письмо:
I=K*i=1600 * 4 бит = 6400 бит = 800 байт
Ответ: 800 байт
3. Черно-белое изображение имеет 8 градаций яркости. Размер изображения 10*15 см. Разрешение 300 точек на дюйм (1 дюйм = 2,5 см). Сколько Кбайт памяти требуется для хранения изображения в несжатом виде?
Решение:
N=8
i=log28=3 бит (на каждую точку)
Размер изображения = 10*15 см = 4*6 дюйм = 24 дюйм2
На дюйм – 300 точек, на дюйм2=3002точек=90000точек.
K=90000 точек*24 дюйм2=2160000 точек
I=K*i=2160000*3бит=6480000 бит = 810000 байт = 810 Кбайт
Ответ: 810
4. Цветное изображение имеет 256 цветов. Размер изображения 7,5*12,5 см. Для хранения изображения требуется 432*105 бит памяти. Каково разрешение изображения в точках на дюйм? (1дюйм=2,5см)
Дано:
N=256 – количество цветов
I=43200000 бит – информационный объём изображения
Решение:
i=log2256=8 бит
7,5см*12,5см = 3дюйм*5 дюйм=15 дюйм2
X – точек на дюйм
X2 – точек на дюйм2
K=X2*15
I=15X2*8 бит
43200000 бит=15X2*8 бит
X2=360000
X=600 точек на дюйм
Ответ: 600
5. Текст занимает 3 страницы по 25 строк. В каждой строке записано по 60 символов. Сколько символов в используемом алфавите, если все сообщение содержит 1125 байт?
Дано:
K1=3; k2=25; k3=60
I=1125 байт = 9000 бит
Решение:
K=3*25*60=4500
i=I/K
i=9000 бит/4500=2 бит
N=2i
N=22=4 символа в алфавите
Ответ: 4
6. Даны два текста, содержащих одинаковое количество символов. Первый текст состоит из алфавита мощностью 16 символов, а второй текст – из 256 символов. Во сколько раз информации во втором тексте больше, чем в первом?
Дано: N1=16; N2=256
Решение:
K1=K2
i1=log216=4
i2=log2256=8
I1=K1*i1
I2=K2*i2
Ответ: в 2 раза
Задания для самостоятельного решения
1. Информационное сообщение объемом 300 бит содержит 100 символов. Какова мощность алфавита?
2. В книге 100 страниц. На каждой странице 60 строк по 80 символов в строке. Вычислить информационный объем книги.
3. Имеется два текста на разных языках. Первый текст использует 32-символьный алфавит и содержит 200 символов, второй — 16-символьный алфавит и содержит 250 символов. Какой из текстов содержит большее количество информации и на сколько битов?
4. В библиотеке 16 стеллажей. На каждом стеллаже по 8 полок. Библиотекарь сказала Оле, что интересующая ее книга, находится на 3 стеллаже, на 2-ой сверху полке. Какое количество информации получила Оля?
5. Сколько символов в тексте, если мощность алфавита — 64 символа, а объем информации, содержащейся в нем, — 1,5 килобайта?
6. Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?
7. Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
8. В колоде содержится 32 карты. Из колоды случайным образом вытянули туза, потом его положили обратно и перетасовали колоду. После этого из колоды опять вытянули этого же туза. Какое количество бит информации в сумме содержат эти два сообщения?
9. Для записи сообщения использовался 64-х символьный алфавит. Каждая страница содержит 30 строк. Все сообщение содержит 8775 байт информации и занимает 6 страниц. Сколько символов в строке?
10. Пользователь компьютера, хорошо владеющий навыками ввода информации с клавиатуры, может вводить в минуту 100 знаков. Мощность алфавита, используемого в компьютере, равна 256. Какое количество информации в байтах может ввести пользователь за 1 минуту
11. Скорость чтения ученика 10 класса составляет приблизительно 250 символов в минуту. Приняв мощность используемого алфавита за 64, определите, какой объем информации в килобайтах получит ученик, если он будет непрерывно читать в течение 40 минут.
12. Для ремонта школы использовали белую, синюю и коричневую краски. Израсходовали одинаковое количество банок белой и синей краски. Сообщение о том, что закончилась банка белой краски, несёт 2 бита информации. Синей краски израсходовали 8 банок. Сколько банок коричневой краски израсходовали на ремонт школы? (на вероятность) 13.В корзине лежат белые и чёрные шары. Среди них 18 чёрных шаров. Сообщение о том, что из корзины достали белый шар, несёт 2 бита информации. Сколько всего в корзине шаров? (на вероятность)
14. За четверть ученик получил 100 оценок. Сообщение о том, что он получил четвёрку, несёт 2 бита информации. Сколько четвёрок ученик получил за четверть?
15. Два сообщения содержат одинаковое количество информации. Количество символов в первом тексте в 2.5 раза меньше, чем во втором. Сколько символов содержат алфавиты, с помощью которых записаны сообщения, если известно, что размер каждого алфавита не превышает 32 символов и на каждый символ приходится целое число битов?
16. Какое количество информации несёт сообщение: «Встреча назначена на сентябрь».
17. Какое количество информации несёт сообщение о том, что встреча назначена на 15 число.
18. Какое количество информации несёт сообщение о том, что встреча назначена на 23 октября в 15.00.
19. Выяснить сколько бит информации несёт каждое двухзначное число (отвлекаясь от его конкретного числового значения).
20. ДНК человека (генетический код) можно представить как некоторое число в четырёхбуквенном алфавите, где каждой буквой помечается звено цепи ДНК, или нуклеотид. Сколько информации (в битах) содержит ДНК человека, содержащий примерно 1,5 х 1023 нуклеотидов.
21. Сколько информации содержит красный сигнал светофора?
22. Сколько граней имеет многогранник, если при его бросании получают 4 бита информации?
23. Во время игры в кости на игральном кубике выпало число 1. Сколько информации содержит это сообщение? 24. Проводятся две лотереи: “4 из 32” и “5 из 64”. В каждой из них достали по одному шару. Сообщение о результате какой лотереи несет больше информации? 25. При угадывании целого числа в некотором диапазоне было получено 4 бита информации. Сколько чисел содержит этот диапазон?
26. Сообщение занимает 2 страницы и содержит 1/8 Кбайта информации. На каждой странице записано 256 символов. Какое количество информации несет одна буква использованного алфавита?
27. Какое количество информации получит второй игрок после первого хода первого игрока в игре “крестики-нолики” на поле 4х4?
28. Цветное (с палитрой из 256 цветов) растровое графическое изображение имеет размер 12х12 точек. Какой объем памяти займет это изображение?
29. Сообщение о том, что ваш друг живет на 6 этаже, несет 4 бита информации. Сколько этажей в доме?
30. Сообщение занимает 3 страницы по 25 строк. В каждой строке записано по 60 символов. Сколько символов в использованном алфавите, если все сообщение содержит 1125 байтов?
31. Для записи сообщения использовался 64-х символьный алфавит. Каждая страница содержит 30 строк. Все сообщение содержит 8775 байтов информации и занимает 6 страниц. Сколько символов в строке?
32. Сообщение занимает 2 страницы и содержит 1/16Кбайта информации. На каждой странице записано 256 символов. Какое количество информации несет одна буква использованного алфавита?
33. Скорость передачи файла равна 256000 бит/с. Передача файла заняла 2 минуты. Определите размер файла в килобайтах.
34. В княжестве Блэквайтия имеются автомобили только белого, серого и черного цветов. Причем из них 36 автомобилей не черного цвета. Количество информации содержащееся в сообщении : « В аварию попал автомобиль не серого цвета» равно бита. Информационный объем сообщения «В аварию попал серый или белый автомобиль» равен бит. Определить количество автомобилей белого цвета.
35. Добрый экзаменатор никогда не ставит двоек по информатике. Он заранее определил количество отметок каждого вида и произвольно расставил их абитуриентам. Причем количество абитуриентов ,которым он не поставил 5 оказалось равно 21. Количество информации в сообщении «Абитуриент Иванов не сдал экзамен на отлично» равно бит. Информационный объем сообщения «Абитуриент Сидоров не получил 4» равен 1 биту. Определите количество абитуриентов, сдавших экзамен на 4 или 5.
36. Сельскохозяйственная фирма. Засеяла каждое из своих полей одной из трех культур: пшеницей, рожью или гречихой. Причем 23 поля засеяно не гречихой. Для проверки качества посева наугад выбирается одно поле. Количество информации, содержащееся в сообщении «Поле засеяно пшеницей» равно бит. Информационный объем сообщения «Поле засеяно не рожью» равен бит. Определить количество полей засеянных не пшеницей.
37. Каждый аспирант кафедры «Информатики» изучает только один из трех языков: английский, немецкий или французский. Причем 2 аспиранта изучают французский. Информационный объем сообщения «Аспирант Петров не изучает английский язык» равен бит. Количество информации в сообщении « Аспирант Иванов изучает немецкий язык» равно битам. Иностранный студент, приехавший в университет, знает только английский язык. Определите количество аспирантов, с которыми он сможет общаться.
