Читать онлайн «Искусство программирования. Том 3. Сортировка и поиск. 2-е издание»

Original pages: 004-033 1 УДК 681. 142. 2 Третий том известной монографии одного из крупнейших американских специалистов по про- граммированию Д. Кнута (первый том вышел в издательстве ”Мир” в 1976 г. , второй—в 1977 г. ) состоит из двух частей: ”Сортировка” и ”Поиск”. В них подробно исследуются различные алгорит- мы внутренней и внешней сортировки, изучаются методы поиска информации в таблицах на основе сравнения или преобразования ключей, даются оценки эффективности предлагаемых алгоритмов. Книга снабжена большим количеством задач и примеров разной степени трудности, существенно дополняющих основной текст. От других руководств по программированию книга выгодно отличается строгостью изложения и широким применением математического аппарата. Вместе с тем она доступна студентам первого курса. Знакомство с двумя первыми томами желательно, но не обязательно. Каждый, кто хочет научиться квалифицированно программировать, найдет в ней много полезного. Рассчитана на широкий круг программистов. Редакция литературы по математическим наукам 20204−022 K 041(01)−78 22 − 78 c Перевод на русский язык, ”Мир”. 1978 2 Original pages: 004-033 ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА Д. Э. Кнут хорошо знаком советскому читателю по переводам двух первых томов его обширной монографии ”Искусство программирования для ЭВМ” и не нуждается в аттестации. Настоящая книга представляет собой третий том и посвящена алгоритмам сортировки и поиска информации. Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столе- тию, и за столь длительное время многие специалисты успели испробовать свои силы в этой области. Написано немало отчетов, статей, монографий. И даже в этих условиях книга Д. Кнута стала событи- ем. По существу это энциклопедия, в которой можно найти любую справку, касающуюся алгоритмов, методов их оценок, истории вопроса и нерешенных проблем. Нет нужды говорить о важности самой области. Практически сортировка и поиск в той или иной мере присутствуют во всех приложениях; в частности, при обработке больших объемов данных эф- фективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы. Поэтому, как справедливо отмечает автор, книга адресована не только системным програм- мистам, занимающимся разработкой программ сортировки и поиска информации. Можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные элементы искусства программирования. Кроме теоретической и практической ценности, книга имеет большое методическое значение. Многие авторы и преподаватели смогут извлечь из нее новые и полезные сведения не только по существу рассматриваемых вопросов, но и по способу их изложения. Автору мастерски удается ”рас- слоить” весь материал таким образом, что книгу можно использовать практически на любом уровне знакомства с предметом и при различной общей математической подготовленности читателя.