Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 2
Текст из файла (страница 2)
Но на самом деле тема сортировки и пояска представляет собой идеальную основу для обсуждения широкого круга важных общпх вопросов. к Насколько хороши разработанные алгоритмы? ° Как улучшить имеющиеся алгоритмы и программы? ° Как с помощью математических методов проанализировать эффективность алгоритмов? ° Как правильно выбрать алгоритм для решения поставленной задачи? ° В каком смысле алгоритм можно считать наилучшим из возможных? ° Какое влияние друг на друга оказывают теория и практика вычислений? ° Как эффективно использовать для больших баз данных внешние носители информации, такие как магнитные ленты, барабаны и диски? На самом деле я считаю, что практически каждый важный аспект программирования возникает в связи с сортировкой и поиском! В данный том входят главы 5 и б.
Глава 5 посвящена сортировке в определенном порядке. Эта большая тема разделена на две основные части, в которых речь идет о внутренней и внешней сортировке. В главу 5 включены также дополнительные разделы. В иих язлагшотся вспомогательные теарки подстаиовок (раздел 5,1) н оптимальных методов сортировки (раздел 5.3), В главе б изучаетгл проблема поиска определенных элементов в таблицах или файлах.
Здесь рассматриваются методы последовательного поиска, методы сравнения ключей лябо цифровых свойств и хеширования, а также исследуется более сложная проблема — выборка вторичного ключа. Главы 5 и б очень взаимосвязаны между собой; многие их темы аналогичны. В них обсуждается два различкых варианта информационных структур (в дополнение к тем, которые рассматривались в главе 2), а имеяно: очереди с приоритетами (раздел 5.2.3) и линейные списки, представляемые в качестве сбалансированных деревьев (раздел 6.2.3). Как и в тома 1 и 2, в этот том включен большой объем ранее не публиковавшегося материала.
Многие рассказывали нли писали мне о своих идеях, и я надеюсь, что я не слишком исказил нх мысли, выразив их собственными словами, У меня нет времена на систематическое изучение патентоведческой литературы. Кроме того„я осуждаю нынешнюю тенденцию к получению патентов на алгоритмы (раздел 5.4.5). Если кто-либо пришлет мне копию соответствукицего патента, на который иет ссылки в данной книге, то я обязательно сделаю такую ссылку в следующих изданиях. Но все-таки я призываю современных специалистов следовать многовековой математической традиции — делать вновь найденные алгоритмы предметом всеобщего достояняя.
Существуют более достойные способы зарабатывания иа жизнь. чем не давать другим пользоваться свопм вкладом в компьютерную науку. Еще будучи преподавателем я использовал данную книгу в качестве учебника для студентов по структурам данных. Я читал этот курс и на младших, и иа старших курсах, опуская ббльшую часть математического материала. В то же время более сложные математические выкладки я использовал как основу для курса анализа алгоритмов, который читался на старших курсах университета (главным образом, это относится к разделам 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, В них я отметил завершение разработки систем ЧЕК и МЕТйГОИТ тем, что применил их для набора книг, для которых они были предназначены. Перейдя к электронной версии книги, я получил возможность проверить каждое слово и каждый знак пунктуации в тексте. Я старался сохранить юношеский задор оригинальных предложений и в то же время внести ббльшую зрелость суждений. Были добавлены десятки новых упражнений, а иа десятки старых даны новые или улучшенные ответы.
Изменения коснулись всего текста, но особенно это относится к разделам 5.1.4 (перестановки и дивграммь1), 5.3 (оптимальная сортировка), 5.4.9 (сортировка иа диске), 6.2.2 (энтропия), 6.4 (универсальное хеширование) и 6.5 (многомерные деревья). Ф Таким образом, работа яад книгой Искусство программирования продолжается. Исследования получисленных алгоритмов продвигаются с феноменальной ско- ростью.
Именно поэтому некоторые разделы данной книги начинаются пиктограммой еВ процессе построенияе !это своеобразное извинение за то, что приведены ие самые новые данные). Например, если бы в настоящее время я читал на последнем курсе университета курс по структурам данных, то я обязательно включил бы обсуждение случайных структур, таких как рандомизированные бинарные деревья поиска и другие. Но пока я могу только сослаться на основные статьи по этому предмету, а также объявить о написании в будущем раздела 6.2.5.
Мои шкафы переполнены важными материалами, которые я планирую включить в окончательное издание тома 3; оно выйдет, вероятно, через »7 лет, Но сначала я должен закончить тома 4 и 5, Я хочу, чтобы они бьиш опубликованы сразу же, как только будут готовы к печати. Я чрезвычайно благодарен сотням людей, которые помогали мне собирать материал а течение последних 35 лет.
Большая часть тяжелой работы по подготовке этого нового издания была выполнена Филлис Винклер (Р)з1111я Ыпк!ег), которая перенесла текст первого издания в формат ТБХ, Снльвио Леви 181)тю Бету) „который профессионально отредактпровал текст и помог подготовить несколько десятков иллюстраций, а также Джеффри Олдхэмом 1аейгеу О!г))загп), который конвертировал свыше 250 оригинальных иллюстраций в формат МЕТр!РОЕТ.
Болыпую помощь, как всегда, оказывали и сотрудники производственного отдела издательства Аг)б)эопЖен1еу. Я исправил все ошибки, которые бдительные читатели обнаружили в первом издании (а также ошибки, которые, увы, не заметил никто), и постарался избежать появления новых озпибок в новом материале. Тем не менее я допускаю, что некоторые огрехи все же остались, и хотел бы исправить нх как можно скорее. Поэтому за каждую опечатку*, а также ошибку, относящуюся к сути излагаемого материала или к приведенным историческим сведениям, я охотно заплачу 32,56 тому, кто первым ее найдет. На %еЬ.странице, адрес которой приведен на обложке книги, содержится текущий список всех найденных ошибок н их исправленпй„о которых мне сообщили.
Р. Е. К. Сгпанфорд, Кнлифорни.к Июль 1997 Писатель пользуется мзаестнымм прмемяегмямм, а пользе которы», надеюсь, нет нмкакн» оснований сомнеаагься. Так, астргтмя у меня непонятное место, читатель должен предположить, что под нмм кроется нечто весьма полезное и гяубономысяенное. — джОндтдн СВИФТ, Сказка бочки, предисловие (1704) е Р! нее»ее в виду оригинал настоящего издания.
— - Г!ром. ред, ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ УПРАЖНЕНИЯ, приведенные в этой серии книг, предназначены как для самостоятельной проработка, так и для семинарских занятий. Очень трудно и, наверное, просто невозможно выучить предмет, только читая теорию и не применяя ее для решения конкретных задач, которые заставляют задуматься о прочитанном. Более того, мы лучше всего заучиваем то, до чего дошли самостоятельно, своим умом. Поэтому упражнения занимают нажатию место в данном издании.
Я приложил немало усилий, чтобы сделать их как можно более информативными„а также отобрать задачи, которые были бы не только поучительны, ио и позволяли читателю получить удовольствие от нх решения. Во многих книгах простые упражнения даются вместе с исключительно сложными. Это не всегда удобно, так как читателю хочется знать заранее, сколько времеви ему придется затратить иа решение задач (иначе в лучшем случае ои их только просмотрит). В качестве классического примера подобной ситуации можно привести книгу Ричарда Беллмана [В)сЬагд Вейшап) Динамическое программпрованне (Мд Изд-во иностр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
