На этом шаге мы подведем некоторый итог изложенному материалу.
Различные методы, представленные на предыдущих шагах (рекурсия, мемоизация, сжатие и манипулирование на битовом уровне), настолько широко распространены в разработке современного программного обеспечения, что без них невозможно представить мир вычислений. Несмотря на то что задачи могут быть решены и без них, зачастую более логично или целесообразно решать их с использованием этих методов.
В частности, рекурсия лежит в основе не только многих алгоритмов, но даже целых языков программирования. В некоторых функциональных языках программирования, таких как Scheme и Haskell, рекурсия заменяет циклы, применяемые в императивных языках. Однако следует помнить, что все, что может быть достигнуто с помощью рекурсивного метода, может быть выполнено также итерационным способом.
Мемоизация была успешно использована для ускорения работы синтаксических анализаторов - программ, которые интерпретируют языки. Это полезно во всех задачах, где результат недавнего вычисления, скорее всего, будет запрошен снова. Еще одна область действия мемоизации - среды выполнения языков программирования. Некоторые такие среды выполнения, например для версии Prolog, автоматически сохраняют результаты вызовов функций (автомемоизация), поэтому функцию не приходится выполнять в следующий раз при таком же вызове. Это похоже на работу декоратора @lru_cache() в fib4().
Сжатие сделало мир, подключенный к Интернету с его ограниченной пропускной способностью, более терпимым. Метод битовых строк, рассмотренный на 8 шаге, применим для простых типов данных в реальном мире, имеющих ограниченное число возможных значений, для которых даже 1 байт является избыточным. Однако большинство алгоритмов сжатия работают путем поиска шаблонов или структур в наборе данных, которые позволяют устранить повторяющуюся информацию. Они значительно сложнее, чем описано на 8 шаге.
Одноразовые шифры не подходят для общих случаев шифрования. Они требуют, чтобы и шифратор, и дешифратор имели один из ключей (фиктивные данные в нашем примере) для восстановления исходных данных, что слишком громоздко и в большинстве схем шифрования не позволяет достичь цели - сохранить ключи в секрете. Но, возможно, вам будет интересно узнать, что название "одноразовый шифр" придумали шпионы, которые во время холодной войны использовали настоящие бумажные блокноты с записанными в них фиктивными данными для создания шифрованных сообщений.
Эти методы являются строительными блоками программ, на них основаны другие алгоритмы. В следующих шагах вы увидите, как широко они применяются.
Со следующегол шага мы начнем рассматривать задачи поиска.
