1. Приведите примеры процессов обработки информации, которые чаще всего вам приходится выполнять в жизни. Для каждого примера определите исходные данные, алгоритм (правила) обработки и получаемые результаты. К каким типам обработки информации относятся эти процессы?
Пример процесса обработки информации: составление плана на день. Исходные данные - список дел на сегодня, алгоритм - выбрать задачи наиболее важные для выполнения сегодня и распределить их по временным промежуткам. Результат - план на день с распределением задач по времени. Этот процесс относится к типу организационной обработки информации.
Пример процесса обработки информации: решение математической задачи. Исходные данные - постановка задачи и начальные данные. Алгоритм - выполнение определенной последовательности математических действий. Результат - решение задачи. Этот процесс относится к типу аналитической обработки информации.
Пример процесса обработки информации: поиск информации в Интернете. Исходные данные - запрос пользователя. Алгоритм - использование поисковой системы и анализ результатов поиска. Результат - список релевантной информации. Этот процесс относится к типу информационной обработки.
2. Поясните суть понятий «кодирование», «код», «кодовая таблица».
Кодирование - процесс преобразования информации из одной формы в другую. Код - совокупность символов, присвоенных элементам информации для представления ее в форме, пригодной для передачи и обработки. Кодовая таблица - таблица, в которой каждому символу или комбинации символов сопоставлен его код.
3. Светодиодная панель содержит шесть излучающих элементов, каждый из которых может светиться или красным, или жёлтым, или зелёным цветом. Сколько различных сигналов можно передать с помощью панели (все излучающие элементы должны гореть, порядок цветов имеет значение)?
Каждый из шести излучающих элементов может принимать один из трех цветов, таким образом всего возможно 3^6 = 729 различных сигналов.
4. Автомобильный номер состоит из нескольких букв (количество букв одинаковое во всех номерах), за которыми следуют три цифры. При этом используются 10 цифр и только 5 букв: А, В, С, D и F. Требуется не менее 100 тысяч различных номеров. Какое наименьшее количество букв должно быть в автомобильном номере?
Для получения не менее 100 тысяч различных номеров нужно использовать 4 буквы. В этом случае всего возможно 5^4 * 10^3 = 6,25 миллиона уникальных номеров.
5. Сколько существует различных последовательностей из 6 символов четырёхбуквенного алфавита {А, В, С, D}, которые содержат не менее двух букв А (т. е. две и более буквы А)?
Сначала определим общее число возможных последовательностей из 6 символов четырехбуквенного алфавита - 4^6 = 4096. Затем определим число последовательностей, которые не содержат буквы А - 3^6 = 729. Таким образом, число последовательностей, содержащих не менее двух букв А, равно 4096 - 729 - 1 (поскольку последовательность может состоять только из букв А) = 3366.
6. Сравните равномерные и неравномерные коды. Каковы их основные достоинства и недостатки?
Равномерные и неравномерные коды представляют различные подходы к представлению информации в компьютерных системах. Равномерные коды характеризуются тем, что каждому символу назначается одинаковая длина кодового слова, что облегчает процессы декодирования. Однако они могут привести к неэффективному использованию пространства, так как короткие слова могут оказаться избыточными для представления некоторых символов. Неравномерные коды, напротив, позволяют использовать различную длину кодовых слов, что повышает эффективность, но усложняет декодирование. Основным достоинством равномерных кодов является их простота, но они неэффективны при передаче часто встречающихся символов. Неравномерные коды обеспечивают оптимальное использование ресурсов, но требуют более сложных методов обработки.
7. Какие коды называют префиксными? Почему они так важны? В чём суть прямого и обратного условий Фано?
Префиксные коды – это такие коды, в которых ни одно кодовое слово не является префиксом другого. Эта особенность позволяет однозначно раскодировать закодированную последовательность без дополнительных разделителей. Их важность заключается в минимизации возможности ошибок при декодировании и оптимизации использования пространства для представления информации. Прямое условие Фано заключается в том, что длины кодовых слов увеличиваются по мере увеличения вероятности появления символов, обеспечивая оптимальное распределение длин. Обратное условие Фано предполагает, что код, удовлетворяющий прямому условию Фано, является единственным оптимальным кодом для данного распределения вероятностей. Эти условия помогают создавать эффективные и безошибочные префиксные коды.
8. Двоичные коды для 5 букв латинского алфавита представлены в таблице:
Из четырёх сообщений, закодированных этими кодами, только одно пришло без ошибки. Найдите его: 1) 110100000100110011; 2) 111010000010010011; 3) 110100001001100111; 4) 110110000100110010.
3) 110100001001100111;
9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
10. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А — 0, Б — 11, В — 20, Г — 21, Д — 22. Можно ли сократить для одной из букв длину кодового слова так, чтобы закодированную последовательность по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.
11. Для передачи закодированных сообщений используется таблица кодовых слов из четырёх букв. Причем используются только буквы А, Р и У. Сколько различных кодовых слов может быть в такой таблице, если ни в одном слове нет трёх одинаковых букв, идущих подряд?
АРУА АУРА РУАА РАУА УАРА УРАА ААРУ АУАР РААУ РУАУ УААР УРАР Всего 12 различных кодовых слов.
12. Методом половинного деления в последовательности чисел 061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612 требуется найти число 590. Опишите процесс поиска.
Метод половинного деления (или бинарного поиска) позволяет находить заданное число в упорядоченной последовательности значительно быстрее, чем линейный поиск. В данном случае, мы хотим найти число 590 в последовательности чисел. Давайте опишем процесс поиска:
Начнем с заданного интервала, в данном случае, у нас есть последовательность чисел от 061 до 612. Это наше начальное "окно поиска".
Сначала найдем средний элемент в этом интервале. Для этого сложим минимальное и максимальное значение интервала и разделим на 2: (061 + 612) / 2 = 326.5. Мы округляем результат до целого числа, так как у нас могут быть только целые числа.
Теперь сравним средний элемент (326) с искомым числом (590):
Если средний элемент (326) меньше искомого числа (590), то мы знаем, что искомое число должно находиться в правой половине интервала (от 326 до 612). Если средний элемент (326) больше искомого числа (590), то мы знаем, что искомое число должно находиться в левой половине интервала (от 061 до 326). В данном случае, 326 меньше 590, поэтому мы переходим к правой половине интервала. Наш новый интервал поиска становится от 326 + 1 (т.е., от следующего элемента после среднего) до 612.
Теперь мы повторяем шаги 2-4 для нового интервала (от 327 до 612).
Находим новый средний элемент в интервале (327 + 612) / 2 = 469.
Сравниваем его с искомым числом (590). 469 меньше 590, поэтому мы переходим к правой половине интервала (от 470 до 612).
Повторяем процесс. Находим новый средний элемент (470 + 612) / 2 = 541.
Сравниваем его с искомым числом (590). 541 меньше 590, поэтому мы переходим к правой половине интервала (от 542 до 612).
Продолжаем процесс. Находим новый средний элемент (542 + 612) / 2 = 577.
Сравниваем его с искомым числом (590). 577 меньше 590.
Теперь интервал поиска стал от 578 до 612. Мы повторяем процесс.
Находим новый средний элемент (578 + 612) / 2 = 595.
Сравниваем его с искомым числом (590). 595 больше 590.
Теперь интервал поиска стал от 578 до 594. Мы опять находим средний элемент и сравниваем его с искомым числом.
Процесс повторяется до тех пор, пока мы не найдем искомое число.
В данном случае, следующий средний элемент будет 586, затем 590, и мы обнаружим, что искомое число 590 найдено.
Таким образом, методом половинного деления мы нашли число 590 в данной последовательности чисел.
13. В Международном конкурсе по информатике «Бобёр» школьникам была предложена задача «Склад», подготовленная специалистами из Японии. Вот её условие.
Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.
Чтобы уменьшить количество открывания дверей, он действует следующим образом:
Сначала открывает склад со средним номером — склад № 16. Затем: • если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру; • если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру.
После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть?
Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?
Плотник использовал метод бинарного поиска для оптимизации количества открываний дверей.
Итак, у нас есть 31 склад. Плотник начинает с открытия склада №16. Поскольку он обнаружил, что заполнены были склады от №1 до №15, это означает, что он открыл склады с номерами от 1 до 15, используя метод бинарного поиска, чтобы минимизировать количество открываний дверей.
Для того чтобы заполнить склады от 1 до 15, плотнику пришлось открыть следующие склады: 1, 8, 4, 12, 2, 6, 10, 14, 3, 5, 7, 9, 11, 13, 15 (15 складов в сумме).
Итак, ему пришлось открыть 15 дверей, используя метод бинарного поиска.