Примечания и дополнительная литература

Воинственное выражение «разделяй и властвуй» появилось вскоре после созда- ния самого метода. Кнут (Knuth, 1998) приписывает Джону фон Нейману одно из первых явных выражений этого принципа — алгоритм сортировки слиянием в 1945 году.
Также у Кнута (Knuth, 1997b) приведена дополнительная информация о разрешении рекуррентности.

Алгоритм вычисления ближайшей пары точек на плоскости был создан Майк- лом Шамосом и является одним из первых нетривиальных алгоритмов в области вычислительной геометрии. В обзорной статье Смида (Smid, 1999) обсуждается широкий спектр результатов для задач поиска ближайших точек. Более быстрый рандомизированный алгоритм для этой задачи будет рассмотрен в главе 13. (Смид также делает интересное замечание по поводу неочевидности представленного здесь алгоритма «разделяй и властвуй»: он говорит, что создатели алгоритма из- начально считали, что квадратичное время является лучшим возможным для по- иска ближайшей пары точек на плоскости.) В более общем плане метод «разделяй и властвуй» оказался очень полезным в вычислительной геометрии, и в книгах Препараты и Шамоса (Preparata, Shamos, 1985) и де Берга и др. (de Berg, 1997) приводится множество других примеров использования этого метода при проек- тировании геометрических алгоритмов.

Алгоритм умножения двух n-разрядных целых чисел за субквадратичное время разработали Карацуба и Офман (Karatsuba, Ofman, 1962). Дополнительная информация об асимптотически быстрых алгоритмах умножения приводится у Кнута (Knuth, 1997b). Конечно, чтобы субквадратичные методы обеспечили выигрыш по сравнению со стандартным алгоритмом, количество разрядов во входных данных должно быть достаточно большим.

У Пресса и др. (Press et al., 1988) приводится информация о быстром преоб- разовании Фурье, включая его практическое применение в обработке сигналов и других областях.

Примечания к упражнениям

Упражнение 7 основано на результатах, авторами которых были Донна Луэллин, Крейг Тови и Майкл Трик.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Примечания и дополнительная литература:

  1. Дополнительная литература
  2. Дополнительная литература
  3. Дополнительная литература
  4. Дополнительная литература
  5. Дополнительная литература
  6. Дополнительная литература
  7. Дополнительная литература
  8. Дополнительная литература
  9. Дополнительная литература
  10. Дополнительная литература
  11. Список дополнительной литературы
  12. Дополнительная литература
  13. Дополнительная литература
  14. Дополнительная литература
  15. Дополнительная литература
  16. Дополнительная литература
  17. Дополнительная литература
  18. Дополнительная литература
  19. Дополнительная литература