§ 4. Обработка информации

Самое главное

Обработка информации — это целенаправленный процесс изменения содержания или формы представления информации. Существует два различных типа обработки информации:

1) обработка, связанная с получением нового содержания, новой информации;

2) обработка, связанная с изменением формы представления информации, не изменяющая её содержания.

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

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

Префиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова. Сообщение, закодированное с помощью префиксного кода, может быть однозначно декодировано.

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

Время поиска зависит от способа организации набора данных и используемого алгоритма поиска.

Для осуществления поиска в неструктурированном наборе данных применяется метод последовательного перебора.

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

Вопросы и задания

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

2. Поясните суть понятий «кодирование», «код», «кодовая таблица».

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

4. Автомобильный номер состоит из нескольких букв (количество букв одинаковое во всех номерах), за которыми следуют три цифры. При этом используются 10 цифр и только 5 букв: А, В, С, D и F. Требуется не менее 100 тысяч различных номеров. Какое наименьшее количество букв должно быть в автомобильном номере?

5. Сколько существует различных последовательностей из б символов четырёхбуквенного алфавита {А, В, С, D}, которые содержат не менее двух букв А (т. е. две и более буквы А)?

6. Сравните равномерные и неравномерные коды. Каковы их основные достоинства и недостатки?

7. Какие коды называют префиксными? Почему они так важны? В чём суть прямого и обратного условий Фано?

8. Двоичные коды для 5 букв латинского алфавита представлены в таблице:

Из четырёх сообщений, закодированных этими кодами, только одно пришло без ошибки. Найдите его:

1) 110100000100110011;
2) 111010000010010011;
3) 110100001001100111;
4) 110110000100110010.

9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

10. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А — 0, Б — 11, В — 20, Г — 21, Д — 22. Можно ли сократить для одной из букв длину кодового слова так, чтобы закодированную последовательность по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.

11. Для передачи закодированных сообщений используется таблица кодовых слов из четырёх букв. Причем используются только буквы А, Р и У. Сколько различных кодовых слов может быть в такой таблице, если ни в одном слове нет трёх одинаковых букв, идущих подряд?

12. Методом половинного деления в последовательности чисел

061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612

требуется найти число 590. Опишите процесс поиска.

13. В Международном конкурсе по информатике «Бобёр» школьникам была предложена задача «Склад», подготовленная специалистами из Японии. Вот её условие.

Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.

Чтобы уменьшить количество открывания дверей, он действует следующим образом:

Сначала открывает склад со средним номером — склад № 16. Затем:

• если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру;

• если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру.

После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть?

Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?