Слайд 1Информация и информационные процессы
§ 1. Количество информации
§ 2. Передача данных
§
3. Сжатие данных
§ 4. Информация и управление
§ 5. Информационное общество
Слайд 2Информация и информационные процессы
§ 1. Количество информации
Слайд 3Формула Хартли (1928)
I – количество информации в битах
N
– количество вариантов
Пример:
В аэропорту стоит 10 самолетов, из
них один
летит в Санкт-Петербург. Оценить количество
информации в сообщении «В Санкт-Петербург летит
второй самолет»?
бита
Слайд 4Алфавитный подход
M – мощность алфавита
Информационный объём
символа:
сообщения длиной L:
Пример: сообщение длиной
100 символов закодировано с помощью алфавита из 50 знаков.
вверх до целого числа
6 битов
600 битов
Слайд 5Количество различных сообщений
M – мощность алфавита
L – длина сообщения
N –
количество различных сообщений
алфавит: А, Б, В, Г
всего: 44 = 42
= 16
Слайд 6Информация и вероятность
Доля символов в русских текстах:
из 1000 символов около
175 пробелов
Слайд 7Вероятность
Вероятность события – число от 0 до 1, показывающее, как
часто случается это событие в большой серии одинаковых опытов.
событие никогда
не происходит
(нет неопределенности)
событие происходит в половине
случаев (есть неопределенность)
событие происходит всегда
(нет неопределенности)
x2 0
x2 < 0
Слайд 8Вероятность
N – количество испытаний
m – сколько раз произошло событие
ровно 2:
чётное:
меньше 3:
2
и 2:
2 чётных:
оба меньше 3:
Слайд 9Вероятность и информация
…АААААААААААААААААА
получили букву «А»:
…BАААААААААААААААААА
получили букву «В»:
Чем более неожиданно событие,
тем больше получено информации.
В 10 опытах будет получено в
10 раз больше информации, чем в одном (аддитивность).
Слайд 10Вероятность и информация
при K = 1 информация в битах
Если
событие имеет вероятность p, то количество информации в битах, полученное
в сообщении об этом событии, равно
Слайд 11Вероятность и информация
Аддитивность:
по 8 шариков разного цвета
всего 88 = 64
варианта
Слайд 12Связь с формулой Хартли
N равновероятных событий
совпадает с
формулой Хартли
Если вероятности
разные:
«Васе достался зелёный шарик».
Слайд 13Формула Шеннона
Количество полученной информации равно уменьшению неопределенности.
I = H =
Hнач – Hкон
Неопределённость знаний об источнике данных (N событий, вероятности
pi):
информационная энтропия
Слайд 14Формула Шеннона
«Идёт ли сейчас снег?» (1 – да, 2 –
нет)
зимой:
летом:
Слайд 15Когда неопределённость наибольшая?
Система двух событий:
Неопределенность максимальна, когда все события
равновероятны.
совпадает с формулой Хартли!
Слайд 16Информация и информационные процессы
§ 2. Передача данных
Слайд 17Скорость передачи данных
Скорость передачи данных – это количество битов (байтов,
Кбайт и т.д.), которое передается по каналу связи за единицу
времени (например, за 1 с).
Пропускная способность канала связи – это наибольшая возможная скорость передачи данных, которую принципиально невозможно превысить.
аппаратура, мощность помех
Слайд 18Единицы измерения
1 бит/с = 1 bps (bits per second)
1 кбит/с
= 1000 бит/с
1 Мбит/с = 106 бит/с
1 Гбит/с = 109
бит/с
Объём переданных данных:
скорость передачи
время
v = 512000 бит/с, t = 1 мин
I = v t = 512000 бит/с 60 с = 30 720 000 битов
= 3 840 000 байтов = 3075 Кбайт.
Слайд 19Объём переданных данных
средняя скорость передачи
время
v = 512000 бит/с, t =
1 мин
I = v t = 512000 бит/с ·
60 с
= 30 720 000 битов
= 3 840 000 байтов
= 3750 Кбайт.
: 8
: 1024
Слайд 20Обнаружение ошибок
Бит чётности:
00 01 10 11
000 011 101
110
Если в принятом блоке нечётное число «1» – ошибка!
принято:
010 110 000 111 000
Для файлов – контрольные суммы (хэш):
CRC = Cyclic Redundancy Code
MD5, SHA-1
10010
Слайд 21Помехоустойчивые коды
111 000 000 111 000 – утроение каждого
бита
принято: 010111000101000
исправлено: 000111000111000
10010
Помехоустойчивый код – это
код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.
Слайд 22Расстояние Хэмминга
Расстояние Хэмминга – это количество позиций, в которых отличаются
два закодированных сообщения одинаковой длины.
d(001, 100) = 2
d(000, 111) =
?
3
Исправление r ошибок:
d 2r + 1
Слайд 23Передача 3-битных блоков
dmin= 3 r = 1
d(000000,
x) = ?
Исправление ошибки
принято: 101110
ближайший допустимый код:
101010
Слайд 24Помехоустойчивые коды Хэмминга
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
dmin= 3 r = 1
Слайд 25Код Хэмминга: исправление ошибки
бит 1: (1 + 1 + 0)
mod 2 = 0
бит 2: (1 + 1 + 0)
mod 2 = 0
бит 4: (1 + 1 + 0) mod 2 = 0
Контрольные биты:
Номер ошибочного бита: 2 + 4 = 6
Слайд 26Длинные коды Хэмминга
Контрольные биты:
1, 2, 4, 8, 16, … ,
Слайд 27Информация и информационные процессы
§ 3. Сжатие данных
Слайд 28Что такое сжатие?
Сообщение: АBА CАBАBА
A 00
B 01
АBА
CАBАBА 00 01 00 11 10 00 01 00
01 00
20 битов
Словарь:
Слайд 29Коэффициент сжатия
Сообщение: 10240 символов
Словарь: 5 байтов
Длина кода:
10240×2 =
20480 битов = 2560 байтов
Длина сжатого сообщения:
5 + 2560
= 2565 байтов
Коэффициент сжатия – это отношение размеров исходного и сжатого файлов.
Слайд 30Сжатие без потерь
Сжатие без потерь – это такое уменьшение объема
закодированных данных, при котором можно восстановить их исходный вид из
кода без искажений.
используются только
4 символа из 256
Слайд 31Алгоритм RLE
RLE (англ. Run Length Encoding, кодирование цепочек одинаковых символов)
100
100
200
байтов
Файл qq.txt
Файл qq.rle (сжатый)
4 байта
сжатие в 50 раз!
Слайд 32Алгоритм RLE
АААААААААААААААБВ
Распаковка:
15
2
Применение:
сжатие рисунков *.bmp (с палитрой)
один из этапов сжатия рисунков
*.jpg
8F C0 02 C1 C216
Слайд 33Неравномерные коды
Идея: кодировать часто встречающиеся символы более короткими кодовыми словами.
Азбука
Морзе:
Слайд 34Префиксные коды
Префиксный код – это код, в котором ни одно
кодовое слово не является началом другого кодового слова (условие Фано).
не
все символы в листьях!
Слайд 35Код Шеннона-Фано
Количество символов в сообщении:
На 2 группы с примерно
равным числом символов:
начинаются с 0
начинаются с 1
начинаются с 11
в
порядке невозрастания
Слайд 36Код Шеннона-Фано
Декодирование:
1110111101001011001111
111
01
111
01
00
10
110
01
111
Т
O
Т
O
Е
Н
О
Т
Слайд 37Код Шеннона-Фано
учитывается частота символов
не нужен символ-разделитель
код префиксный – можно декодировать
по мере поступления данных
нужно заранее знать частоты символов
код неоптимален
при ошибке
в передаче сложно восстановить «хвост»
не учитывает повторяющиеся последовательности символов
Слайд 38Алгоритм Хаффмана
По увеличению частоты:
Слайд 39Алгоритм Хаффмана
0
Т
100
Н
101
Код Хаффмана:
Е
110
О
111
Слайд 40Сравнение алгоритмов
Количество символов в сообщении:
Равномерное кодирование (8-битный код):
(140
+ 68 + 68 + 64 + 60) 8
= 3200 битов
Равномерное кодирование (3-битный код):
(140 + 68 + 68 + 64 + 60) 3 = 1200 битов
+ словарь!
Слайд 41Сравнение алгоритмов
Количество символов в сообщении:
(140 + 68 + 68)
2 + (64 + 60) 3 = 924
бита
140 + (68 + 68 + 64 + 60) 3 = 920 бит
Слайд 42Алгоритм Хаффмана
код оптимальный среди алфавитных кодов
нужно заранее знать частоты символов
при
ошибке в передаче сложно восстановить «хвост»
не учитывает повторяющиеся последовательности символов
Слайд 43Алгоритм LZW
1977: А. Лемпел и Я. Зив, 1984: Т. Велч
Идеи:
кодировать не отдельные символы, а блоки
последовательностям символов присваиваются числовые коды
новая
цепочка занесение в словарь с новым кодом
словарь строится по мере получения данных
не нужны частоты символов за один проход!
Применение:
сжатие рисунков *.gif, *.tif
сжатие документов *.pdf
Слайд 44Алгоритм LZW
ввод СТРОКА
пока не конец данных
ввод СИМВОЛ
если Есть_в_словаре(
СТРОКА + СИМВОЛ ) то
СТРОКА:= СТРОКА + СИМВОЛ
иначе
вывод Код(СТРОКА)
Добавить_в_словарь( СТРОКА + СИМВОЛ )
СТРОКА:= СИМВОЛ
вывод Код(СТРОКА)
да / нет
получить из словаря
Слайд 45Сжатие с потерями
Сжатие с потерями – это такое уменьшение объема
закодированных данных, при которых распакованный файл может отличаться от оригинала.
Применение:
сжатие рисунков *.jpg, *.jpeg
сжатие звука *.mp3, *.aac, *.ogg, …
сжатие видео *.mpg, *.wmv, *.mov, …
Идея: «отбросить» часть данных, которые не влияют на восприятие информации человеком (доп. размытие фотографий, частоты выше 20 кГц, …)
Слайд 46Снижение глубины цвета
размер
качество
Слайд 47Сжатие JPEG
Y = 0,299R + 0,587G + 0,114B
Cb = 128
– 0,1687R – 0,3313G + 0,5B
Cr = 128 + 0,5R
– 0,4187G – 0,0813B
глаз чувствительнее к зелёному!
Cb = Cr = 128
Слайд 48Сжатие JPEG
Идея: глаз наиболее чувствителен к яркости
12 чисел
+ дискретное косинусное
преобразование, алгоритмы RLE и Хаффмана
потери!
Слайд 49Сжатие JPEG
Артефакты – заметные искажения из-за сжатия с потерями
Слайд 50Сжатие рисунков с потерями и без
Слайд 51Сжатие звука (MP3)
MP3 = MPEG-1 Layer 3, кодирование восприятия
Битрейт –
это число бит, используемых для кодирования 1 секунды звука.
MP3: от
8 до 320 кбит/c
Без сжатия на CD (1 сек, 44 кГц, 16 бит, стерео):
288000 = 176 000 байт = 1 408000 бит = 1408 кбит
Cжатие MP3 (256 кбит/с):
Слайд 52Сжатие видео
видео = изображения + звук
Кодек (кодировщик/декодировщик) – это программа
для сжатия данных и восстановления сжатых данных.
MJPEG, MPEG-4, DivX, Xvid,
H.264, …
Артефакты – заметные искажения из-за сжатия с потерями
Слайд 53Сжатие: итоги
Хорошо сжимаются:
тексты (*.txt)
документы (*.doc)
несжатые рисунки (*.bmp)
несжатый звук (*.wav)
несжатое видео
(*.avi)
Плохо сжимаются:
случайные данные
сжатые данные в архивах (*.zip, *.rar, *.7z)
сжатые рисунки
(*.jpg, *.gif, *.png)
сжатый звук (*.mp3, *.aac)
сжатое видео (*.mpg, *.mp4, *.mov)
Слайд 54Информация и информационные процессы
§ 4. Информация и управление
Слайд 55Кибернетика
Кибернетика – это наука, изучающая общие закономерности процессов управления и
передачи информации в машинах, живых организмах и обществе.
Идеи:
управление
в любых системах подчиняется одним и тем же законам
управление связано с обменом информацией
Слайд 56Что такое система?
Система – это группа объектов и связей между
ними, выделенных из среды и рассматриваемых как одно целое.
Примеры:
общество
семья
экологическая система
компьютер
файловая
система
операционная система
среда
Системный эффект: свойства системы нельзя свести к «сумме» свойств ее компонентов.
самолёт летает!
Слайд 57Что такое система?
Свойства системы: компоненты + связи (алмаз, графит)
Подсистема: компонент-система.
Системный анализ: изучение сложных систем на основе теории управления и
теории информации.
подсистема
элемент
Надсистема: система более высокого уровня.
Слайд 58Системы управления
Разомкнутая система – регулятор не получает информации о состоянии
объекта (программное управление).
Примеры:
водитель с завязанными глазами
начальник, не проверяющий рабочих
информационное табло
на вокзале
светофор
простота – не нужно датчиков
нужна точная модель объекта
нельзя учесть влияние среды
Слайд 59Системы с обратной связью
Замкнутая система – регулятор получает информации о
состоянии объекта по каналу обратной связи.
усложнение системы (датчики)
модель объекта может
быть неточной
можно учесть влияние среды
Отрицательная ОС – регулятор уменьшает разницу между целью и состоянием объекта.
Слайд 60Типы систем управления
Автоматические – работают без участия человека.
Автоматизированные – собирают
и обрабатывают информацию, а решения принимает человек.
Адаптивные – «подстраиваются» под
изменение внешних условия или свойств объекта.
Слайд 61Управление роботами
система управления
исполнительные механизмы (моторы)
датчики
датчики
датчики
Слайд 62Управление роботами
микроконтроллер
микропроцессор
оперативная память (ОЗУ)
постоянная память (ПЗУ)
каналы ввода-вывода
ошибка управления:
e =
– 0
пропорциональный закон управления:
u = – ke = – ke(
– 0)
команда для вращения
(+ – по часовой стрелке)
Слайд 63Информация и информационные процессы
§ 5. Информационное общество
Слайд 64Что такое информационное общество?
Прогресс в обработке информации:
письменность (около 3000 лет
до н.э., Египет)
книгопечатание (X век – Китай, XV век –
Европа)
средства связи (телеграф, телефон, радио, телевидение; конец XIX – начало XX века);
компьютеры (вторая половина XX века).
Информационное общество – это такая ступень развития цивилизации, на которой главными продуктами производства становятся информация и знания.
Слайд 65Информатизация
Информатизация – переход к информационному обществу:
внедрение информационных технологий во все
сферы жизни
развитие компьютерных сетей, сотовой связи и т.п.
необходимость компьютерной грамотности
для всех
свобода доступа к информации;
доступность образования, в том числе дистанционного (через Интернет)
изменение структуры экономики
изменение уклада жизни людей
Слайд 66Информатизация
Негативные последствия:
усиление влияния СМИ
разрушается частная жизнь людей
сложно выбрать качественные и
достоверные данные
личное общение людей заменяется общением в Интернете
людям старшего поколения
очень сложно приспособиться
Слайд 67Информационные ресурсы
Ресурсы – условия, позволяющие после некоторой «обработки» получить желаемый
результат.
Информационные ресурсы – документы
в библиотеках, архивах, банках данных,
информационных системах.
товар!
Информационные услуги:
поиск и подбор информации
подбор персонала (кадровые агентства)
обучение (учебные центры)
рекламные агентства
консультации, услуги по оптимизации бизнеса
разработка программ и веб-сайтов
Слайд 68Информационные технологии
Технология – это способ сделать «продукт» из исходных материалов
(с гарантированным результатом!).
Новые информационные технологии – это технологии, связанные
с использованием компьютеров для хранения, защиты, обработки и передачи информации.
подготовка документов в электронном виде
поиск информации
телекоммуникации (сети, Интернет, e-mail)
автоматизированные системы управления (АСУ)
системы автоматизированного проектирования (САПР)
геоинформационные системы
обучение (электронные учебники, компьютерные тренажеры, дистанционное обучение).
Слайд 69Автоматизированные системы управления
Ресторан+
Слайд 70Автоматизированные системы управления
… технологическими процессами (АСУ ТП)
рабочее место
оператора
блок сбора
информации
датчики
блок управления
локальная сеть
Слайд 71САПР
САПР – системы автоматизированного проектирования
Слайд 73Дистанционное обучение
видеолекции
самостоятельная работа
письменные задания
работа с тьютором (наставником)
консультации по Интернету
тьютор
Слайд 74Дистанционное обучение
www.intuit.ru
www.edx.org
www.udacity.com
www.coursera.org
Гарвардский университет
Массачусетский технологический институт
Стэнфорский университет
Университет Виргиния
33
университета
www.khanacademy.org
Академия Хана
Слайд 76Государственные электронные услуги
gosuslugi.ru – Портал государственных услуг РФ
подать заявку на
получение паспорта
подать налоговую декларацию
записаться на приём к врачу;
зарегистрироваться как ИП
или ООО
зарегистрировать автомобиль
оплатить штрафы
…
rosreestr.ru – регистрация сделок с недвижимостью
www.nalog.ru – Федеральная налоговая служба
www.pfrf.ru – Пенсионный фонд РФ
rospotrebnadzor.ru – Роспотребнадзор
Слайд 77Электронная цифровая подпись
Электронная цифровая подпись (ЭЦП) – это набор символов,
который получен в результате шифрования сообщения с помощью личного секретного
ключа отправителя.
Применение:
доказательство авторства
невозможность отказа от авторства
защита от изменений (проверка целостности)
Слайд 78Электронная цифровая подпись
10101001010101011
открытый ключ
секретный ключ
Aсимметричное шифрование
11110101101000001
?
совпадают?
Удостоверяющий центр
Слайд 79Информационная культура
Для общества – способность общества
эффективно использовать информационные ресурсы и
средства обмена информацией
применять передовые достижения в области информационных технологий
Для человека
– умение
формулировать потребность в информации
находить нужную информацию
отбирать и анализировать информацию
представлять информацию в разных видах;
обрабатывать информацию
использовать информацию для принятия решений
Слайд 80Стандарты в сфере ИТ
Стандарт – это нормативный документ, в котором
определены требования к некоторому объекту или процессу.
использование технических терминов
разъёмы
величины напряжения
и силы тока
протоколы обмена данными (TCP/IP)
языки программирования (С++)
оформление документации
ISO – Международная организация по стандартизации
МЭК – Международная электротехническая комиссия
IBM PC – открытая архитектура
Слайд 81Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г.
Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО
ПГГПУ, г. Пермь
eremin@pspu.ac.ru
Слайд 82Источники иллюстраций
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
иллюстрации художников издательства «Бином»
авторские материалы