Теоретические основы информатики

Теоретические основы информатики

Тема: Информатика и информация. Алфавитный подход к измерению информации

Сабитова Диляра Арифовна, преподаватель кафедры естественно-математического образования

ПЛАН ЛЕКЦИИ

• Информатика и информация
• Количество информации. Формула Хартли
• Формула Шеннона

Информатика

Информатика – это наука о способах получения, накоплении, хранении, преобразовании, передаче и использовании информации

Информатика

• Теоретическая информатика
• Кибернетика
• Вычислительная техника
• Программирование
• Искусственный интеллект
• Прикладная информатика

Информация

• Информация – это сведения, уменьшающие неопределённость нашего знания об окружающем нас мире, которые являются объектом хранения, преобразования, передачи и использования.
• Информация - сведения (сообщения, данные) независимо от формы их представления (Федеральный закон от 27.07.2006 N149-ФЗ «Об информации, информационных технологиях и о защите информации»).

Информация

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

Информация

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

Информация

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

Данные

• Данные - это зарегистрированные сигналы.
• Данные - это информация, представленная в виде, позволяющем запоминать, хранить, передавать или обрабатывать её с помощью технических средств.
• Данные – это информация об объекте или отношениях объектов, выраженная в знаковой форме.

Сигнал

Сигнал – это изменяющийся во времени физический процесс. К регистрации сигналов можно отнести:

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

Процесс передачи данных

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

• понятность — информация выражена языком, понятным получателю;
• достоверность — информация отражает истинное положение дел;
• полнота — информация достаточна для принятия решения;
• актуальность — информация важна и существенна в настоящее время;
• ценность (полезность) — определяется задачами, которые можно решить с её помощью

Информацию, зафиксированную каким-либо способом, называют информационным объектом

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

Компьютер

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

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

Представление информации

• Аналоговая форма
• Дискретная форма

Представление информации

Язык — знаковый способ представления информации

• Естественные языки
• Формальные языки

Кодирование информации

Неравномерные коды

Префиксные коды

Префиксный код — это код со словами переменной длины, в котором ни одно кодовое слово не является началом другого кодового слова.

Пример: 0, 10, 11

100111011010

10 0 11 10 11 0 10

Непрефиксные коды

Набор 0, 10, 100, 11 образует непрефиксный код

Равномерные коды

Если мощность кодового алфавита равна М , а длина кода — I , можно составить

N = М  I

различных кодовых слов.

M = 2: N = 2 I

Примеры решения заданий

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

Решение .

Количество комбинаций можно считать символами исходного  алфавита. Тогда мощность исходного алфавита N = 18.

Мощность двоичного кодового алфавита M = 2. Известно, что N = 2 I

Определим длину двоичного кода I = log 2 N = log 2 18. Округлим полученный результат до ближайшего большего целого, получим

I = 5.

Ответ: 5

Примеры решения заданий

Пример 1.2 . Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трёх состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?

Решение .

Мощность кодового алфавита M = 3 (три состояния лампочек), мощность исходного алфавита N = 18 (количество различных сигналов). Известно, что N = М  I  = 3  I . Определим длину кодового слова по формуле log 3 N = log 3 18. Округлим полученный результат до ближайшего большего целого (2

Ответ: 3.

Примеры решения заданий

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

Решение .

Мощность кодового алфавита (количество различных видов флагов) M = 3, длина кодового слова равна 5 (количество сигнальных флагов). Количество различных сигналов определим по формуле N = М I  = 3 5 = 243. Эту задачу можно решить простыми рассуждениями. Так как имеем неограниченное количество флагов трёх видов, то каждый флаг в последовательности из пяти сигнальных флагов можно выбрать тремя способами.

Получаем 3 ⋅ 3 ⋅ 3  ⋅ 3 ⋅ 3 = 243.

Ответ: 243.

Количество информации

Содержательный (вероятностный)

Алфавитный

Вероятностный подход

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

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

Количество информации. Формула Хартли

Р. Хартли в 1928 г. сформулировал законы , которым должно подчиняться количество информации:

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

N2 = Info(N1 ) Info(N2 ) (монотонность).   3. Info(N1) + Info(N2 ) + … + Info(Nk) = Info (N1  + N2 + … + Nk). I = log b N " width="640"

Количество информации. Формула Хартли

1. Info(1) = 0. 

2. N1 N2 = Info(N1 ) Info(N2 ) (монотонность).  

3. Info(N1) + Info(N2 ) + … + Info(Nk) = Info (N1  + N2 + … + Nk).

I = log b N

Количество информации

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

Если возможное количество равновероятных исходов опыта (событий) равно N, то вероятность наступления одного из них определяется как p = 1/N , и формула Хартли имеет вид:

I = log 2 1/p = – log 2 p

Количество информации

Пример 1.6. Задание с кратким ответом

Сколько бит информации нужно получить, чтобы отгадать одно задуманное целое число из 32 возможных чисел в интервале [0;31]?

По формуле Хартли: I = log 2 32 = 5 или 2 I = 32.

Количество информации

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

Количество информации. Формула Шеннона

В общем случае среднее количество информации, получаемой при неравновероятных событиях, определяется по формуле Шеннона:

где p i — вероятность наступления i-го события

Количество информации. Формула Шеннона

Самый простой код — равномерный:

А — 00, B — 01, C — 10, D — 11.

Для этого кода требуется два двоичных знака (2 бита) на символ сообщения.

Если же учесть вероятность появления символа, можно построить следующий (префиксный) код:

А — 0, B — 10, C — 110, D — 111.

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

1/2 ⋅ 1 + 1/4 ⋅ 2 + 1/8 ∙ 3 + 1/8 ∙ 3 = 1,75 бит

Алфавитный подход

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

Алфавитный подход

Количество информации I , которое несёт каждый символ алфавита, вычисляется по формуле:

I = log 2 N,

где N — мощность исходного алфавита. Величину I называют информационным весом символа (исходного алфавита)

Количество информации, содержащееся в символьном сообщении, вычисляется по формуле:

V = К ∙ I = К ∙ log 2 N,

где К — количество символов в тексте исходного сообщения (длина сообщения).

Примеры решения заданий

Пример 1.7. Задание с кратким ответом Сколько килобайтов информации содержит сообщение объёмом 2 16 бит? В ответе укажите одно число. 

Решение .

Воспользуемся приведённой выше таблицей:

1 Кбайт == 2 13 бит, значит, 2 16 бит = 2 16–13 Кбайт = 2 3 Кбайт = 8 Кбайт.

Ответ: 8.

Примеры решения заданий

Пример 1.8. Сколько  информации  содержит  сообщение  о  том,  что  на  экзамене  ученик  вытянул  билет  № 14,  а  всего  экзаменационных  билетов было  32? Решение :  Выбран один из 32 билетов, т. е. произошло одно из 32 равновероятных  событий.  По  формуле  Хартли  количество  информации равно:

I =  log 2 32 = 5 бит

Ответ: 5.

Примеры решения заданий

Пример 1.9. При  угадывании  целого  числа  из  интервала  от  10  до  N   получено 7  бит информации. Укажите максимально возможное значение  N . Решение :  В указанном интервале находится ( N  – 10 + 1) целых чисел.  По формуле Хартли количество информации равно: I =  log 2 ( N  – 9) = 7 бит. Тогда  N  – 9 = 2 7  = 128,  N  = 128 + 9 = 137. Ответ: 137

Примеры решения заданий

Пример 1.10. В корзине лежат 8 подберёзовиков и 24 подосиновика. Какое количество информации содержится в сообщении о том, что взятый наугад из корзины гриб оказался подберёзовиком?

Решение :  Общее количество грибов в корзине 8 + 24 = 32. Количество  информации, полученное в сообщении о том, что вынут подберёзовик, равно 

I = – log2(8/32) = 2 бит.

Ответ: 2.

Примеры решения заданий

Пример 1.11. В течение полугодия ученик получал оценки 2, 3, 4 и 5, всего он получил 64 оценки. Сообщение о том, что ученик получил оценку 4, несёт 2 бит информации. Сколько четвёрок получил ученик за полугодие? Решение :  Пусть  Х — количество четвёрок, полученных учеником. Тогда количество информации в сообщении о полученной четвёрке равно

I =  – log 2 (Х/64) = 2 бит. 

Отсюда 64/Х = 4, Х = 64/4 = 16. Ответ:  16