Меры информации Информатика. 2 Информация Информация (лат. informatio разъяснение, пояснение) - совокупность сведений (данных), которая воспринимается. - презентация

1 Меры информации Информатика

2 2 Информация Информация (лат. informatio разъяснение, пояснение) - совокупность сведений (данных), которая воспринимается из окружающей среды (входная информация), выдается в окружающую среду (исходная информация) или сохраняется внутри определенной системы. Свойства информации: объективность и субъективность; полнота; достоверность; адекватность; доступность; актуальность. Материальный носитель - материальный объект или среда, служащая для передачи информации. Изменение характеристики носителя называется сигналом, а значение этой характеристики параметром сигнала.

3 3 Объекты информации Источник информации Получатель информации Сообщение Канал связи Источник информации – это субъект или объект, порождающий информацию и представляющий ее в виде сообщения. Получатель информации - это субъект или объект, принимающий сообщение и способный правильно его интерпретировать. Сигнал – материальный носитель, который фиксирует информацию для переноса ее от источника к потребителю.

4 4 Наука исследования свойств знаков и систем Семиотика (греч. semeion – знак, признак) - наука, занимающаяся исследованием свойств знаков и знаковых систем. Семиотика выделяет следующие уровни передачи информации: Синтаксический, рассматриваются внутренние свойства сообщений. Семантический, анализируется смысловое содержание сообщения, его отношение к источнику информации Прагматический, рассматривается потребительское содержание сообщения, его отношение к получателю.

5 5 Классификация мер информации Синтаксическая мера информации Семантическая мера информации Прагматическая мера информации

6 6 На синтаксическом уровне для измерения информации вводятся два параметра Синтаксическая мера информации Объем информации (объемный подход) Количество информации (вероятностный подход)

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

8 8 Единицы измерения информации 1 бит = кол-во двоичных цифр (0 и 1) Пример: код имеет объем данных V= 8 бит 1 байт = 8 бит 1 Кбайт = 1024 байт = 2 10 байт 1 Мбайт = 1024 Кбайт = 2 20 байт = байт; 1 Гбайт = 1024 Мбайт = 2 30 байт = байт; 1 Тбайт = 1024 Гбайт = 2 40 байт = байт.

9 9 Вероятностный подход События, о которых нельзя сказать произойдут они или нет, пока не будет осуществлен эксперимент, называются случайными. Отдельный повтор случайного события называется опытом, а интересующий нас исход этого опыта – благоприятным. Если N – общее число опытов, а N А - количество благоприятных исходов случайного события А, то отношение N A / N, называется относительной частотой появления события А. В разных сериях опытов частота может быть различна, но при увеличении количества опытов относительная частота все меньше отклоняется от некоторой константы, ее наличие называется статической устойчивостью частот. Если все исходы опыта конечны и равновозможные, то их вероятность равна где n - число исходов.

10 10 Энтропия (часть1) Энтропия – численная мера измеряющая неопределенность. Некоторые свойства функции: 1.f (1)=0, так как при n=1 исход не является случайным и неопределенность отсутствует. 2.f (n) возрастает с ростом n, чем больше возможных исходов, тем труднее предсказать результат. 3.Если a и b два независимых опыта с количеством равновероятных исходов n a и n b, то мера их суммарной неопределенности равна сумме мер неопределенности каждого из опытов: За количество информации - разность неопределенностей ДО иПОСЛЕ опыта: 10

11 11 общее число исходов М – число попыток (пример: Х = 6 2 = 36) Энтропия системы из М бросаний кости будет в M раз больше, чем энтропия системы однократного бросания кости - принцип аддитивности энтропии: Энтропия (часть 2) 11

12 12 Обозначим через K Получим f(X) = K lnX или H = K lnX, таким образом получим формулу Хартли для равновозможных исходов Формула Шеннона для неравновозможных исходов Формула Хартли и Шеннона 12

13 13 Количество информации (в битах), заключенное в двоичном слове, равно числу двоичных знаков в нем. Энтропия (часть 3) Информация – это содержание сообщения, понижающего неопределенность некоторого опыта с неоднозначным исходом; убыль связанной с ним энтропии является количественной мерой информации.

14 14 Семантическая мера информации Тезаурус это совокупность сведений, которыми располагает пользователь или система. Зависимость количества семантической информации, воспринимаемой потребителем, от его тезауруса. при Sp0 пользователь не воспринимает, не понимает поступающую информацию; при Sp пользователь все знает, и поступающая информация ему не нужна.

15 15 Прагматическая мера информации Эта мера определяет полезность информации (ценность) для достижения пользователем поставленной цели. Эта мера также величина относительная, обусловленная особенностями использования этой информации в той или иной системе. Ценность информации целесообразно измерять в тех же самых единицах (или близких к ним), в которых измеряется целевая функция. Целевая функция - есть математическое выражение некоторого критерия качества одного объекта (решения, процесса и т.д.) в сравнении с другим.

16 Кодирование информации. Информатика

17 17 Передатчик Приемник Помехи Кодирующие устройство Декодирующие устройство Источник Получатель Схема передачи информации

18 18 Абстрактный алфавит Алфавит - множество знаков, в котором определен их порядок (общеизвестен порядок знаков в русском алфавите: А, Б,..., Я) 1.Алфавит прописных русских букв 2.Алфавит Морзе 3.Алфавит клавиатурных символов ПЭВМ IBM (русифицированная клавиатура) 4.Алфавит знаков правильной шестигранной игральной кости 5.Алфавит арабских цифр 6.Алфавит шестнадцатиричных цифр 7.Алфавит двоичных цифр 8.Двоичный алфавит «точка, «тире» 9.Двоичный алфавит «плюс», «минус» 10.Алфавит прописных латинских букв 11.Алфавит римской системы счисления 12.Алфавит языка блок-схем изображения алгоритмов 13.Алфавит языка программирования

19 19 Кодирование информации. Источник представляет сообщение в алфавите, который называется первичным, далее это сообщение попадает в устройство, преобразующее и представляющее его во вторичном алфавите. Код – правило, описывающее соответствие знаков (или их сочетаний) первичного алфавита знаком (их сочетаниями) вторичного алфавита. Кодирование – перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов. Декодирование – операция обратная кодированию. Кодер – устройство, обеспечивающее выполнение операции кодирования. Декодер – устройство, производящее декодирование. Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечит возврат к исходной информации без каких-либо ее потерь.

20 20 Математическая постановка задачи кодирования А - первичный алфавит. Состоит из N знаков со средней информацией на знак I А. В - вторичный алфавит из М знаков со средней информацией на знак I В. Сообщение в первичном алфавите содержит n знаков, а закодированное – m знаков. I s (A)-информация в исходном сообщении, I f (B)-информация в закодированном сообщении.

21 21 I S (A) I f (B) – условие обратимости кодирования, т.е не исчезновения информации. n* I А m* I B (заменили произведением числа знаков на среднее информационное содержание знака). m/n – характеризует среднее число знаков вторичного алфавита, который используется для кодирования одного знака первичного. Обозначим его К (А, В) К (А, В) I (A) / I (B) Обычно К (А, В) >1 К min (А, В)= I (A) / I (B) – минимальная длинна кода Математическая постановка задачи кодирования

22 22 Первая теорема Шеннона Примером избыточности может служить предложение «в словох всо глосноо зомононо боквой о» Существует возможность создания системы эффективного кодирования дискретных сообщений, у которой среднее число двоичных символов на один символ сообщения асимптотически стремится к энтропии источника сообщений. Х = {xi } - кодирующее устройство – В Требуется оценить минимальную среднюю длину кодовой комбинации. Шенноном была рассмотрена ситуация, когда при кодировании сообщения в первичном алфавите учитывается различная вероятность появления знаков, а также равная вероятность появления знаков вторичного алфавита. Тогда: где I (A) - средняя информация на знак первичного алфавита.

23 23 Вторая теорема Шеннона При наличии помех в канале всегда можно найти такую систему кодирования, при которой сообщения будут переданы с заданной достоверностью. При наличии ограничения пропускная способность канала должна превышать производительность источника сообщений. 1.Первоначально последовательность Х = {xi} кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех). 2.Затем в последовательность из В длины n вводится r символов и по каналу передается новая последовательность из n + r символов. Число возможных последовательностей длины n + r больше числа возможных последовательностей длины n. Множество всех последовательностей длины n + r может быть разбито на n подмножеств, каждому из которых сопоставлена одна из последовательностей длины n. При наличии помехи на последовательность из n + r символов выводит ее из соответствующего подмножества с вероятностью сколь угодно малой. Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины n + r, и тем самым восстановить исходную последовательность длины n. 23

24 24 Вторая теорема Шеннона Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины п + r, и тем самым восстановить исходную последовательность длины п. Эта теорема не дает конкретного метода построения кода, но указывает на пределы достижимого в создании помехоустойчивых кодов, стимулирует поиск новых путей решения этой проблемы. 1.Способ кодирования только устанавливает факт искажения сообщения, что позволяет потребовать повторную передачу. 2.Используемый код находит и автоматически исправляет ошибку передачи.

25 25 Равномерное алфавитное кодирование. Представление чисел в компьютере 1.Компьютерный алфавит С включает буквы латинского алфавита – 52 шт. 2.Букв русского (прописные и строчные) – 66 шт. 3.Цифры 0…9 – 10 шт. 4.Знаки математических операций, препинания, спецсимволы – 20 штук Итого: 148

26 26 К (С, 2) log ,21, так как длина кода – целое число, следовательно, К (С,2) = 8бит = 1байт. Именно такой способ кодирования принят в компьютерных системах. Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении. Это объемный способ измерения информации. Присвоение символу конкретного двоичного кода фиксируется в кодовой таблице, где устанавливается соответствие между символами и их порядковыми номерами.

27 27 Таблицы кодировки Таблица, в которой устанавливается однозначное соответствие между символами и их порядковыми номерами, называется таблицей кодировки. Для разных типов ЭВМ используют различные таблицы кодировки: ANSI - (American National Standards Institute) ASCII - (American Standard Cod for Information Interchange)

28 28 Таблица кодировки ASCII

29 29 Код обмена информации ASCII Первоначально – 7 бит N=2 7 =128 символов 0…31- всевозможные управляющие символы 32…127 – видимые на экране символы. Сейчас – 8 бит N=2 8 =256 символов 128…255- национальные алфавиты,псевдографика = буква А = 65

30 30 Системы кодирования КОИ-7 Windows-1251 КОИ-8 ISO Unicode