1 Информация и информационные процессы § 1. Количество информации § 2. Передача данных § 3. Сжатие данных § 4. Информация и управление § 5. Информационное общество
§ 1. Количество информации 2
3 I – количество информации в битах N – количество вариантов Ральф Хартли Пример: В аэропорту стоит 10 самолетов, из них один летит в Санкт-Петербург. Оценить количество информации в сообщении «В Санкт-Петербург летит второй самолет»? бита
4 N – мощность алфавита Информационный объём символа: сообщения длиной L : Пример : сообщение длиной 100 символов закодировано с помощью алфавита из 50 знаков. бита бита вверх до целого числа 6 битов 6 00 битов
5 Оцените теоретическое количество информации в сообщении «Приеду в четверг». Используемый алфавит состоит из заглавных и строчных русских букв и пробела. Каков будет фактический объем этого же сообщения, если при передаче каждый символ колируется минимально возможным целым числом битов?
6 N – мощность алфавита L – длина сообщения Q – количество различных сообщений алфавит: А, Б, В, Г А, Б, В, Г А, Б, В, Г для каждого варианта А, Б, В, Г всего: 4 всего: 4 4 = 4 2 = 16
7 Некоторое устройство имеет специальную кнопку включения/выключения, а выбор режима работы осуществляется установкой ручек двух тумблеров, каждая из которых может находиться в одном из пяти положений. Сколько различных режимов работы может иметь устройство? Выключенное состояние режимом работы не считать. В некоторой стране проживает 1000 человек. Индивидуальные номера налогоплательщиков - физических лиц в этой стране содержат только цифры 0, 1, 2 и 3. Каково минимальное количество разрядов в ИНН в этой стране, если различные между собой номера имеют абсолютно все жители?
8 3. Индивидуальные номера страховых медицинских свидетельств жителей в некоторой стране содержат только цифры 1, 3, 5, 7 и содержат одинаковое количество цифр, а именно 3 цифры. Известно, что медицинскую страховку имеют абсолютно все жители и номера всех свидетельств различны. Каково максимально возможное количество жителей в стране? 4. В велокроссе участвуют 108 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого из спортсменов. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли 96 велосипедистов? (Ответ дайте в байтах.)
9 0,175 О 0,090 Е 0,072 А 0,063 И 0,062 Т 0,053 Н 0,052 С 0,045 р 0,040 В 0,038 Л 0,035 К 0,028 М 0,026 Д 0,025 П 0,023 У 0,021 Я 0,018 Ы 0,017 З 0,016 Ь 0,015 Б 0,014 Г 0,013 Ч 0,012 Й 0,010 Х 0,009 Ж 0,007 Ю 0,006 Ш 0,005 Ц 0,004 Щ 0,003 Э 0,002 Ф 0,001 Доля символов в русских текстах: из 1000 символов около 175 пробелов вероятность p появления символа
10 Вероятность события – число от 0 до 1, показывающее, как часто случается это событие в большой серии одинаковых опытов. событие никогда не происходит (нет неопределенности) событие происходит в половине случаев ( есть неопределенность ) событие происходит всегда (нет неопределенности) x 2 0 x 2 < 0
11 N – количество испытаний m – сколько раз произошло событие ровно 2: чётное: меньше 3 : 2 и 2: 2 чётных: оба меньше 3 :
12 …АААААААААААААААААА получили букву « А »: … B АААААААААААААААААА получили букву « В »: Чем более неожиданно событие, тем больше получено информации. В 10 опытах будет получено в 10 раз больше информации, чем в одном ( аддитивность ). Определили свойства количества информации! !
13 при K = 1 информация в битах Если событие имеет вероятность p, то количество информации в битах, полученное в сообщении об этом событии, равно
14 Аддитивность : по 8 шариков разного цвета всего 8 8 = 64 варианта бита битов битов Аддитивность выполняется! !
15 N равновероятных событий совпадает с формулой Хартли Если вероятности разные: « Васе достался зелёный шарик ».
16 Количество полученной информации равно уменьшению неопределенности. I = H = H нач – H кон Как вычислить H ? ? Неопределённость знаний об источнике данных ( N событий, вероятности p i ): Клод Шеннон информационная энтропия
17 « Идёт ли сейчас снег? » (1 – да, 2 – нет) зимой : Как вычислить p 2 ? ? Сумма вероятностей всех событий, составляющих полную систему, равна 1! ! бит летом : бит
18 Система двух событий: Неопределенность максимальна, когда все события равновероятны. 0 1 0,5 1 0,5 H p 1 совпадает с формулой Хартли!
§ 2. Передача данных 19
20 Скорость передачи данных – это количество битов (байтов, Кбайт и т.д.), которое передается по каналу связи за единицу времени (например, за 1 с). бит / с = 1 bps ( bits per second ) 1 кбит / с = 1000 бит / с 1 Мбит / с = 10 6 бит / с 1 Гбит / с = 10 9 бит / с Объём переданных данных: скорость передачи время v = 512000 бит / с, t = 1 мин I = v t = 512000 бит / с 60 с = 30 720 000 битов = 3 840 000 байтов = 3075 Кбайт.
21 Бит чётности : 00 01 10 11 00 0 01 1 10 1 11 0 теперь число единиц в каждом блоке чётное Если в принятом блоке нечётное число «1» – ошибка ! принято: 010 110 000 111 000 Можно ли исправить ? ? Для файлов – контрольные суммы (хэш) : CRC = Cyclic Redundancy Code MD5, SHA-1 Верно ли переданы данные ? ? 10010
22 1 11 0 00 0 00 1 11 0 00 – утроение каждого бита принято: 010 111000 101 000 исправлено: 000 111000 111 000 10010 Обнаруживает 1 или 2 ошибки, исправляет 1 ошибку! ! Помехоустойчивый код – это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.
23 Расстояние Хэмминга – это количество позиций, в которых отличаются два закодированных сообщения одинаковой длины. d ( 0 0 1, 1 0 0 ) = 2 d (00 0, 1 11 ) = ? 3 Обнаруживает 1 или 2 ошибки, исправляет 1 ошибку! ! Исправление r ошибок: d 2 r + 1
24 000 000 001 111 010 011 011 100 100 101 101 010 110 110 111 001 d min = 3 r = 1 d (000000, x ) = ? 001111 4 010011 3 011100 3 100101 3 101010 3 110110 4 111001 4 Исправление ошибки принято: 101110 Недопустимый код! ! ближайший допустимый код: 101010
25 1 2 3 4 5 6 7 0 1 1 1 1 0 0 4 полезных бита, 3 контрольных избыточность 3 /4 =75% 3 = 1 + 2 5 = 1 + 4 6 = 2 + 4 7 = 1 + 2 + 4 бит 1: (1 + 1 + 0) mod 2 = 0 бит 2 : (1 + 0 + 0) mod 2 = 1 бит 4 : (1 + 0 + 0) mod 2 = 1 d min = 3 r = 1
26 1 2 3 4 5 6 7 0 1 1 1 1 1 0 бит 1: (1 + 1 + 0) mod 2 = 0 бит 2 : (1 + 1 + 0) mod 2 = 0 бит 4 : (1 + 1 + 0) mod 2 = 0 Контрольные биты: Номер ошибочного бита: 2 + 4 = 6 0 1 1 1 1 0 0 1 1 0 0
27 Контрольные биты: 1, 2, 4, 8, 16, …, 2 k Исправляется только 1 ошибка в блоке! ! Длина кодовых слов, бит Число контрольных битов Избыточность 4 3 75% 11 4 36% 27 5 19% 58 6 10% 248 8 3% 1014 10 1%
§ 3. Сжатие данных 28
29 Алфавит: A, B, C, Сообщение: А B А C А B А B А 8 0 битов в 8-битной кодировке! ! A 00 B 01 C 1 0 1 1 А B А C А B А B А 00 01 00 11 10 00 01 00 01 00 20 битов Как раскодировать? ? Словарь: 00 01 10 11 00000100 2 01000001 2 01000010 2 01000011 2 00100000 2 4 символа A ( код 65 ) B ( код 6 6) C ( код 67 ) пробел ( код 32)
30 Сообщение: 10240 символов Алфавит: A, B, C, Словарь: 5 байтов Длина кода: 10240 × 2 = 20480 битов = 2560 байтов Длина сжатого сообщения: 5 + 2560 = 2565 байтов Коэффициент сжатия – это отношение размеров исходного и сжатого файлов.
31 Сжатие без потерь – это такое уменьшение объема закодированных данных, при котором можно восстановить их исходный вид из кода без искажений. За счёт чего сжимается сообщение? ? В данных должна быть избыточность! ! используются только 4 символа из 256
32 RLE ( англ. Run Length Encoding, кодирование цепочек одинаковых символов ) A A … A B B … B 100 100 200 байтов Файл qq.txt Файл qq.rle ( сжатый ) 100 A 100 B 4 байта В чем состоит избыточность? ? сжатие в 5 0 раз! Сжатие с потерями или без ? ? Что в худшем случае ? ?
33 1 0001111 2 11000000 2 0 0000010 2 11000001 2 11000010 2 повтор 15 A ( код 192) 2 Б ( код 193) В ( код 194) управляющие байты ААААААААААААААА БВ Распаковка: 15 2 Применение: сжатие рисунков *.bmp ( с палитрой ) один из этапов сжатия рисунков *.jpg
34 Идея: кодировать часто встречающиеся символы более короткими кодовыми словами. Азбука Морзе: А И • • • – – – корень Н М Т Е Е • – Т И • – А • • Н – М • – – Проблема: разделить последовательность на кодовые слова! ! • • И ЕЕ Можно ли обойтись без разделителя? ?
35 Префиксный код – это код, в котором ни одно кодовое слово не является началом другого кодового слова (условие Фано ). А И • • • – – – корень Н М Т Е Е • – Т И • – А • • Н – М • – – Это не префиксный код! ! Проблема: как построить префиксный код? ! не все символы в листьях!
36 Алфавит: О, Е, Н, Т, Количество символов в сообщении: 179 О Н Е Т 89 72 53 5 0 На 2 группы с примерно равным числом символов: 179 О Н Е Т 89 72 53 5 0 229 2 14 начинаются с 0 начинаются с 1 00 Т 0 1 О 10 Н Е 72 53 начинаются с 1 1 Н Е 110 111
37 Т О Е Н 0 0 0 0 1 1 1 1 корень Это префиксный код ( все символы в листьях дерева ) ! ! Декодирование : 01100110001101111001 01 10 01 10 0 0 110 11 1 10 01 Т O Т O Е Н О Т
38 учитывается частота символов не нужен символ-разделитель код префиксный – можно декодировать по мере поступления данных нужно заранее знать частоты символов код неоптимален при ошибке в передаче сложно восстановить « хвост » не учитывает повторяющиеся последовательности символов
39 Дэвид Хаффман 179 Е Т Н О 72 53 50 89 По увеличению частоты: 179 Е Т Н О 72 89 103 179 Е О 1 61 Т Н 103
40 179 Е О Т Н 264 Т Н Е О 0 1 0 1 1 1 0 0 0 Т 10 0 Н 1 01 Код Хаффмана : Е 1 10 О 1 11
41 Количество символов в сообщении: 179 О Н Е Т 89 72 53 5 0 Равномерное кодирование (8 -битный код): (179 + 89 + 72 + 53 + 50) 8 = 3544 бита Равномерное кодирование (3 -битный код): (179 + 89 + 72 + 53 + 50) 3 = 1329 битов + словарь! В чём избыточность? ?
42 Количество символов в сообщении: 179 О Н Е Т 89 72 53 5 0 Код Шеннона-Фано: 00 О 10 Е 110 Н Т 111 01 ( 179 + 89 + 50) 2 + ( 7 2 + 53 ) 3 = 1 011 битов Код Хаффмана: 0 О 1 11 Е 1 10 Н Т 1 01 1 00 179 + ( 89 + 72 + 53 + 50) 3 = 971 бит Оптимален! !
43 код оптимальный среди алфавитных кодов нужно заранее знать частоты символов при ошибке в передаче сложно восстановить « хвост » не учитывает повторяющиеся последовательности символов
44 1977: А. Лемпел и Я. Зив, 1984: Т. Велч Идеи: кодировать не отдельные символы, а блоки последовательностям символов присваиваются числовые коды новая цепочка занесение в словарь с новым кодом словарь строится по мере получения данных не нужны частоты символов за один проход! Применение: сжатие рисунков *.gif, *.tif сжатие документов *.pdf
45 Сжатие с потерями – это такое уменьшение объема закодированных данных, при которых распакованный файл может отличаться от оригинала. Применение: сжатие рисунков *.jpg, *.jpeg сжатие звука *.mp3, *.aac, *.ogg, … сжатие видео *.mpg, *.wmv, *.mov, … Идея: « отбросить » часть данных, которые не влияют на восприятие информации человеком (доп. размытие фотографий, частоты выше 20 кГц, …)
46 8 битов на пиксель (256 цветов) 4 бита на пиксель (16 цветов ) 2 бита на пиксель (4 цвета) размер качество
47 RGB Y Cb Cr яркость «синева» «краснота» Y = 0,299 R + 0,587 G + 0,114 B Cb = 128 – 0,1687 R – 0,3313 G + 0,5 B Cr = 128 + 0,5 R – 0,4187 G – 0,0813 B глаз чувствительнее к зелёному! Что для чёрно-белого (серого)? ? Cb = Cr = 128
48 Идея: глаз наиболее чувствителен к яркости Y 1, Cb 1, Cr 1 Y 2, Cb 2, Cr 2 Y 3, Cb 3, Cr 3 Y 4, Cb 4, Cr 4 12 чисел например: Cb = Cb 1 + Cb 2 + Cb 3 + Cb 4 4 Cr = Cr 1 + Cr 2 + Cr 3 + Cr 4 4 Y 1, Y 2, Y 3, Y 4, Cb, Cr 6 чисел + дискретное косинусное преобразование, алгоритмы RLE и Хаффмана потери!
49 качество 100 (8400 байтов) качество 50 (3165 байтов) качество 0 (1757 байтов) качество 0 (фрагмент) 40 3 0 20 1 0 0 BMP BMP( RLE ) GIF PNG JPEG (1 0 0) JPEG (50) JPEG (0) V, Кбайт Плавные переходы! ! Артефакты – заметные искажения из-за сжатия с потерями
50 Большие области одного цвета! Чёткие границы! ! 12 0 10 0 8 0 40 0 BMP BMP( RLE ) GIF PNG JPEG (1 0 0) JPEG (50) JPEG (0) 6 0 2 0 V, Кбайт Что особенного? ? с потерями! без потерь!
51 MP3 = MPEG-1 Layer 3, кодирование восприятия Битрейт – это число бит, используемых для кодирования 1 секунды звука. MP3: от 8 до 320 кбит/ c Без сжатия на CD (1 сек, 44 кГц, 16 бит, стерео): 2 88000 = 176 000 байт = 1 408000 бит = 1408 кбит C жатие MP3 ( 256 кбит / с):
52 видео = изображения + звук Кодек (кодировщик / декодировщик ) – это программа для сжатия данных и восстановления сжатых данных. MJPEG, MPEG-4, DivX, Xvid, H.264, … Артефакты – заметные искажения из-за сжатия с потерями
53 Сжатие уменьшает избыточность данных! ! Хорошо сжимаются : тексты ( *.txt ) документы ( *.doc ) несжатые рисунки ( *.bmp ) несжатый звук ( *.wav ) несжатое видео ( *. avi ) Плохо сжимаются : случайные данные сжатые данные в архивах ( *.zip, *.rar, *. 7 z ) сжатые рисунки ( *.jpg, *.gif, *.png ) сжатый звук ( *.mp3, *.aac ) сжатое видео ( *.mpg, *.mp4, *.mov ) Нужно ли стремиться к полному удалению избыточности? ?
§ 4. Информация и управление 54
55 Норберт Винер Кибернетика – это наука, изучающая общие закономерности процессов управления и передачи информации в машинах, живых организмах и обществе. Идеи: управление в любых системах подчиняется одним и тем же законам управление связано с обменом информацией
56 Система – это группа объектов и связей между ними, выделенных из среды и рассматриваемых как одно целое. Примеры: общество семья экологическая система компьютер файловая система операционная система А Б В Г среда Системный эффект : свойства системы нельзя свести к «сумме» свойств ее компонентов. самолёт летает!
57 Свойства системы: компоненты + связи (алмаз, графит) Подсистема : компонент-система. Цель работы системы определяется надсистемой! ! А Б В Е Ж Г Д S S 1 S 2 Системный анализ : изучение сложных систем на основе теории управления и теории информации. подсистема элемент Надсистема : система более высокого уровня.
58 регулятор объект цель среда управление Разомкнутая система – регулятор не получает информации о состоянии объекта ( программное управление ). Примеры: водитель с завязанными глазами начальник, не проверяющий рабочих информационное табло на вокзале светофор простота – не нужно датчиков нужна точная модель объекта нельзя учесть влияние среды Неизвестно, достигнута ли цель! !
59 Замкнутая система – регулятор получает информации о состоянии объекта по каналу обратной связи. регулятор объект цель среда управление датчики обратная связь (ОС) сравнение с целью! усложнение системы (датчики) модель объекта может быть неточной можно учесть влияние среды Отрицательная ОС – регулятор уменьшает разницу между целью и состоянием объекта.
60 Автоматические – работают без участия человека. Автоматизированные – собирают и обрабатывают информацию, а решения принимает человек. Адаптивные – «подстраиваются» под изменение внешних условия или свойств объекта.
§ 5. Информационное общество 61
62 Прогресс в обработке информации : письменность (около 3000 лет до н.э., Египет) книгопечатание ( X век – Китай, XV век – Европа) средства связи (телеграф, телефон, радио, телевидение; конец XIX – начало XX века); компьютеры (вторая половина XX века). Информационное общество – это такая ступень развития цивилизации, на которой главными продуктами производства становятся информация и знания.
63 Информатизация – переход к информационному обществу: внедрение информационных технологий во все сферы жизни развитие компьютерных сетей, сотовой связи и т.п. необходимость компьютерной грамотности для всех свобода доступа к информации; доступность образования, в том числе дистанционного (через Интернет) изменение структуры экономики изменение уклада жизни людей
64 Негативные последствия : усиление влияния СМИ разрушается частная жизнь людей сложно выбрать качественные и достоверные данные личное общение людей заменяется общением в Интернете людям старшего поколения очень сложно приспособиться
65 Ресурсы – условия, позволяющие после некоторой «обработки» получить желаемый результат. Информационные ресурсы – документы в библиотеках, архивах, банках данных, информационных системах. товар! Информационные услуги : поиск и подбор информации подбор персонала (кадровые агентства) обучение (учебные центры) рекламные агентства консультации, услуги по оптимизации бизнеса разработка программ и веб-сайтов
66 Технология – это способ сделать «продукт» из исходных материалов (с гарантированным результатом!). Новые информационные технологии – это технологии, связанные с использованием компьютеров для хранения, защиты, обработки и передачи информации. подготовка документов в электронном виде поиск информации телекоммуникации (сети, Интернет, e-mail ) автоматизированные системы управления (АСУ) системы автоматизированного проектирования (САПР) геоинформационные системы обучение (электронные учебники, компьютерные тренажеры, дистанционное обучение).
67 менеджер администратор сервер, база данных производство (кухня) рабочие места официантов, барменов, кассиров Ресторан+
68 … технологическими процессами (АСУ ТП) рабочее место оператора блок сбора информации датчики блок управления блок сбора информации датчики блок управления GSM модем GSM модем локальная сеть
69 САПР – системы автоматизированного проектирования
70 Измерение расстояния Проложить маршрут Панорамы улиц
71 видеолекции самостоятельная работа письменные задания работа с тьютором (наставником) консультации по Интернету Интернет тьютор
72 www.intuit.ru www.edx.org www.udacity.com www.coursera.org Гарвардский университет Массачусетский технологический институт Стэнфорский университет Университет Виргиния 33 университета www.khanacademy.org Академия Хана
73
74 Для общества – способность общества эффективно использовать информационные ресурсы и средства обмена информацией применять передовые достижения в области информационных технологий Для человека – умение формулировать потребность в информации находить нужную информацию отбирать и анализировать информацию представлять информацию в разных видах; обрабатывать информацию использовать информацию для принятия решений Нормы права и морали действуют по-прежнему! !
75 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
76 www.newbeanbag.ru compression.ru maps.yandex.ru ixbt.com www.dinamika-avia.ru www.transas.ru crazypiter.ru www.fotosearch.com www.notebookcheck.net www.energy2.ru www.wlangdesign.com www.1himplast.ru www.applecad.com gprs-modem.ru en.wikipedia.org nivo.co.za иллюстрации художников издательства «Бином» авторские материалы
