AOP_Tom3 (1021738), страница 19
Текст из файла (страница 19)
Надеемся, что читатель не будет удивлен, найдя ссылки на главы 7, 8 и последующие не вошедшие в предлащемые три тома главы. Мы вместе с автором надеемся, что очень скоро они будут опубликованы и, безусловно, сразу же появятся в русском переводе в качестве продолжения этого издания. Следует также обратить внимание на далеко не всегда стандартные обозначении, которыми пользуется автор. Так же, как и определения, эти обозначения могут появиться в 1-м томе, а вводится во 2-м.
Поэтому без указателя обозначений пользоваться книгой было бы чрезвычайно трудно. Хочу также обратить внимание на запись М, где А— некоторое высказывание. Эта запись встречается в формулах, а иногда и в тексте, и обозначает величину, равную индикатору А. — Профессор Ю. В. Козаченко ПРЕДИСЛОВИЕ /Сулннадня — это искусство, Плагооодная наука; все кулннаоы — джентльмены. — тит ливий, дь «/гье сопл//а ххх«х.и /повв/тт ва/«том, Ада/о«пу ог а/е/алело/у 1.2.2.2) Нлстаящий таы является логическим продолжением материала об информационных структурах, содержащегося в главе 2 тома 1, так как в нем к основным структурным идеям добавляется понятие линейно упорядоченных данных. Название "Сортировка и поиск" может ввести читателя в заблуждение, и он решит, что эта книга предназначена только для тех системных программистов, которые занимаются подготовкой программ сортировки общего назначения илн приложений, выполняющих выборку информации.
Но на самом деле тема сортировки к поиска представляет собой идеальную основу для обсуждения широкого круга зажных общих вопросон. ° Насколько хороши разработанные алгоритмы? в Как улучшить имеющиеся алгоритмы и программы? ° Как с помощью математических методов проанал>«знровать эффективность алгоритмов? ° Как правильно выбрать алгоритм для решения поставленной задачи? ° В каком смысле алгоритм л«ажно считать наилучшим из возможных? ° Какое влияние друг на друга оказывают теория и практика вычислений? ° Как эффективно использовать для больших баэ данных внешние носители информации, такие как магнитные ленты, барабаны и диски? 4а самом деле я считаю, что практически каждый важный аспект программирова«ия возникает в связи с сортировкой и поиском! В данный том входят главы 5 и б, Глава 5 посвящена сортировке в определенном юрядке.
Эта большая тема разделена на две основные части, в которых речь идет > внутренней н внешней сортировке. В главу 5 включены также дополнительные >азделы. В них излагаются вспомогательные теории подстаиовок (раздел 5.1) и >птимвльных методов сортировки (раздел 5.3). В главе 6 изучается проблема поиска >пределенных элементов в таблицах илн файлах. Здесь рассматриваются методы юследовательного поиска, методы сравнения ключей либо цифровых свойств и :ешнрования, а также исследуется более сложная проблема — выборка вторичного ;люча.
Главы 5 и б очень взаимосвязаны между собой; многие их темы аналогичны. В них обсуждается два различных варианта информационных структур (в дополнение к тем, которые рассматривалнсь в главе 2), а именно: очереди с приоритетами (раздел 5.2.3) и линейные списки, представляемые в качестве сбалансированных деревьев (раздел 6.2.3). Как и в тома 1 и 2, в этот том включен большой объем ранее не публиковавшегося материала. Многие рассказывали или писали мне о своих идеях, и я надеюсь, что я не слишком исказил их мысли, выразив их собственными словами.
У меня нет времени иа систематическое изучение патеитоведческой литературы. Кроме того, я осуждаю нынешнюю тенденцию к получению патентов на алгоритмы (раздел 5.4.5). Если кто-либо пришлет мне копию соответствующего патента, на который нет ссылки в данной книге, то я обязательно сделаю такую ссылку' в следующих изданиях. Но все-такн я призываю современных специалистов следовать многовековой математической традиции — делать вновь найденные алгоритмы предметом всеобщего достояния.
Существуют более достойные способы зарабатывания на жизнь, чем нв давать другим пользоватьси своим вкладом в компьютерную науку. Еще будучи преподавателем я использовал данную книгу в качестве учебника для студентов по структурам данных.
Я читал этот курс и на младших, и на старших курсах, опуская ббльшую часть математического материала. В то же время более сложные математические выкладки я испольэовал как основу для курса анализа алгоритмов. который читался иа старших курсах университета (главным об1эаэом, это относится к разделам 5.1, 5.2.2 и 6.4). Курс по сложности вычислений (предназначенный для выпускного курса университета) может быть основан на разделах 5.3 и 5.4.4, а также 4.3.3, 4.6.3 и 4.6.4 тома 2.
Настоящий том, в основном, представляет собой полную и самостоятельную книгу; исключением являются лишь разделы, касающиеся компьютера И1Х, описание которого приведено в томе 1. В приложении Б приведены испачьзованные в данной книге математические обозначения, которые иногда отличаются от принятых в традиционной математической литературе. Предисловие ко второму изданию Это новое издание соответствует третьим изданиям томов 1 и 2.
В них я отметил завершение разработки систем Ч~Х и МЕТйгОг1Т тем, что применил их для набора книг, для которых они были предназначены. Перейдя к электронной версии книги, я получил возможность проверить каждое слово и каждый знак пунктуации в тексте. Я старался сохранить юношеский задор оригинальных предложений и в то же время внести ббльшую зрелость суждений. Были добавлены десятки новых упражнений, а на десятки старых даны новые или улучшенные ответы. Изменения коснулись всего текста, но особенно это относится к разделам 5.1.4 (перестановки и диаграммы), 5.3 (оптимальная сортировка), 5.4.9 (сортировка на диске), 6.2.2 (энтропия), 6.4 (универсальное хеширование) и 6.5 (многомерные деревья).
Ф Таким образом, работа над книгой Искусство программирования продолжается. Исследования получисленных алгоритмов продвигаются с феноменальной ско- растаю. Именно поэтому некоторые разделы данной книги начинаются пиктограммой "В процессе построения" (это своеобразное извинение за то, что приведены не самые новые данные). Например, если бы в настоящее время я читал на последнем курсе университета курс по структурам данных, то я обязательно включил бы обсуждение случайных структур, таких как рандомизиронанвые бинарные деревья поиска и другие.
Но пока я могу только сослаться на основные статьи по этому предмету, а также объявить о написании в будущем раздела 6.2.5. Мои шкафы переполнены важными материалами, которые я планирую включить в окончательное издание тома 3; оно выйдет, вероятно, через 17 лет. Но сначала я должен закончить тома 4 и 5.
Я хочу, чтобы они были опубликованы сразу же„как только будут готовы к печати. Стпанфорд, Калифорния Июль 1997 В. Е. К. Писатель пользуется известными привилегиями, в пользе которых, надеюсь, нет никаких оснований сомневаться. Так, встретив у меня непонятное место, читатель должен предположить, что под ним кроется нечто весьма полезное и глубокомысленное. — дЗКОНАТАН СНИезТ, Сказка бочки, предисловие (1704) * Имеется и аиду оригинал настоящего издания.
— Прям. ред. Я чрезвычайно благодарен сотням людей, которые помогали мне собирать материал в течение последних 35 лет. Большая часть тяжелой работы по подготовке этого нового издания была выполнена Филлис Винклер (РЫ111е %1п(г(ег), которая перенесла текст первого издания в формат ТЕХ, Сильвио Леви (611ч(о Бечу), который профессионально отредактировал текст я полюг подготовить несколько десятков иллюстраций, а также Джеффри Олдхэмом (зег1геу Оыьапз), который конвертировал свьппе 250 оригинальных иллюстраций в формат МЕТЯРОБТ.
Большую помощь, как всегда, оказывали и сотрудники производственного отдела издательства Аг(г(1эопЖеэ! еу. Я исправил все ошибки, которые бдительные читатели обнаружили в первом издании (а также ошибки, которые, увы, не заметил никто), и постарался избежать поняления новых ошибок в новом материале. Теьг не менее я допускаю, что некоторые огрехи все же остались, и хотел бы исправить вх как можно скорее. Поэтому за каждую опечатку*, а также ошибку, относящуюся к сути излагаемого материала или к приведенным историческим сведениям, я охотно заплачу $2,56 тому, кто первым ее найдет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
