Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

1.6. РЕАЛЬНЫЕ ПРИЛОЖЕНИЯ
Различные.методы,.представленные.в.этой.главе.(рекурсия,.мемоизация,.сжатие.
и.манипулирование.на.битовом.уровне),.настолько.широко.распространены.
в.разработке.современного.программного.обеспечения,.что.без.них.невозможно.
представить.мир.вычислений..Несмотря.на.то.что.задачи.могут.быть.решены.и.без.
них,.зачастую.более.логично.или.целесообразно.решать.их.с.использованием.
этих.методов.

---

46
Глава 1.
Простые задачи
В.частности,.рекурсия.лежит.в.основе.не.только.многих.алгоритмов,.но.даже.
целых.языков.программирования..В.некоторых.функциональных.языках.про-
граммирования,.таких.как.Scheme.и.Haskell,.рекурсия.заменяет.циклы,.при-
меняемые.в.императивных.языках..Однако.следует.помнить,.что.все,.что.может.
быть.достигнуто.с.помощью.рекурсивного.метода,.может.быть.выполнено.также.
итерационным.способом.
Мемоизация.успешно.задействовалась.для.ускорения.работы.синтаксических.
анализаторов.—.программ,.которые.интерпретируют.языки..Это.полезно.во.
всех.задачах,.где.результат.недавнего.вычисления,.скорее.всего,.будет.запрошен.
снова..Еще.одна.область.действия.мемоизации.—.среды.выполнения.языков.
программирования..Некоторые.такие.среды.выполнения,.например.для.версии.
Prolog,.автоматически.сохраняют.результаты.вызовов.функций.
(автомемоиза-
ция)
,.поэтому.функцию.не.приходится.выполнять.в.следующий.раз.при.таком.
же.вызове.
Сжатие.сделало.мир,.подключенный.к.интернету.с.его.ограниченной.пропуск-
ной.способностью,.более.терпимым..Метод.битовых.строк,.рассмотренный.
в.разделе.1.2,.применим.для.простых.типов.данных.в.реальном.мире,.имеющих.
ограниченное.число.возможных.значений,.для.которых.даже.1.байт.оказыва-
ется.избыточным..Однако.большинство.алгоритмов.сжатия.работают.путем.
поиска.шаблонов.или.структур.в.наборе.данных,.которые.позволяют.устра-
нить.повторяющуюся.информацию..Они.значительно.сложнее,.чем.описано.
в.разделе.1.2.
Одноразовые.шифры.не.подходят.для.общих.случаев.шифрования..Они.требуют,.
чтобы.и.шифратор,.и.дешифратор.имели.один.из.ключей.(фиктивные.данные.
в.нашем.примере).для.восстановления.исходных.данных,.что.слишком.громоздко.
и.в.большинстве.схем.шифрования.не.позволяет.достичь.цели.—.сохранить.ключи.
в.секрете..Но,.возможно,.вам.будет.интересно.узнать,.что.название.«одноразовый.
шифр».придумали.шпионы,.которые.во.время.холодной.войны.использовали.
настоящие.бумажные.блокноты.с.записанными.в.них.фиктивными.данными.для.
создания.шифрованных.сообщений.
Эти.методы.являются.строительными.блоками.программ,.на.них.основаны.
.другие.алгоритмы..В.следующих.главах.вы.увидите,.как.широко.они.приме-
няются.