Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Макет индивидуально-образовательной траектории по дисциплине "Основы теории информации"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

Макет индивидуально-образовательной траектории по дисциплине "Основы теории информации"

библиотека
материалов

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ЯРОСЛАВСКОЙ ОБЛАСТИ
государственное профессиональное образовательное учреждение

Ярославской области

Рыбинский полиграфический колледж












Макет индивидуально-ориентированного плана обучающегося


_________________________________________

(ФИО, группа)

по дисциплине/МДК/ПМ

«Основы теории информации»


для специальности 09.02.02
















Рыбинск 2016 г.

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

Индивидуально-ориентированный план обучающегося составлен в соответствии с учебным планом и рабочей программой дисциплины/МДК/ПМ. Задачи данного плана:

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

  2. осуществить дифференциацию обучения на уроках, консультациях, во внеклассных мероприятиях;

  3. развивать самостоятельность обучающихся, умение организовывать и управлять своей учебно - познавательной деятельностью;

  4. развивать информационные и коммуникационные компетенции обучающихся.

  1. Тематический план и содержание УД/МДК/ПМ

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

Объем
часов

ОП.01. Основы теории информации


34/18/16/17




Раздел 1. Базовые понятия теории информации


10/6/4/5




Тема 1.1. Формальное представление знаний. Виды информации

Содержание: Понятие информации. Классификация информации.

2





Самостоятельная работа: Изучение темы "Принципы хранения, измерения, обработки и передачи информации".

1

Тема 1.2. Способы измерения информации

Содержание: Вероятностный подход к измерению дискретной и непрерывной информации Клода Шеннона. Методы и средства определения количества информации.

4





Практическое занятие 1: Методы и средства определения количества информации.

2


Практическое занятие 2: Поиск энтропии случайных величин.

2


Самостоятельная работа: Подготовка доклада по теме "Экспертные системы. Информация Фишера". Решение задач по теме.

4

Раздел 2. Кодирование информации


4/2/2/2




Тема 2.1. Способы кодирования информации

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

2





Практическое занятие 3: Кодирование и декодирование информации.

2


Самостоятельная работа: Решение задач.

2

Раздел 3. Энтропия


8/6/2/4




Тема 3.1. Смысл энтропии Шеннона

Содержание: Энтропийное кодирование. Пропускная способность дискретного канала. Интерполяционная формула Уиттекера-Шеннона, частота Найквиста. Семантическая информация. Закон аддитивности информации.

6





Практическое занятие 4: Понятие энтропии, формула Шеннона.

2


Самостоятельная работа: Решение задач.

4




Раздел 4. Защита и передача информации


12/4/8/6







Тема 4.1. Сжатие и передача информации

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

4





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

2


Практическое занятие 6: Теорема отчетов Котельникова и Найквиста - Шеннона.

2


Практическое занятие 7: Способы передачи цифровой информации.

2


Практическое занятие 8: Расчет скорости передачи информации.

2






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

6



3. Индивидуально – ориентированный план

  1. Методические материалы

Тема 1.1. Формальное представление знаний. Виды информации

Информация характеризует разнообразие (неоднородность) в окружающем мире.

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

При получении информации уменьшается неопределённость знания.

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

  • зрительная информация (визуальная, от англ. visual) - поступает через глаза (по разным оценкам, это 80-90 % всей получаемой нами информации);

  • звуковая информация (аудиальная, от англ. audio) - поступает через уши;

  • вкусовая информация - поступает через язык;

  • обонятельная информация (запахи) - поступает через нос;

  • тактильная информация - мы её получаем с помощью осязания (кожи), «на ощупь».

Ещё выделяют информацию, получаемую с помощью «мышечного чувства» (человеческий мозг получает импульсы от мышц и суставов при перемещении частей тела).

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

Формы представления информации

Информация может быть представлена (зафиксирована, закодирована) в различных формах:

  • текстовая информация - последовательность символов (букв, цифр, других знаков); в тексте важен порядок их расположения, например, КОТ и ТОК - два разных текста, хотя они состоят из одинаковых символов;

  • числовая информация;

  • графическая информация (рисунки, картины, чертежи, карты, схемы, фотографии и т. п.);

  • звуковая информация (звучание голоса, мелодии, шум, стук, шорох и т. п.);

  • мультимедийная информация, которая объединяет несколько форм представления информации (например, видеоинформация).

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

Для того чтобы данные стали информацией, их нужно понять и осмыслить, а на это способен только человек. Если человек, получающий сообщение, знает язык, на котором оно записано, он может понять смысл этого сообщения, т. е. получить информацию. Обрабатывая и упорядочивая информацию, человек выявляет закономерности - получает знания. Мы увидели, что в науке существуют достаточно тонкие различия между понятиями «данные», «информация», «знания». Тем не менее, на практике чаще всего всё это называется общим термином «информация».

Вопросы и задания

1. Как связана неопределенность знания с получением информации?

2. Как связана информация и сложность объекта?

3. Объясните, почему термин «информация» трудно определить.

4. Согласны ли вы с «определением» информации, которое дал Н. Винер? Как вы его понимаете?

5. Как человек воспринимает информацию?

6. Чем отличается текст от набора символов?

7. К какому виду информации относятся видеофильмы?

8. Что такое тактильная информация?

9. Всякая ли информация увеличивает знания? Почему?

10. Какими свойствами должна обладать «идеальная» информация?

11. Приведите примеры необъективной, непонятной, бесполезной, недостоверной, неактуальной и неполной информации.

12. Может ли информация быть достоверной, но бесполезной? Достоверной, но необъективной? Объективной, но недостоверной? Актуальной, но непонятной?

13. Приведите примеры обработки информации в технических устройствах.



Тема 1.2. Способы измерения информации

Для человека информация - это, прежде всего, смысл, заключённый в сигналах и данных. Как измерить смысл? На этот вопрос пока нет однозначного ответа.

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

Что такое бит?

Рассмотрим электрическую лампочку, которая может находиться в двух состояниях: «горит» и «не горит». Тогда на вопрос «Горит ли сейчас лампочка» есть два возможных варианта ответа, которые можно обозначить цифрами 1 («горит») и 0 («не горит») (рис. 1.5). Поэтому ответ на этот вопрос (полученная информация) может быть записан как 0 или 11.

Цифры 0 и 1 называют двоичными, и с этим связано название единицы измерения количества информации - бит. Английское слово bit - это сокращение от выражения binarу digit - «двоичная цифра». Впервые слово «бит» в этом значении использовал американский инженер и математик Клод Шеннон в 1948 г.

Бит — это количество информации, которую можно записать (закодировать) с помощью одной двоичной цифры.

Другие единицы

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

1 байт = 8 битов.

Сразу возникает вопрос: а почему не 10 битов? Дело в том, что слово «байт»1 (англ. byte) имеет второе значение - так называют наименьший блок (ячейку) памяти, который процессор компьютера может считать и обработать за один раз. Для современных компьютеров он состоит из 8 элементов, каждый из которых хранит 1 бит данных. Это связано с тем, что до недавнего времени при обработке текста использовался набор из 256 символов, так что для кодирования каждого символа было нужно 8 битов.

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

1 Кбайт (килобайт) = 1024 байта = 210 байта = 213 битов.

1 Мбайт (мегабайт) = 1024 Кбайт = 210 Кбайт = 220 байтов = 223 битов.

1 Гбайт (гигабайт) = 1024 Мбайт.

1 Тбайт (терабайт) = 1024 Гбайт.

1 Впервые его использовал американский инженер В. Бухгольц в 1956 г.

Так сложилось исторически, что при измерении количества информации приставка «кило-» обозначает, в отличие от международной системы единиц СИ, увеличение не в 1000 раз, а в 1024 = 210 раз. Аналогично «мега-» - это увеличение в 10242 = 220 = 1 048 576 раз, а не в 1 млн = 10002 раз.

Строго говоря, нужно называть такие кило- (мега-, гига-, ...) байты двоичными, поскольку множитель 1024 - это 210. Стандарт Международной электротехнической комиссии (МЭК) предлагает называть их «кибибайт», «мебибайт», «гибибайт» и «тебибайт», но эти названия на практике не прижились.

Для перевода количества информации из одних единиц в другие нужно использовать приведённые выше соотношения. При переводе из крупных единиц в мелкие числа умножают на соотношение между единицами. Например:

2 Кбайт = 2 ∙ (1 Кбайт) = 2 ∙ 1024 байтов = 2048 байтов = 2048 ∙ (1 байт) = 2048 ∙ 8 битов = 16 384 бита.

2 Кбайт = 2 ∙ 210 байтов = 211 байтов = 211 ∙ 23 битов = 214 битов.

В последней строке все расчёты сделаны через степени числа 2, очень часто так бывает проще.

При переводе количества информации из мелких единиц в крупные нужно делить на соотношение между единицами. Например:

8192 бита = 8192 ∙ (1/8 байта) = 8192 : 8 байтов = 1024 байта = 1024 ∙ (1/1024 Кбайт) = 1024 : 1024 Кбайт = 1 Кбайт.

8192 бита = 213 битов = 213 ∙ (1/23 байта) = 210 байтов = 210 ∙ (1/210 Кбайт) = 1 Кбайт.

Формула Хартли. Закон аддитивности информации

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

i= Log2N,

где i -количество информации в битах; N - число возможных состояний. Ту же формулу можно представить иначе:

N = 2i.

Пусть имеется N состояний системы S или N опытов с различными, равновозможными, последовательными состояниями системы. Если каждое состояние системы закодировать, например, двоичными кодами определенной длины d, то эту длину необходимо выбрать так, чтобы число всех различных комбинаций было бы не меньше, чем N. Наименьшее число, при котором это возможно, называется мерой разнообразия множества состояний системы и задается формулой Р. Хартли:

Н = klogaN,

где k — коэффициент пропорциональности (масштабирования, в зависимости от выбранной единицы измерения меры), а — основание системы меры.

Если измерение ведется в экспоненциальной системе, то k = 1, Н = lnN (нат); если измерение было произведено в двоичной системе, то k = 1/ln2, Н = log2N(бит); если измерение было произведено в десятичной системе, то k = 1/ln10, Н = lgN (дит).

Пример. Чтобы узнать положение точки в системе из двух клеток, т. е. получить некоторую информацию, необходимо задать один вопрос (Левая или правая клетка?). Узнав положение точки, мы увеличиваем суммарную информацию о системе на 1 бит (I = log22). Для системы из четырех клеток необходимо задать 2 аналогичных вопроса, а информация равна 2 битам (I = log24). Если же система имеет n различных состояний, то максимальное количество информации будет определяться по формуле: I = log2n.

Справедливо утверждение Хартли: если в некотором множестве Х = {х1, х2, …, хn} необходимо выделить произвольный элемент хi X, то для того, чтобы выделить (найти) его, необходимо получить не менее logan (единиц) информации.

Если N — число возможных равновероятных исходов, то величина klnN представляет собой меру нашего незнания о системе.

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

Формула Хартли отвлечена от семантических и качественных индивидуальных свойств рассматриваемой системы (качества информации в проявлениях системы с помощью рассматриваемых N состояний системы). Это основная и положительная сторона формулы. Но имеется основная и отрицательная ее сторона: формула не учитывает различимость и различность рассматриваемых N состояний системы.

Уменьшение (увеличение) Н может свидетельствовать об уменьшении (увеличении) разнообразия состояний N системы. Обратное, как это следует из формулы Хартли (так как основание логарифма больше 1!), — также верно.

Закон аддитивности информации

log2 (N1N2) = log2N1 + log2N2,

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

Пример.

Имеется 27 монет: 26 настоящих и одна фальшивая, она легче настоящих. Сколько взвешиваний необходимо произвести, чтобы определить фальшивую монету?

Фальшивой может оказаться любая из 27 монет, следовательно, по формуле Хартли количество недостающей информации равно log227 битов. Любое взвешивание имеет три исхода и может дать нам только log23 битов информации. Если мы производим Xвзвешиваний, то они дадут X log23 битов информации.

Итак, X log23 ≥ log227 = log233 = 3 ∙ log23.

Следовательно, X ≥ 3. На самом деле достаточно ровно 3 взвешиваний: первое по 9 монет, второе по 3 монеты из найденной группы и, наконец, по одной монете из найденной группы по 3 монеты.

Чтобы найти элемент множества, состоящего из 7 элементов, необходимо задать три вопроса, а чтобы найти элемент множества, состоящего из 9 элементов, - 4 вопроса, то есть по формуле Хартли получить log27 + log29 битов информации. Но если необходимо отгадать пару элементов из этих множеств, то требуется получить log2(7 ∙ 9) битов информации, а это меньше 6 вопросов. Противоречия нет:

­hello_html_m66c192e8.png.

hello_html_m65ad460b.gif

hello_html_7274334f.gif

Вопросы и задания

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

2. Приведите примеры сообщений, количество информации в которых равно 1 биту.

3. Что такое двоичные цифры?

4. Какие приставки рекомендует МЭК для обозначения двоичных килобайта и мегабайта? Как вы думаете, почему они редко используются?

5. Пассажир не знает, какой (только один!) из 8 поездов, стоящих на вокзале, проследует в Санкт-Петербург. В справочном бюро он задаёт 8 вопросов: «Поезд на 1-й платформе проследует в Санкт-Петербург?», «Поезд на 2-й платформе проследует в Санкт-Петербург?» и т. д. На первые 7 вопросов он получает ответ «нет», а на последний - «да». Пассажир считает, что он получил 8 битов информации. Прав он или нет? Почему?

*6. В зоопарке содержится 10 обезьян, причём одна из них выступает в цирке. Обезьяны сидят в двух вольерах, в первом - 8 животных, а во втором - два. Посетитель зоопарка считает, что сообщение «Обезьяна, выступающая в цирке, сидит во втором вольере» содержит 1 бит информации. Прав он или нет? Рассмотрите разные варианты уточнения постановки задачи.

7. В горах, рядом с которыми живёт племя Тумба-Юмба, есть 4 пещеры. В каждой из них может быть (а может не быть) клад. Можно ли закодировать сведения о том, где есть клады, используя 3 бита? 4 бита? 5 битов?

8. Известно, что ровно в двух пещерах из четырёх есть клады. Сколько битов нужно, чтобы закодировать информацию о расположении кладов?

*9. Известно, что дверь с двумя замками открывается двумя из четырёх имеющихся ключей. Оцените количество информации в сообщении «Дверь открывается ключами № 2 и № 4». Закодируйте его, используя наименьшее количество двоичных цифр.



Тема 2.1. Способы кодирования информации

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

Пример:

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

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

Пример:

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

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

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

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

Ðèñóíîê 22

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

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

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

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

Ðèñóíîê 23

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

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

Ðèñóíîê 24

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



Вопросы и задания:

  1. Правило цифрового представления символов

  2. Чем отличаются стандарты для представления символов?

  3. Какие кодировки символов вы знаете?

  4. Назовите самый распространённый код для информационного обмена?

  5. Назовите недостатки стандарта ISO-646?

  6. В виде чего представлена графическая информация на экране?

  7. Что называется глубиной цвета?

  8. Что называется разрешающей способностью?

  9. Что называется скорость передачи информации?

  10. Что считается процессором?

  11. Что такое код Хаффмана?

  12. Что называется деревом Хаффмана?

  13. Назовите расширения растровых графических изображений?

  14. Закодируйте свое имя, фамилию и отчество с помощью одной из таблиц (win-1251, KOI-8)

  15. Закодируйте следующие слова, используя таблицы ASCII-кодов: ИНФОРМАТИЗАЦИЯ, МИКРОПРОЦЕССОР, МОДЕЛИРОВАНИЕ

  16. Раскодируйте следующие слова, используя таблицы 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

  1. Известно, что видеопамять компьютера имеет объем 512 Кбайт. Разрешающая способность экрана 640 на 200. Сколько страниц экрана одновременно разместится в видеопамяти при палитре: а) из 8 цветов,  б) 16 цветов; в) 256 цветов?

  2. Сколько бит требуется, чтобы закодировать информацию о 130 оттенках?

  3. Подумайте, как уплотнить информацию о рисунке при его записи в файл, если известно, что: а) в рисунке одновременно содержится только 16 цветовых оттенков из 138 возможных; б) в рисунке присутствуют все 130 оттенков одновременно, но количество точек, закрашенных разными оттенками, сильно различаются.

  4. Найдите в сети Интернет информацию на тему «Цветовые модели HSB, RGB, CMYK» и создайте на эту тему презентацию. В ней отобразите положительные и отрицательные стороны каждой цветовой модели, принцип ее функционирования и применение.



Тема 3.1. Смысл энтропии Шеннона

В основанной американским ученым Клодом Шенноном математической теории информации под информацией понимались не любые сведения, а лишь те, которые снимают полностью или уменьшают существующую до их получения неопределенность (неизвестность). Каждому сигналу в теории Шеннона соответствует вероятность его появления (например, при передаче текста телеграммы вероятность появления буквы “Р” приблизительно равна 1/32). Чем меньше вероятность появления того или иного сигнала, тем больше информации он несет для потребителя. В обыденном понимании чем неожиданнее новость, тем больше ее информативность.

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

Информация по Шеннону Увеличение информации эквивалентно сокращению энтропии. Первичное и самое существенное в определении энтропии - логарифм числа возможных состояний или их вероятностей.

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

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

Формула Шеннона имеет следующий вид:

image002.gif

Знак минус в формуле не означает, что энтропия – отрицательная величина. Объясняется это тем, что pi1 по определению, а логарифм числа меньшего единицы - величина отрицательная.

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

Решение. Из десяти цифр четыре (2, 3, 5, 7) являются простыми, поэтому вероятность img337.pngизвлечь карточку с простой цифрой равна 0,4, а вероятность противоположного события img1082.png.

Воспользуемся формулой Шеннона

img1083.png.

Пример 2. Какую степень неопределенности содержит угадывание месяца рождения случайно встреченного человека?

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

img1084.png(бит).

Пример 3. В одной группе 6 студентов из 24 получили в сессию неудовлетворительную оценку, а в другой - 9 из 27. В каком случае сложнее предсказать успеваемость студента?

Решение. Используем формулу Шеннона



img1085.png



img1086.png



img287.png> img285.png, поэтому сложнее предсказать успеваемость студента во второй группе.

Вопросы и задания.

1. Каковы основные требования к функции меры неопределенности?

2. Формула Шеннона.

3. В чем различие формул Хартли и Шеннона?

4. Какие свойства энтропии вы знаете?

5. Основные единицы измерения энтропии и их связь.

6. Бит и другие его названия.

7. Какую степень неопределенности содержит угадывание дня рождения случайно встреченного человека?

8. В каком случае менее предсказуем исход: в том, когда подбрасываем монету, или в том, когда угадываем пол первого случайно встреченного человека?

9. Что более непредсказуемо:

а) исход подбрасывания двух игральных костей или

б) угадывание карты из колоды в 36 карт (32 карты)?

10. В одной группе 6 студентов из 20 получили в сессию неудовлетворительные оценки, а в другой - 8 из 24. В каком случае сложнее предсказать успевающего студента?

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

12. В одной подгруппе 3 из 10 студентов получили неудовлетворительную оценку по немецкому языку, а в другой - 4 из 12 по английскому. В каком случае сложнее предсказать успеваемость по иностранному языку двух случайно выбранных студентов одной подгруппы?

Тема 4.1. Сжатие и передача информации

Код Хаффмана

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

(1)

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


(2)

Ðèñóíîê 1

минимальна (|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. Вес узлов будем обозначать нижними индексами: A5, B3, C7.

  3. Составные узлы будем заключать в скобки: ((A5+B3)8+C7)15.

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

  1. A2B1C5D2E7F1G3H15

  2. A2C5D2E7G3H15 (F1+B1)2

  3. C5E7G3H15 (F1+B1)2 (A2+D2)4

  4. C5E7H15 (A2+D2)4 ((F1+B1)2+G3)5

  5. E7H15 ((F1+B1)2+G3)5 (C5+(A2+D2)4)9

  6. H15 (C5+(A2+D2)4)9 (((F1+B1)2+G3) 5+E7)12

  7. H15 ((C5+(A2+D2)4) 9+(((F1+B1)2+G3) 5+E7)12)21

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

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

ROOT

/\

0 1

/ \

/\ H

/ \

/ \

/ \

0 1

/ \

/ \

/ \

/ \

/\ /\

0 1 0 1

/ \ / \

C /\ /\ E

0 1 0 1

/ \ / \

A D /\ G

0 1

/ \

F B

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

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

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

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

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

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

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

Метод RLE.

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


Вопросы и задания

  1. Что такое код Хаффмана?

  2. Что называется деревом Хаффмана?

  3. Как происходит сжатие методом Хаффмана?

  4. Как происходит сжатие по методу RLE?

  5. Назовите расширения растровых графических изображений?

6. Выполните сжатие методом Хаффмана


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


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


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

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

ssssoooeeerroooaayyyyyddddoeuuuuuwwwwjjjorruuuuuuuuuuxxxkhhhhhhmmmmmmgggllllllljjjj


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

FFFFFFFFKKKKKSSSSUURERRRRRRRRRPPPPPPPPDDDDKKKKKKGLDDDDDDDDKKKKKKKKGGGGMGMMMM

8. Изучите алгоритм LZ78. Закодируйте информацию из прим. 6 с помощью этого алгоритма.

9. Изучите код Фано. Построить схему оптимального кодирования для алфавита с распределением вероятностей р=(0,2;0,2;0,19;0,12;0,11;0,09;0,09)


  1. Список рекомендуемой литературы


    1. Основы теории информации: учебное пособие / А.М. Маскаева - М.: ФОРУМ: ИНФРА-М, 2014. - 96 с.

    2. Е.В. Андреева, Л.Л. Босова, И.Н. Фалина. Математические основы информатики, М.:Бином, 2005. – 328

    3. http://www.iqlib.ru/book/preview/241110b984214e4193595815ad8b0983





Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 25.10.2016
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров147
Номер материала ДБ-288419
Получить свидетельство о публикации
Похожие материалы

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