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

Принятие разрешимости с полиномиальным временем как формального поня- тия эффективности было постепенным процессом, на который повлияли работы многих исследователей, среди которых были Кобхэм, Рабин, Эдмондс, Хартма- нис и Стирнс.
В отчете Сипсера (Sipser, 1992) содержится как историческая, так и техническая информация по процессу разработки. Подобным образом исполь- зование асимптотической записи порядка скорости роста как границы времени выполнения алгоритмов (в отличие от точных формул с коэффициентами при старших членах и младшими членами) было решением, не столь очевидным на момент его введения; в Тьюринговской лекции Тарьяна (Tarjan, 1987) содержится интересная точка зрения на ранние представления исследователей, работавших в этой области, включая Хопкрофта, Тарьяна и других. Дополнительную инфор- мацию об асимптотической записи и скорости роста базовых функций можно найти у Кнута (Knuth, 1997a).

Реализация приоритетных очередей с использованием кучи, а также ее при- менение для сортировки обычно приписываются Уильямсу (Williams, 1964) и Флойду (Floyd, 1964). Приоритетная очередь представляет собой нетривиаль- ную структуру данных с множеством разных применений; в следующих главах мы обсудим другие структуры данных, когда они будут полезны при реализации
конкретных алгоритмов. Структура данных Union-Find рассматривается в главе 4 для реализации алгоритма поиска минимального остовного дерева, а рандомизи- рованное хеширование — в главе 13. Другие структуры данных рассматриваются в книге Тарьяна (Tarjan, 1983). Библиотека LEDA (Library of Efficient Datatypes and Algorithms) Мельхорна и Нэера (Mellhorn, Naher, 1999) предоставляет обшир- ную подборку структур данных, используемых в комбинаторных и геометрических задачах.

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

Упражнение 8 основано на задаче, о которой мы узнали от Сэма Туэга.


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

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

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