Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 2

Теперь же, когда есть множество компьютеров, есть еще больше алгоритмов, и алгоритмы лежат в основе вычислений. Эта книга служит исчерпывающим вводным курсом по современным компьютерным алгоритмам. В ней представлено большое количество конкретных алгоритмов, которые описываются достаточно глубоко, однако таким образом, чтобы разработка и анализ были доступны читателям всех уровней подготовки.

Мы старались обойтись элементарными пояснениями, но при этом не нанести ущерба ни глубине изложения, ни математической строгости. В каждой главе представлен определенный алгоритм и описаны метод его разработки, область применения и другие связанные с ним вопросы. Алгоритмы описываются и простым человеческим языком, и с помощью псевдокода, разработанного таким образом, чтобы быть понятным любому, у кого есть хотя бы минимальный опыт программирования.

В книге представлены 244 рисунка, иллюстрирующих работу алгоритмов, и многие из них состоят из нескольких частей. Поскольку один из важнейших критериев разработки алгоритмов — их эффективность, каждое описание алгоритма включает в себя тщательный анализ времени его работы. Данный учебник предназначен, в первую очередь, для студентов и аспирантов, изучающих тот или иной курс по алгоритмам и структурам данных. Он также будет полезен для технических специалистов, желающих повысить свой уровень в этой области, поскольку описание процесса разработки алгоритмов сопровождается изложением технических и математических вопросов.

В этом, третьем, издании книга вновь существенно изменена. В ней появились новые главы, пересмотренный псевдокод и более активный стиль изложения. Преподавателю Мы составляли эту книгу так, чтобы разнообразие рассматриваемых в ней тем сочеталось с полнотой изложения. Она будет полезной при чтении разнообразных курсов — от курса по структурам данных для студентов до курса по алгоритмам для аспирантов. Поскольку в книге намного больше материала, чем необходимо для обычного курса, рассчитанного на один семестр, можно выбрать только тот материал, который точнее всего соответствует курсу, который вы собираетесь преподавать.

15 Предисловие Курсы удобно разрабатывать на основе отдельных глав. Книга написана так, что ее главы сравнительно независимы одна от другой. В каждой главе материал изложен по мере его усложнения и разбит на разделы. В студенческом курсе можно использовать только сравнительно легкие разделы, а в аспирантском— всю главу в полном объеме.

В книгу вошли 957 упражнений и 158 задач. Упражнения даются в конце каждого раздела, а задачи — в конце каждой главы. Упражнения представлены в виде кратких вопросов для проверки степени освоения материала. Одни из них просты н предназначены для самоконтроля, в то время как другие — посложнее и могут быть рекомендованы в качестве домашних заданий. Решение задач требует больших усилий, и с их помощью часто вводится новый материал. Обычно задачи сформулированы так, что в них содержатся наводящие вопросы, помогающие найти верное решение. Отступив от принятой в предыдущих изданиях практики, мы сделали общедоступными решения ко многим, но не ко всем, задачам и упражнениям. На веб-сайте Ь~Тр: //тИргевв .

в1 ~ . еби/аьдокШнаа / имеются ссылки на эти решения. Вы можете зайти на сайт, чтобы узнать, есть ли решение тех задач, которые вы планируете задать студентам. Ожидается, что со временем набор представленных решений будет понемногу расти, так что мы рекомендуем посещать сайт при каждом очередном чтении вашего курса. Разделы и упраяснения, которые больше подходят для аспирантов, чем для студентов, обозначены звездочкой (*). Они не обязательно сложнее тех, возле которых звездочка отсутствует; просто для их понимания может понадобиться владение более сложным математическим аппаратом.

Для того чтобы справиться с упражнениями со звездочкой, может понадобиться более основательная подготовка или неординарная сообразительность. Студенту Надеемся, что этот учебник станет хорошим введением в теорию алгоритмов. Авторы попытались изложить каждый алгоритм в доступной и увлекательной форме. Чтобы облегчить освоение незнакомых или сложных апгоритмов, каждый из них описывается поэтапно.

В книге также подробно объясняются математические вопросы, необходимые для понимания проводимого анализа алгоритмов. Для тех читателей, которые уже в некоторой мере знакомы с какой-то темой, материал глав организован таким образом, чтобы эти читатели могли опустить вводные разделы и перейти непосредственно к более сложному материалу. Книга получилась довольно большой, поэтому не исключено, что в курсе лекций будет представлена лишь часть изложенного в ней материала. Однако авторы попытались сделать ее такой, чтобы она стала полезной как сейчас в качестве учебника, способствующего усвоению курса лекций, так и позже, в профессиональной деятельности, в качестве настольного справочного пособия для математиков и инженеров.

Ниже перечислены необходимые предпосылки, позволяющие освоить материап этой книги. !6 Предиславие Читатель должен обладать некоторым опытом в программировании. В частности, он должен иметь представление о рекурсивных процедурах и простых структурах данных, таких как массивы и связанные списки.

Читатель должен обладать определенными математическими навыками, в особенности навыками доказательства теорем методом математической индукции. Для понимания некоторых вопросов, изложенных в этой книге, потребуется умение выполнять некоторые простые математические преобразования. Помимо этого, в частях ! и Ч!П рассказывается обо всех используемых математических методах.

Мы получили множество просьб предоставить решения к задачам и упражнениям из книги. На нашем веб-сайте !з~1р://вз11ргеав.т1с.ес!и/ а1дох1кЬтв/ имеются ссылки на решения некоторых задач и упражнений, так что вы запросто можете сравнивать собственные решения с нашими. Однако мы просим вас ие присылать нам свои решения. Профессионалу Широкий круг вопросов, которые излагаются в этой книге, позволяет говорить о том, что она станет прекрасным учебником по теории алгоритмов. Поскольку каждая глава является относительно самостоятельной, читатель сможет сосредоточить внимание на вопросах, интересующих его больше других.

Основная часть обсуждаемых здесь алгоритмов обладает большой практической ценностью. Поэтому не обойдены вниманием особенности реализации алгоритмов и другие инженерные вопросы. Часто предлагаются реальные альтернативы алгоритмам, представляющим преимущественно теоретический интерес. Если вам понадобится реализовать любой из предложенных здесь алгоритмов, вы должны суметь достаточно легко преобразовать приведенный псевдокод в код на вашем любимом языке программирования. Мы разработали псевдокод таким образом, чтобы каждый алгоритм был представлен ясно и лаконично.

Вследствие этого не рассматриваются обработка ошибок и другие связанные с разработкой программного обеспечения вопросы, требующие определенных предположений, касающихся конкретной среды программирования. Авторы попытались представить каждый алгоритм просто и непосредственно, не используя индивидуальных особенностей того или иного языка программирования, что могло бы усложнить понимание сути алгоритма. Мы понимаем, что, работая с книгой, не будучи студентом, вы не сможете проконсультироваться по поводу решения вами задач и упражнений с преподавателем. Поэтому на нашем веб-сайте !зтср://ш1сргеав.т1к.ес!и/ а1дох1кЬюав/ имеются ссылки на решения некоторых задач и упражнений, так что у вас есть возможность проверить свою работу.

Однако мы просим вас не присылать нам свои решения. Коллеге В книге приведена обширная библиография и представлены ссылки на современную литературу. В конце каждой главы есть раздел "Заключительные заме- Предисловие !7 чания", содержащий исторические подробности и ссылки. Однако эти замечания не могут служить исчерпывающим руководством в области алгоритмов. Возможно, в это будет сложно поверить, но даже в такую обьемную книгу не удалось включить многие интересные алгоритмы из-за недостатка места. Несмотря на огромное количество писем от студентов с просьбами предоставить решения задач и упражнений, политика авторов — не приводить ссылки на источники, из которых эти задачи и упражнения были заимствованы. Это сделано для того, чтобы студенты не искали готовых решений в литературе, а решали задачи самостоятельно.

Изменения в третьем издании Что же изменилось в третьем издании книги по сравнению со вторым? Количество этих изменений находится на том же уровне, что и количество изменений во втором издании по сравнению с первым. Как мы писали в предыдущем издании, в зависимости от точки зрения, можно сказать, что их достаточно мало или довольно много. Беглый взгляд на оглавление книги показывает, что большая часть глав и разделов второго издания осталась на месте. Мы убрали нз книги две главы и один раздел, но при этом добавили три новые главы и два новых раздела, помимо этих новых глав. Мы сохранили смешанную схему первых двух изданий. Вместо организации глав в соответствии с проблемной областью задач или в соответствии с методами решения задач, мы использовали оба подхода одновременно. В книге имеются главы, посвященные методу "разделяй и властвуй", динамическому программированию, амортизационному анализу, МР-полноте и приближенным алгоритмам.

Но в ней же есть целые части, посвященные сортировке, структурам данных для динамических множеств и алгоритмам для решения задач на графах. Мы считаем, что, хотя вы и должны знать, как применять методы проектирования и анализа алгоритмов, задачи редко подсказывают, какие именно методы в наибольшей степени подходят для их решения. Вот краткая информация о наиболее существенных изменениях в третьей редакции книги.

Мы добавили новые главы, посвященные деревьям ван Эмде Боаса и многопоточным алгоритмам, и убрали из приложений материал о матрицах. Мы пересмотрели главу, посвященную рекуррентности, в сторону большего охвата метода "разделяй и властвуй" и ее первых двух разделов, посвященных применению этого метода для решения двух задач. Во втором разделе этой главы описан алгоритм Штрассена умножения матриц, которые был перенесен сюда из главы об операциях с матрицами. Мы убрали две главы с достаточно редко изучаемым материалом: биномиальными пирамидами и сортирующими сетями.