Информатика. Формула Шеннона. Количество информации как мера уменьшения неопределенности знания
 Скачать 242.5 Kb.
|
Занимательные задачи1.Передача текста. При передаче текстового сообщения возможна ошибка при приеме любой буквы. Для повышения надежности можно передавать каждый символ дважды, но тогда поиск правильного вида сообщения производится перебором всех возможных комбинаций символов из «поврежденных» пар с поиском среди полученных вариантов осмысленных. Как модифицировать описанный метод передачи, чтобы дешифровку сообщений мог производить компьютер? Какой вариант модификации является оптимальным (требующим минимального увеличения длительности сообщения)? (Вероятность ошибочного приема более одного символа подряд считать равной нулю). Решение. Оптимальным вариантом, при котором расшифровка принятого текста может производиться компьютером (не понимающим смысла слов и интерпретирующим их только как последовательности байтов - кодов символов), является передача каждого символа трижды с исправлением возможных ошибок методом «голосования». Если в результате сбоя какой-либо из триад один символ отличается от двух других, именно они и показывают верный ответ. Число 3 является в указанных условиях необходимым и достаточным: другие количества повторов при увеличении длительности передачи практически не повышают ее надежность по сравнению с трехкратным повторением. 2. Серии Штермера. В начале 20 века при попытке определить методом радиолокации высоту расположения в атмосфере ионизированного (отражающего радиолучи) слоя был обнаружен интересный эффект. Эхо каждого посланного в небо радиосигнала было двойным: один ответный сигнал был отражен от слоя, а происхождение второго было неизвестно, причем интервалы между этими парами сигналов были разными. Записанные последовательности длительностей этих пауз (которые позже были названы сериями Штермера - по фамилии ученого, производившего эксперименты) до сих пор будоражат умы многих исследователей, считающих их посланиями другой цивилизации. Попробуйте помочь ученым и расшифровать две приведенные ниже серии Штермера, учитывая, что, по существующей гипотезе, последовательность двоичных представлений чисел-длительностей без учета незначащих нулей представляет собой зашифрованное изображение. а) 19, 128, 4, 17, 196, 768, 72, 56, 19, 128, 1024, 11, 252, 20480, 98, 118, 54, 10, 4, 42, 71, 138, 16, 69, 48; б) 7, 28, 68, 4, 47, 1, 30, 33, 400, 30, 35, 46, 5, 17, 74, 19, 39, 7, 17, 124, 5, 25. Решение. а) преобразуем первую серию в последовательность бит: 19 - 10011, 128 - 10000000, 4 - 100, 17 - 10001, 196 - 11000100, 768 - 1100000000, 72 - 1001000, 56 - 111000, 19 - 10011, 128 - 10000000, 1024 - 10000000000, 11 - 1011, 252 - 11111100, 20480 - 101000000000000, 98 - 1100010, 118 - 1110110, 54 - 110110, 10 - 1010, 4 - 100, 42 - 101010, 71 - 1000111, 138 - 10001010, 16 - 10000, 69 - 1000101, 48 - 110000. Подсчитаем общее количество бит: оно равно 169. Это число характерно тем, что из трех его делителей - 1, 13, 169 - первый и последний тривиальны, а оставшийся является простым числом, причем 169 - квадрат этого числа: 169=13*13. Предположим, что число 13 определяет размеры (в точках) квадратной картинки, которая, согласно гипотезе, зашифрована в сообщении. Начертим на клетчатой бумаге квадрат со стороной 13 клеток и перепишем значения бит подряд слева направо сначала в клетки первого ряда (верхнего), затем второго и т.д. вплоть до последнего. А теперь закрасим клетки, содержащие 1. Что получилось? б) преобразуем аналогичным образом в последовательность бит вторую серию: 7 - 111, 28 - 11100, 68 - 1000100, 4 - 100, 47 - 101111, 1- 1, 30 - 11110, 33 - 100001, 400 - 110010000, 30 - 11110, 35 - 100011, 46 - 101110, 5 - 101, 17 - 10001, 280 - 100011000, 17 - 10001, 74 - 1001010, 19 - 10011, 39 - 100111, 7 - 111, 17 - 10001, 124 - 1111100, 5 - 101, 25 - 11001. Подсчитав количество бит, получим число 125. Его нетривиальным делителем является число 5, причем 125=5*5. Предположим, что здесь мы имеем дело с «трехмерной» картинкой, или с пятью квадратными рисунками размером 5 на 5 точек каждый. Вычертим их рядом на клетчатой бумаге и заполним клетки битами также, как в предыдущем случае: сначала весь первый квадрат, затем второй и так до последнего. Закрасим клетки, содержащие 1. Что получилось на этот раз? 3. Решить арифметический ребус, т. е. Поставить в соответствие каждой букве в равенстве цифру (разные буквы обозначают разные цифры): ДАД = РАД. Решение. В десятичной системе счисления при записи натуральных чисел цифры, участвующие в записи числа указывают последовательно справа налево вес цифры в числе (количество единиц, затем десятков …), например, 45 = 4 * 10 + 5; 432 = 4 *100 + 3 * 10 + 2. В данном ребусе таким же образом нужно получить числа ДА и РАД. ДА = Д * 10 + А РАД = Р * 100 +А * 10 +Д. Далее организуем перебор значений переменных Р, А, Д (три вложенных цикла). нц для Р от 1 до 9 нц для А от 1 до 9 нц для Д от 0 до 9 если Д < > Р и Д < > А и Р < >А то ДА : = Д * 10 + А; РАД : = Р * 100 + А * 10 + Д если ДА ** Д = РАД то вывод РАД все все кц кц кц Ответ: 252 = 625. 4. а) Предложите самый простой способ кодирования любого текста так, чтобы шифровка и дешифровка могли осуществляться одним и тем же устройством (с помощью одной и той же операции над кодами символов). б) как шифровать текст с паролем (пароль - любое число о 1 до 255) с сохранением универсальности работы устройства? Решение. а) самый простой способ такой шифровки текста - заменять все единичные биты в двоичном коде символа на нулевые и наоборот, включая незначащие нули, т. е. Производить инверсию байта. Тогда вид символов будет изменяться довольно непредсказуемым на первый взгляд образом. Дешифровка производится обратной заменой, т. е. тоже инверсией. Операция дешифровки полностью идентична операции шифровки; б) шифровку с паролем будем в этом случае выполнять при помощи логической операции XOR, операндами которой являются байт-код символа и байт-пароль. Для шифровки потребуется повторно выполнить операцию XOR (используя то же самое число-пароль). Это возможно благодаря тому, что XOR относится к числу симметричных логических операций. 5. Незнайка написал послание и подписался одним зашифрованным словом, используя код, состоящий из 0 и 1. Им был выбран самый простой способ кодировки текста 32 букв алфавита( е = е). Знайка быстро расшифровал сообщение, распознав количество букв в нем, и посоветовал Незнайке быть поскромнее и более изобретательным. Определите ключ (принцип) шифровки и расшифруйте слово-подпись: 011111001111000010100100001101 Решение. Нужно каждой букве русского алфавита задать номер от 0 до 31. Максимальный номер (31) можно представить как двоичное число 31 =11111. Так как номеров больших 31 нет, то для кодирования русских букв достаточно пятизначного двоичного числа. Дальше необходимо разбить цепочку - шифр на группы из пяти знаков справа налево. 01111 = 15 - П 10011 = 19 - У 11000 = 24 - Ш 10100 = 10 - К 01000 = 8 - И 01101 = 13 - Н. Дидактическая игра "Домино"Педагогический процесс - это совокупность урочных занятий, внеклассной и внешкольной воспитательной работы, проводимых педагогическим и ученическим коллективами по одному плану. В обучении применяют в основном уроки-семинары, практические и лабораторные уроки, на которых используют различные методы и средства обучения. Увеличение умственной нагрузки на уроках заставляет задуматься над тем, как поддержать у учащихся интерес к изучаемому материалу, их активность на протяжении всего урока. Приходится искать эффективные методы обучения и такие методические приемы, которые активизировали бы мысль школьников, стимулировали бы их к самостоятельному приобретению знаний. Надо позаботиться о том, чтобы на уроках ученик работал активно и увлеченно, и использовать это как отправную точку для возникновения и развития любознательности, глубокого познавательного интереса. Немаловажную роль здесь можно отвести дидактическим играм. Доминирующим видом деятельности ребенка в первые годы обучения является игра. И, хотя, с возрастом она утрачивает свои позиции, в средних и старших классах она может сохранить свое влияние, как средство стимулирования интереса к учению. Игра - творчество, игра - труд. В процессе игры у детей вырабатывается привычка сосредоточиваться, мыслить самостоятельно, развивается внимание, стремление к знаниям, Разнообразные игровые действия, при помощи которых решается та или иная умственная задача, поддерживает и усиливает интерес детей к учебному предмету. Широкое понимание термина «занимательность» идет еще от Н.И. Лобачевского, творца неевклидовой геометрии. Он обосновывает дидактический принцип «преподавания, приноровленного к возрасту». Лобачевский считал, что занимательность - необходимое средство возбуждать и поддерживать внимание, без нее преподавание не бывает успешным. Современная дидактика, обращаясь к игровым формам обучения на уроках, справедливо усматривает в них возможность эффективной организации взаимодействия педагога и учащихся, продуктивной формой их общения с присущими им элементами соревнования, неподдельного интереса. Одной из таких игр может быть «Домино»: учащимся предлагаются карточки, состоящие из двух частей, необходимо найти взаимосвязь между различными карточками.
|