Лекция 13

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

структурированный набор данных (упорядоченный список)
искомый элемент сравнивается с центральным элементом последова-тельности, номер которого находится как [N/2] + 1; если значения искомого элемента и центрального совпадают, то поиск завершается, в противном случае поиск продолжается в одной из двух частей последовательности
длительность поиска (L): N = 2L,
где N — размер набора данных
неструктурированный набор данных
поиск завершается, когда найден искомый элемент или когда просмотрены все элементы набора данных, но искомого элемента в нем нет
длительность поиска (L): L = N/2,
где N — размер набора данных;
если искомый элемент окажется последним или его не окажется вообще, то длительность поиска равна N
Поиск информации
МЕТОД
ПОСЛЕДОВАТЕЛЬНОГО
ПЕРЕБОРА
МЕТОД
ПОЛОВИННОГО
ДЕЛЕНИЯ
Алгоритм поиска информации зависит от способа организации информации.

Технические системы передачи информации
Из истории:
первой технической системой передачи стал телеграф (1837 г.);
затем был изобретен телефон (1876 г. американец Александр Белл);
изобретение радио (1895 г. Русский инженер Александр Степанович Попов.1896 г. итальянский инженер Г. Маркони)
в 20 веке появились телевидение и Интернет

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

Модель передачи информации по техническим каналам связи
ШУМ
КАНАЛ СВЯЗИ
ЗАЩИТА от ШУМА
КОДИРУЮЩЕЕ УСТРОЙСТВО
ПРИЕМНИК ИНФОРМАЦИИ
ДЕКОДИРУЮЩЕЕ УСТРОЙСТВО
ИСТОЧНИК ИНФОРМАЦИИ

Пример работы модели передачи информации по техническим каналам
КОДИРУЮЩЕЕ УСТРОЙСТВО
МИКРОФОН
КАНАЛ СВЯЗИ
ДЕКОДИРУЮЩЕЕ УСТРОЙСТВО
ПРИЕМНИК

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

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

Задачи, решаемые разработчиками технических систем передачи информации:
как обеспечить наибольшую скорость передачи информации;
как уменьшить потери информации при передаче.
К. Шеннон был первым, взявшимся за решение этих задач и создавшим науку – теорию информации.

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

Пропускная способность канала
зависит от его технической реализации.
В компьютерных сетях используются следующие средства связи:
телефонные линии (10÷100 Кбит/с);
электрическая кабельная связь;
оптоволоконная кабельная связь (10÷100 Мбит/с);
радиосвязь (10÷100 Мбит/с).

Скорость передачи информации
зависит не только от пропускной способности канала связи, но и от разрядности кодировки информации.
Длину кода сообщения надо делать минимально возможной.

Шум
Термином «шум» называют разного помехи, искажающие передаваемый сигнал и приводящие к потере информации.
Технические причины возникновения помех:
плохое качество линий связи;
незащищенность друг от друга различных потоков информации, передаваемой по одним и тем же каналам.
Наличие шума приводит к потере информации

Защита от шума
Шеннон разработал специальную теорию кодирования, дающую методы борьбы с шумом.
Одна из важнейших идей этой теории состоит в том, что передаваемый по линии связи код должен быть избыточным.
Избыточность кода – это многократное повторение передаваемых данных.

Защита от шума
Избыточность кода не может быть слишком большой. Это приведет к задержкам и удорожанию связи.
Теория кодирования как раз и позволяет получить такой код, который будет оптимальным: избыточность передаваемой информации будет минимально возможной, а достоверность принятой информации – максимальной.

Защита от шума
(1940-1950 г. XX века)

Защита от шума
В современных системах цифровой связи для борьбы с потерей информации при передаче:
все сообщение разбивается на порции – блоки;
для каждого блока вычисляется контрольная сумма (сумма двоичных цифр), которая передается вместе с данным блоком;
в месте приема заново вычисляется контрольная сумма принятого блока, если она не совпадает с первоначальной, передача повторяется.

Система основных понятий

Информационный процесс
Информационный процесс — совокупность последовательных действий (операций), производимых над информацией (в виде данных, идей, гипотез, теорий) для получения какого-либо результата (достижения цели).
!
Информационные процессы

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

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

Кодирование информации
Кодирование — обработка информации, заключающая-ся в её преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем.
Код — система условных обозначений (кодовых слов), используемых для представ-ления информации.
Кодовая таблица — сово-купность используемых ко-довых слов и их значений.
!

КОМБИНАТОРИКА
Всего: 10 вариантов
Всего: 10·10=100
вариантов
Всего: 10·10·10=1000
вариантов
Сколько вариантов
Кодовый замок имеет три кольца с цифрами от 0 до 9. Сколько различных комбинаций можно на нем закодировать?
Правило умножения
Если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n · m способами.
Решение:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

Префиксный код
Главное условие использования неравномерных кодов — возможность однозначного декодирования записанного с их помощью сообщения.
Пре́фиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова.
!
Определите, является ли код, состоящий из заданной последовательности слов, префиксным:
?
а) 0, 10, 11
б) 0, 10, 11, 100
префиксный код
не префиксный код
10

Правила Фано
Роберт Марио Фа́но - американский учёный, известный по работам в области теории информации.
Для того чтобы сообщение, записанное с помощью неравномерного кода, однозначно декодировалось, достаточно, чтобы никакое кодовое слово не было началом другого (более длинного) кодового слова.
Обратное условие Фано также является достаточным условием однозначного декодирования неравномер-ного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода.
Для возможности однозначного декодирования достаточно выполнения одного из условий Фано —прямого или обратного.

Задание 1
Светодиодная панель содержит 6 излучающих элементов, каждый из которых может светиться красным, желтым, синим или зеленым цветом. Сколько различных сигналов можно передать с помощью панели (все излучающие элементы должны гореть, порядок цветов имеет значение)?
1
2
3
4
5
6