Методические указания к выполнению практических работ по ОТИ Практическая работы 1-4

Пояснительная записка

Практические задания учебной дисциплины «Основы теории информации »

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

В результате освоения учебной дисциплины обучающийся должен уметь:

 применять правила недесятичной арифметики;

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

повышать помехозащищенность и помехоустойчивость передачи информации;

кодировать информацию (символьную, числовую, графическую, звуковую, видео);

сжимать и архивировать информацию;

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

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

ОК-3. Решать проблемы, оценивать риски и принимать решения в нестандартных ситуациях.

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

ОК-5. Использовать информационно-коммуникационные технологии для совершенствования профессиональной деятельности.

ОК-6. Работать в коллективе и команде, обеспечивать ее сплочение, эффективно общаться с коллегами, руководством, потребителями.

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

ОК-8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознано планировать повышение квалификации.

ОК-9. Быть готовым к смене технологий в профессиональной деятельности.

ОК-10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).

В результате освоения учебной дисциплины обучающийся должен знать:

основные понятия теории информатики;

виды информации и способы представления ее в электронно – вычислительных машинах;

свойства информации;

меры и единицы измерения информации;

принципы кодирования и декодирования;

основы передачи данных;

каналы передачи информации.

ПК-1.1. Обрабатывать статический информационный контент.

ПК-1.2. Обрабатывать динамический информационный контент.

ПК 1.3. Осуществлять подготовку оборудования к работе.

ПК-2.1. Проводить исследование объекта автоматизации.

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

Практическая работа №1.  – 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 связаны формулой:

2^x = N

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

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

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

x = log₂N

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 байт = 8 бит

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

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

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

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

1 килобайт = 1 Кб = 2¹⁰ байт = 1024 байта

1 мегабайт = 1 Мб = 2¹⁰ Кб = 1024 Кб =  1048576 байт

1 гигабайт = 1 Гб = 2¹⁰ Мб = 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 бокалов. Сколько единиц информации будет содержать сообщение о бокале с ядом?

Критерии оценки:

  Оценка «5» ставится студенту, полно и правильно выполнившему задание.

  Оценка «4» ставится студенту, допустившему 1-2 недочета.

  Оценка «3» ставится студенту, допустившему 3-4 недочета.

  Оценка «2» ставится студенту, выполнившему задание менее, чем на 50%.

 Контроль  и оценка осуществляется преподавателем за  выполненную работу

Практическая работа 2 – 2+2 ч

ТЕМА: Построение префиксных кодов.

Теоретическая часть

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

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

И т.д. до 33-ей строки..

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

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

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

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

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

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

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

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

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

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

е

ё

ж

з

и

й

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

е

ё

ж

з

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

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

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

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

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

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

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

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

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

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

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

· во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке.

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

Задание Реализуйте шифрование Вижинера – 2 ч

1. Цитата из поэмы А. С. Пушкина «Полтава»  (1829), песнь I:

Богат и славен Кочубей,

Его луга необозримы:

Там табуны его коней

Пасутся вольны, нехранимы.

Кругом Полтавы хутора

Окружены его садами,

И много у него добра,

Мехов, атласа, серебра

И на виду и под замками...

2. Цитата из басни И. А. Крылова «Воспитание Льва» (1811).

Лев предполагает отдать сына на воспитание Кроту, так как

о нем молва была,

Что он во всем большой порядок любит:

Без ощупи шага не ступит,

И всякое зерно для своего стола

Он сам и чистит, сам и лупит;

И, словом, слава шла,

Что Крот великий зверь на малые дела...

3. Цитата из стихотворения Г.  Р.  Державина «На смерть кн. Мещерского» (1779):

Сын роскоши, прохлад и нег,

Куда, Мещерский, ты сокрылся?

Оставил ты сей жизни брег,

К брегам ты мертвых удалился...

Где стол был яств, там гроб стоит;

Где пиршеств раздавались лики,

Надгробные там воют клики

И бледна Смерть на всех глядит...

4.

A mouse

A mouse is a hand-operated input device. If you use your imagination, it does actually look like a real mouse. A mouse can be used to move a cursor (a pointer) around the screen, to draw shapes or to make a choice from a menu. (A menu is a list of different options.)

5.Цитата поставлена эпиграфом к 4-й главе повести А.С. Пушкина • «Дубровский».

О небо!

Где ж правота, когда священный дар,

Когда бессмертный гений — не в награду

Любви горящей, самоотверженья,

Трудов, усердия, молений послан —

А озаряет голову безумца,

Гуляки праздного?..

Критерии оценки:

  Оценка «5» ставится студенту, полно и правильно выполнившему задание.

  Оценка «4» ставится студенту, допустившему 1-2 недочета.

  Оценка «3» ставится студенту, допустившему 3-4 недочета.

  Оценка «2» ставится студенту, выполнившему задание менее, чем на 50%.

 Контроль  и оценка осуществляется преподавателем за  выполненную работу

ТЕМА: Построение префиксных кодов.

ЦЕЛЬ:  ознакомление с построением префиксных кодов.

Задание Реализуйте шифрование Вижинера – 2 ч

1.Цитата из трагедии Шекспира «Гамлет», д. 1, сц. 5, слова Гамлета. В переводе М. Вронченко (1828):

Есть многое в природе, друг Горацио,

Что и не снилось нашим мудрецам.

2.Цитата из комедии А. С. Грибоедова «Горе от ума» (1824), д. 4, явл. 4. Чацкий, прерывая вранье Репетилова, говорит ему:

 Послушай, ври, да знай же меру;

 Есть от чего в отчаянье прийти.

3.Выражение из лирической комедии Н.А. Некрасова «Медвежья охота» (1868)

                               Диалектик обоятельный

Честен мыслью, сердцем чист!

Помню я твой взор мечтательный,

Либерал-идеалист!..

Грознйы деятель в теории,

Беспощадный радикал,

Ты на улице истории

С полицейским избегал.

49.                                                                                         A mouse

A mouse is a hand-operated input device. If you use your imagination, it does actually look like a real mouse. A mouse can be used to move a cursor (a pointer) around the screen, to draw shapes or to make a choice from a menu. (A menu is a list of different options.)

5.                                                      The Keyboard.

There is one input device invented long before the first computer: The Keyboard. Computers now have a great variety of keyboard* but all of them have the standard layout.

Критерии оценки:

  Оценка «5» ставится студенту, полно и правильно выполнившему задание.

  Оценка «4» ставится студенту, допустившему 1-2 недочета.

  Оценка «3» ставится студенту, допустившему 3-4 недочета.

  Оценка «2» ставится студенту, выполнившему задание менее, чем на 50%.

 Контроль  и оценка осуществляется преподавателем за  выполненную работу

Практическая работа №3.  – 2+2 ч

ТЕМА: Код  Хемминга.

Теоретическая часть

Определение 1: Пусть A={a₁,a₂,_...,a_n} - алфавит из n различных символов, W={w₁,w₂,_...,w_n} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c₁,c₂,_...,c_n}, такой что:

(1)	ci не является префиксом для cj, при i!=j

(2)

минимальна (|ci| длина кода ci)

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

Замечания:

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.                     Веса узлов будем обозначать нижними индексами: A₅, B₃, C₇.

3.                     Составные узлы будем заключать в скобки: ((A₅+B₃)₈+C₇)₁₅.

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

1.                     A₂ B₁ C₅ D₂ E₇ F₁ G₃ H₁₅

2.                     A₂ C₅ D₂ E₇ G₃ H₁₅ (F₁+B₁)₂

3.                     C₅ E₇ G₃ H₁₅ (F₁+B₁)₂ (A₂+D₂)₄

4.                     C₅ E₇ H₁₅ (A₂+D₂)₄ ((F₁+B₁)₂+G₃)₅

5.                     E₇ H₁₅ ((F₁+B₁)₂+G₃)₅ (C₅+(A₂+D₂)₄)₉

6.                     H₁₅ (C₅+(A₂+D₂)₄)₉ (((F₁+B₁)₂+G₃) ₅+E₇)₁₂

7.                     H₁₅ ((C₅+(A₂+D₂)₄) ₉+(((F₁+B₁)₂+G₃) ₅+E₇)₁₂)₂₁

8.                     (((C₅+(A₂+D₂)₄) ₉+(((F₁+B₁)₂+G₃) ₅+E₇)₁₂)₂₁+H₁₅)₃₆

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

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" - правого. Используя этот механизм, мы без труда можем присвоить коды всем символам кодируемого алфавита. Выпишем, к примеру, коды для всех символов в нашем примере:

A=0010bin	C=000bin	E=011bin	G=0101bin
B=01001bin	D=0011bin	F=01000bin	H=1bin

Теперь у нас есть все необходимое для того чтобы закодировать сообщение 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 символов, на каждый из которых отводилось по [log₂|A|]=3 бита (здесь и далее будем понимать квадратные скобки [] как целую часть, округленную в положительную сторону, т.е. [3,018]=4). Таким образом, размер S равен 36*3=108 бит

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

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

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

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

Задание 1.

однозначно декодировать коды переменной длины

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

ssssoooeeerroooaayyyyyddddoeuuuuuwwwwjjjorruuuuuuuuuuxxxkhhhhhhmmmmmmgggllllllljjjj

Задание 2.

однозначно декодировать коды переменной длины

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

FFFFFFFFKKKKKSSSSUURERRRRRRRRRPPPPPPPPDDDDKKKKKKGLDDDDDDDDKKKKKKKKGGGGMGMMMM

Критерии оценки:

  Оценка «5» ставится студенту, полно и правильно выполнившему задание.

  Оценка «4» ставится студенту, допустившему 1-2 недочета.

  Оценка «3» ставится студенту, допустившему 3-4 недочета.

  Оценка «2» ставится студенту, выполнившему задание менее, чем на 50%.

 Контроль  и оценка осуществляется преподавателем за  выполненную работу

ТЕМА: Код  Хемминга.

Теоретическая часть

Метод RLE.

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

Задание 1.

однозначно декодировать коды переменной длины

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

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

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

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

Критерии оценки:

  Оценка «5» ставится студенту, полно и правильно выполнившему задание.

  Оценка «4» ставится студенту, допустившему 1-2 недочета.

  Оценка «3» ставится студенту, допустившему 3-4 недочета.

  Оценка «2» ставится студенту, выполнившему задание менее, чем на 50%.

 Контроль  и оценка осуществляется преподавателем за  выполненную работу

 

Практическая работа №4.  2+2 ч

ТЕМА: Блочное кодирование.

Теоретическая часть

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

Пример:

Рассмотрим последовательность строчных букв русского алфавита: а, б, в, г, д, е, ё, ж, з, и, й. к, л, м. н. о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, в, э, ю, я. Присвоив каждой букве номер от 0 до 33. получим простейший способ представления символов. Последнее число - 32 в двоичной форме имеет вид 100000, то есть для хранения символа в памяти понадобится 6 бит.Так как с помощью шести бит можно представить число 2⁶ - 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-код символа А= 65₁₀ =41₁₆= 01000111₂;

Unicode-код символа С= 67₁₀=0000000001100111₂

Задание 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, после чего в тексте появится буква, закодированная набранным кодом.

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

Критерии оценки:

  Оценка «5» ставится студенту, полно и правильно выполнившему задание.

  Оценка «4» ставится студенту, допустившему 1-2 недочета.

  Оценка «3» ставится студенту, допустившему 3-4 недочета.

  Оценка «2» ставится студенту, выполнившему задание менее, чем на 50%.

 Контроль  и оценка осуществляется преподавателем за  выполненную работу

ТЕМА: Блочное кодирование.

Задания– 2 ч

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

Решение:

·  Создать новый текстовый документ в Word;

·  Выбрать  – Команда –  Вставка – Символ.          
В открывшемся окне «Символ» установить из: Юникод (шестн.),

·  В наборе символов находим букву  К и щелкнем на ней левой кнопкой мыши (ЩЛКМ).

·  В строке код знака  появится код выбранной буквы 041А (незначащие нули тоже записываем).

·  У буквы о код – 043Е и так далее: д – 0434, и – 0438, р – 0440, о – 043Е, в – 0432, к – 043А, а – 0430.

·  Установить Кириллица (дес.)

·  К – 0202, о – 0238, д – 0228, и – 0232, р – 0240, о – 0238, в –0226, к – 0202, а –0224.

Задание 1.

Открыть 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

Вывод: _________________________________________________________

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

Задание 2.

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

Задание 3.

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

Задание 4.

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

Задание 5.

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

Критерии оценки:

  Оценка «5» ставится студенту, полно и правильно выполнившему задание.

  Оценка «4» ставится студенту, допустившему 1-2 недочета.

  Оценка «3» ставится студенту, допустившему 3-4 недочета.

  Оценка «2» ставится студенту, выполнившему задание менее, чем на 50%.

 Контроль  и оценка осуществляется преподавателем за  выполненную работу