Обработка — целенаправленное изменение информации по правилам. Результатом может быть новое содержание или новая форма представления без изменения смысла.
Для каждой процедуры полезно явно назвать входные данные, алгоритм, результат и условие завершения.
Каркас темы
Вычисление вывода по данным создаёт новое содержание, а перевод формата или кодирование меняет представление; одна реальная задача может сочетать оба типа.
Информационная задача задаёт исходные данные, исполнителя, алгоритм обработки и требуемый результат; условие завершения показывает, когда работа окончена.
Компьютер является формальным исполнителем и выполняет заданные команды без самостоятельного понимания цели; человек может выбирать и изменять способ решения.
Код — система условных обозначений, кодовая таблица связывает объекты и кодовые слова, кодирование заменяет исходные объекты их кодами.
Равномерный код использует кодовые слова одной длины; неравномерный — разных длин.
Префиксный код не допускает, чтобы одно кодовое слово было началом другого; это прямое условие Фано и достаточное условие однозначного декодирования слева направо.
Обратное условие Фано запрещает одному слову быть окончанием другого и достаточно для декодирования справа налево.
Невыполнение прямого условия Фано само по себе не доказывает неоднозначность: может выполняться обратное условие или иной критерий однозначной декодируемости.
В бинарном кодовом дереве кодовые слова префиксного кода соответствуют листьям; путь от корня задаёт последовательность битов.
Для алфавита мощности q существует qⁿ слов фиксированной длины n; для нескольких разрешённых длин количества складывают.
Ограничения на позиции считают отдельно: выбирают позиции особых символов, затем заполняют остальные разрешёнными способами.
Последовательный поиск применим к любому массиву и завершает работу при нахождении элемента или после просмотра всех N элементов.
Если искомый элемент гарантированно присутствует и равновероятно занимает любую из N позиций, среднее число последовательных сравнений равно (N+1)/2; для отсутствующего элемента требуется N сравнений.
Двоичный поиск требует упорядоченного массива и после каждого сравнения отбрасывает половину оставшегося диапазона.
Организация данных влияет на выбор алгоритма: подготовка сортировки имеет стоимость, поэтому её выгода зависит от числа будущих запросов.