Задачи по теме «Измерение информации» Задачи егэ
|
Скачать 236.7 Kb.
|
|
Сборник задач «Измерение информации» СОДЕРЖАНИЕ
1.1 Содержательный подход. Вопрос «как измерить информацию?» очень непростой. Ответ на него зависит от того, что понимать под информацией. Но поскольку определять информацию можно по-разному, то и способы измерения тоже могут быть разными. Выше мы подошли к информации только с одной стороны: выяснили, чем она является для человека. Другую точку зрения на информацию, объективную, то есть не связанную с её отношением к человеку, мы обсудим несколько позже. Итак, пока остаемся на прежней позиции: информация — это знания человека. Отсюда следует вывод, что сообщение информативно (содержит ненулевую информацию), если оно пополняет знания человека. Например, прогноз погоды на завтра — информативное сообщение, а сообщение о вчерашней погоде неинформативно: нам это уже известно. Нетрудно понять, что информативность одного и того же сообщения может быть разной для разных людей. Например: 2 х 2 = 4 информативно для первоклассника, изучающего таблицу умножения, и неинформативно для старшеклассника. Отсюда, казалось бы, следует вывод, что сообщение информативно для человека, если оно содержит новые сведения, и неинформативно, если сведения старые, известные. Но вот вы раскрыли учебник по высшей математике и прочитали там такое определение: Значение определённого интеграла равно разности значений первообразной подынтегральной функции на верхнем и на нижнем пределах. Пополнил этот текст ваши знания? Скорее всего, нет! Он вам непонятен, а поэтому – неинформативен. Быть понятным, значит быть логически связанным с предыдущими знаниями человека. Для того, чтобы понять данное определение, нужно изучить элементарную математику и знать начала высшей. Получение всяких знаний должно идти от простого к сложному. И тогда каждое новое сообщение будет понятным, а значит, будет нести информацию для человека. Сообщение несёт информацию для человека, если содержащиеся в нём сведения являются для него новыми и понятными. Неопределённость знаний и единица информации. Пока мы с вами научились различать лишь две ситуации: «нет информации» — «есть информация», то есть количество информации равно нулю или не равно нулю. Но, очевидно, для измерения, тогда мы сможем определять, в каком сообщении информации больше, в каком — меньше. Единица измерения информации была определена в науке, которая называется теорией информации. Эта единица называется «бит». Её определение звучит так: Сообщение, уменьшающее неопределённость знаний в два раза, несёт 1 бит информации. В этом определении есть понятия, которые требуют пояснения. Что такое «неопределённость знаний»? Лучше всего это объяснить на примерах. Допустим, вы бросаете монету, загадывая, что выпадет: орёл или решка? Есть всего два варианта возможного результата бросания монеты. Причём, ни один из этих вариантов не имеет преимущества перед другим. В таком случае говорят, что они равновероятны. В этом случае перед подбрасыванием монеты неопределённость знаний о результате равна двум. Игральный кубик с шестью гранями может с равной вероятностью упасть на любую из них. Значит, неопределённость знаний о результате бросания кубика равна шести. Ещё пример: спортсмены-лыжники перед забегом путём жеребьёвки определяют свой порядковый номер на старте. Допустим, неопределённость знаний спортсменом своего номера до жеребьёвки равна ста. Следовательно, можно сказать так: неопределённость знаний о некотором событии — это количество возможных результатов события (бросания монеты, кубика; вытаскивания жребия). Вернёмся к примеру с монетой. После того, как вы бросили монету и посмотрели на неё, вы получили зрительное сообщение, что выпал, например, орёл. Произошла одно из двух возможных событий. Неопределённость знаний уменьшилась в два раза: было два варианта, остался один. Значит, узнав результат бросания монеты, вы получили 1 бит информации Сообщение о том, что произошло одно событие из двух равновероятных, несёт 1 бит информации. А теперь такая задача: студент на экзамене может получить одну из четырёх оценок: «5» — «отлично», «4» — «хорошо», «3» — «удовлетворительно», «2» — неудовлетворительно». Представьте себе, что ваш товарищ пошёл сдавать экзамен. Причём, учится он очень неровно и может с одинаковой вероятностью получить любую оценку от «2» до «5». Вы волнуетесь за него, ждёте результата экзамена. Наконец, он пришёл и на ваш вопрос: «Ну, что получил? — ответил: «Четвёрку!». Вопрос. Сколько бит информации содержится в его ответе? Если сразу сложно ответить на этот вопрос, то давайте подойдём к ответу постепенно. Будем отгадывать оценку, задавая вопросы, на которые можно ответить только «да» или «нет». Вопросы будем ставить так, чтобы каждый ответ уменьшал количество вариантов в два раза и, следовательно, приносил 1 бит информации. Первый вопрос: Оценка выше тройки? Да! После этого ответа число вариантов уменьшилось в два раза. Остались только «4» и «5». Получен 1 бит информации. Второй вопрос: Ты получил пятёрку? Нет! Выбран один вариант из двух оставшихся: оценка – «четвёрка». Получен еще 1 бит информации. В сумме имеем 2 бита. Сообщение о том, что произошло одно из четырёх равновероятных событий несёт 2 бита информации. Метод поиска, на каждом шаге которого отбрасывается половина вариантов, называется методом половинного деления. Решим ещё одну частную задачу, применив этот метод, а потом выведем общее правило. На книжном стеллаже восемь полок. Книга может быть поставлена на любую из них. Сколько информации содержит сообщение о том, где находится книга? Задаём вопросы: Книга лежит выше четвёртой полки? Нет. Книга лежит ниже третьей полки? Да. Книга – на второй полке? Нет. Ну, теперь всё ясно! Книга лежит на первой полке! Каждый ответ уменьшал неопределённость в два раза. Всего было задано три вопроса. Значит, набрано 3 бита информации. И если бы сразу было сказано, что книга лежит на первой полке, то этим сообщением были бы переданы те же 3 бита информации. А сейчас попробуем получить формулу, по которой вычисляется количество информации, содержащейся в сообщении о том, что произошло одно из множества равновероятных событий. Обозначим буквой N количество возможных событий, или, как мы это ещё называли, - неопределённость знаний. Буквой i будем обозначать количество информации в сообщении о том, что произошло одно из N событий. В примере с монетой N = 2, i = 1. В примере с оценками N = 4, i = 2. В примере со стеллажом N = 8, i = 3. Нетрудно заметить, что связь между этими величинами выражается формулой: 2i = N Действительно: 21 = 2; 22 = 4; 23 = 8. Если величина N известна, аi – неизвестно, то формула становится показательным уравнением для определения i. Например, пусть на стеллаже не 8, а 16 полок. Чтобы ответить на вопрос, сколько информации содержится в сообщении о том, где лежит книга, нужно решить уравнение: 2i = 16. Поскольку 16 = 24, то i = 4. Количество информации i, содержащееся в сообщении о том, что произошло одно из N равновероятных событий, определяется из решения показательного уравнения: 2i= N. Если значение N равно целой степени числа 2 (4, 8,16, 32, 64 и т.д.), то такое уравнение решается просто: i будет целым числом. А чему равно количество информации в сообщении о результате бросания игральной кости, у которой имеется шесть граней и, следовательно, N = 6? Решение уравнения 2i= 6 будет дробным числом, лежащим между числами 2 и 3, поскольку 22 = 4, а 23= 8. С точностью до пяти знаков после запятой решение такое: 2,58496. Алфавитный подход. Способ, не связывающий количество информации с содержанием сообщения, называется алфавитным подходом. Проще всего разобраться в этом на примере текста, написанного на каком-нибудь языке. Для нас удобнее, чтобы это был русский язык. Всё множество используемых в языке символов будем традиционно называть алфавитом. Обычно под алфавитом понимают только буквы, но поскольку в тексте могут встречаться знаки препинания, цифры, скобки, то мы их тоже включим в алфавит. В алфавит также следует включить и пробел (промежуток между словами). Полное число символов алфавита принято называть мощностью алфавита. Будем обозначать эту величину буквой N. Например, мощность алфавита из русских букв и дополнительных символов равна 54. Представьте себе, что текст к вам поступает последовательно, по одному знаку, словно бумажная ленточка, выползающая из телеграфного аппарата. Предположим, что каждый появляющийся на ленте символ с одинаковой вероятностью может быть любым символом алфавита. В действительности это не совсем так, но для упрощения примем такое предположение. В каждой очередной позиции текста может появиться любой из N символов. Каждый символ несёт i бит информации; число i можно определить из уравнения: 2i = N. Для N – 54, получаем: i = 5,755 бит. Вот сколько информации несёт один символ в русском тексте! А теперь для того, чтобы найти количество информации во всём тексте, нужно посчитать число символов в нём и умножить на i. Возьмём с книжной полки какую-нибудь книгу и посчитаем количество информации на одной её странице. Пусть страница содержит 50 строк. В каждой строке – 60 символов. Значит, на странице умещается 50х60 = 17265 бит. Следовательно, при алфавитном подходе к измерению информации количество информации от содержания не зависит. Количество информации зависит от объёма текста (то есть от числа знаков в тексте) и от мощности алфавита. Отсюда следует, например, что нельзя сравнивать информационные объёмы текстов, написанных на разных языках, только по объёму. У них отличаются информационные веса одного символа, так как мощности алфавитов разных языков – различные. Но если книги написаны на одном языке, то понятно, что в толстой книге информации больше, чем в тонкой. При этом содержательная сторона книги в расчёт не берётся. Сформулируем правило, как измерить информацию, используя для этого алфавитный подход. Количество информации, содержащееся в символьном сообщении, равно К х i, где К – число символов в тексте сообщения а i – информационный вес символа, который находится из уравнения 2i = N, где N – мощность используемого алфавита. Применение алфавитного подхода удобно, прежде всего, при использовании технических средств работы с информацией. В этом случае теряют смысл понятия «новые – старые», «понятные – непонятные» сведения. Алфавитный подход является объективным способом измерения информации в отличие от субъективного, содержательного, подхода.
Основополагающая роль в вероятностном подходе принадлежит энтропии множества вероятностей, формула которой была получена в 1948 году американским исследователем К. Шенноном. Предлагая для измерения количества информации свою знаменитую энтропийную меру, К. Шеннон руководствовался следующими соображениями. Вероятность p – количественная априорная (т.е. известная до проведения опыта) характеристика одного из исходов (событий) некоторого опыта. Измеряется в пределах от 0 до 1. Если заранее известны все исходы опыта, сумма их вероятностей равна 1, а сами исходы составляют полную группу событий. Если все исходы могут свершиться с одинаковой долей вероятности, они называются равновероятными. Например, пусть опыт состоит в сдаче студентом экзамена по информатике. Очевидно, у этого опыта всего 4 исхода (по количеству возможных оценок, которые студент может получить на экзамене). Тогда эти исходы составляют полную группу событий, т.е. сумма их вероятностей равна 1. Если студент учился хорошо в течение семестра, значения вероятностей всех исходов могут быть такими: p(5) = 0.5; p(4) = 0.3; p(3) = 0.1; p(2) = 0.1, где запись p(j) означает вероятность исхода, когда получена оценка j (j = {2, 3, 4, 5}). Если студент учился плохо, можно заранее оценить возможные исходы сдачи экзамена, т.е. задать вероятности исходов, например, следующим образом: p(5) = 0.1; p(4) = 0.2; p(3) = 0.4; p(2) = 0.3. В обоих случаях выполняется условие: где n – число исходов опыта, i – номер одного из исходов. Пусть можно получить n сообщений по результатам некоторого опыта (т.е. у опыта есть n исходов), причем известны вероятности получения каждого сообщения (исхода) - p i . Тогда в соответствии с идеей Шеннона, количество информации I в сообщении i определяется по формуле: где p i – вероятность i -го сообщения (исхода). Пример 1. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для студента-хорошиста. Пусть I(j) – количество информации в сообщении о получении оценки j. В соответствии с формулой Шеннона имеем: I(5) = -log2 0,5 = 1, I(4) = -log2 0,3 = 1,74, I(3) = -log2 0,1 = 3,32, I(2) = -log2 0,1 = 3,32. Пример 2. Определить количество информации, содержащейся в сообщении о результате сдачи экзамена для нерадивого студента: I(5) = -log2 0,1 = 3,32, I(4) = -log2 0,2 = 2,32, I(3) = -log2 0,4 = 1,32, I(2) = -log2 0,3 = 1,74. Таким образом, количество получаемой с сообщением информации тем больше, чем неожиданнее данное сообщение. Этот тезис использован при эффективном кодировании кодами переменной длины (т.е. имеющими разную геометрическую меру): исходные символы, имеющие большую частоту (или вероятность), имеют код меньшей длины, т.е. несут меньше информации в геометрической мере, и наоборот.
строки, в каждой строке 56 символов. В одном из представлений Unicode каждый символ кодируется 2 байтами. Определите информационный объём статьи в этом варианте представления Unicode 11) 12) Отв 176 бит 13) Отв 216 бит 14) 15) 16) 17) 18) Отв 12 19) Отв 16 20) 21) 22) 23) Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке длиной 75 символов, первоначально записанного в 16-битной кодировке Unicode, в 8-битный код КОИ-8. На сколько битов уменьшилась длина сообщения? Отв 600 24) Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке длиной 80 символов, первоначально записанного в 8-битной кодировке КОИ-8, в 16-битный код Unicode. На сколько битов увеличилась длина сообщения? Отв 640 25) Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке длиной 120 символов, первоначально записанного в 16-битной кодировке Unicode, в 8-битный код КОИ-8. На сколько битов уменьшилась длина сообщения? Отв 960
Отв 1,5 бита
1) В мотокроссе участвуют 238 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 140 мотоциклистов? Ответ 1120 бит 2) Каждая ячейка памяти компьютера, работающего в пятеричной системе счисления, может принимать 5 различных значений (-2, -1, 0, 1, 2). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина? Отв 625 3) При сдаче экзамена в университете в память компьютера заносится индивидуальный буквенно-цифровой код студента и его оценка. Код состоит из 12 символов. В качестве символов используют 26 букв английского алфавита и десятичные цифры в любом порядке. При этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Оценка — число от 0 до 10 — также кодируется с использованием минимально возможного и одинакового количества битов. Код студента вместе с его оценкой записывается минимально возможным и целым числом байтов. Определите объём файла, содержащего такую информацию, после сдачи экзамена 48 студентами. Отв 480 байт 4) Для регистрации на сайте пользователю требуется придумать пароль. Длина пароля — ровно 15 символов. В качестве символов используются десятичные цифры и 28 различных букв, причём все буквы используются в двух начертаниях — как строчные, так и заглавные (регистр буквы имеет значение!). Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти, который требуется для хранения 20 паролей. Отв 280 байт
Отв 230 байт
Отв 810 байт 9) На некотором сайте при регистрации требуется придумать пароль длиной ровно 6 символов, состоящий из 15 определённых символов и любых десятичных цифр в произвольном порядке. Каждый такой пароль в компьютерной программе на сайте записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти, отводимый этой программой для записи 100 паролей. Отв 400 байт 10) На некотором сайте при регистрации требуется придумать пароль длиной до 5 символов, состоящий из 25 определённых символов и любых десятичных цифр в произвольном порядке. Каждый такой пароль в компьютерной программе на сайте записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы также кодируются одинаковым и минимально возможным количеством байт). Определите объём памяти, отводимый этой программой для записи 20 паролей. Отв 100 байт
13) Для входа в детском игрушечном компьютере требуется придумать пароль длиной не более 4 символов, состоящий из 33 заглавных русских букв и любых десятичных цифр в произвольном порядке. Каждый такой пароль записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти, отводимый в таком компьютере для записи 15 паролей. Отв 45 байт 14) Для кодирования сообщений решено использовать последовательности разной длины из двух знаков: € и ₣. Сколько различных символов можно закодировать, используя подобный код длиной не менее пяти и не более десяти знаков (€ и ₣)? Отв 2016 15) Световое табло состоит из лампочек, каждая из которых может находиться в одном из 3 состояний (включена, выключена, мигает). Какое наименьшее количество лампочек n должно находиться на табло, чтобы с его помощью можно было передать 122 различных сигнала, используя не менее одной и не более n лампочек? Отв 5 16) Для кодирования решено использовать последовательности разной длины из трёх знаков: D, O и G. Сколько различных символов можно закодировать, используя подобный код длиной не менее двух и не более четырёх знаков (D, O и G)? Отв 117 17) Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире)? Отв 24 18) Некоторое количество символов кодируется с помощью трёх знаков: «+», «−» и «*». Сколько всего различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя такой код длиной не менее трёх и не более четырёх знаков? Отв 108 19) Некоторое количество символов кодируется с помощью четырёх знаков: «/», «\», «<�» и «>». Сколько всего различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя такой код длиной не менее двух и не более трёх знаков? Отв 80 20) Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее пяти и не более шести сигналов (точек и тире)? Отв 96 21) Некоторое количество символов кодируется с помощью четырёх знаков: «/», «\», «<�» и «>». Сколько всего различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя такой код длиной не менее трёх и не более четырёх знаков? Отв 320 22) Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)? Отв 48 23) Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов? Отв 3 24) Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов? Отв 32 25) Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля? Отв 6 26) Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60? Отв 6 27) Некоторый алфавит содержит 4 различных символа. Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться? Отв 64 28) Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в пять секунд можно передать при помощи этого устройства? Отв 243 29) Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код азбуки Морзе длиной не менее трёх и не более 5 сигналов (точек и тире)? Отв 56 30) Сколько есть различных символьных последовательностей длины от двух до четырёх в трёхбуквенном алфавите {А, B, C}? Отв 117
|
Добавить документ в свой блог или на сайт
Похожие:
 |
Задачи библиотеки: Главные задачи работы библиотеки в 2013/2014 уч... Поддерживать и обеспечивать образовательные задачи, сформулированные в концепции школы и в школьной программе |
 |
Литература Задачи по теме «Системы счисления» Какое из приведенных ниже чисел с в двоичной системе соответствует неравенству: A |
|
Нелинейный метод наименьших квадратов Постановка задачи Постановка задачи. Что будет, если зависимость наблюдаемых значений yi от параметров нелинейная, т е |
|
Задачи истории литературы: Задачи, связанные с изучением отдельного... Принцип историзма. Умение отстраняться от современности, широкая эрудиция, умение «вживаться» в эпоху |
|
Постановка задачи Роботы — это физические агенты, которые выполняют поставленные перед ними задачи, проводя манипуляции в физическом мире. Управление... |
|
К курсовому проекту по курсу «Операционные системы и среды» Тема:... Главная идея такого подхода – в разделении всей задачи на более мелкие подзадачи, которые могут быть вычислены независимо друг от... |
|
План работы координатора егэ на 2010-2011 учебный год Сентябрь Информирование по вопросам подготовки к егэ: знакомство с инструкций, ее дополнение по подготовке к егэ; правила поведения на егэ;... |
|
Определение ориентации неподвижного объекта с помощью спутниковых радионавигационных систем В статье рассматривается постановка задачи определения ориентации. Описана модель, используемая для решения задачи. Приведен алгоритм... |
|
Урок по теме «А. С. Пушкин» Цели и задачи: развитие способности воспринимать и понимать глубинный смысл поэзии, стимулирование творческой деятельности учащихся;... |
|
Задачи: Образовательные: Вспомнить историю открытия Лицея и жизнь... Цель: Представление результатов исследовательской деятельности учащихся по теме «Лицейские друзья А. С. Пушкина в Томске» |