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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

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

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

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

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

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

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

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

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

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

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

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

Это сделано для того, чтобы студенты не искали готовые решения в литературе, а решали задачи самостоятельно. Изменения во втором издании Какие изменения произошли во втором издании книги? В зависимости от точки зрения, можно сказать, что их достаточно мало или довольно много. Ббльшая часть глав первого издания содержится и во втором издании. Авторы убрали две главы и некоторые разделы, но добавили три новые главы и (кроме них) четыре новых раздела. Если судить об изменениях по оглавлению, то, скорее всего, можно прийти к выводу, что их объем достаточно скромный.

Однако зти изменения далеко выходят за рамки оглавления. Ниже без определенного порядка приводится обзор наиболее значительных изменений во втором издании. ° К коллективу соавторов присоединился Клифф Штайн (С111Т Бге1л). ° Были исправлены ошибки. Сколько их было допущено? Ну, скажем, несколько. ° Появились три новые главы: ° в главе 1 обсуждается роль алгоритмов в вычислениях; ° в главе 5 излагается вероятностный анализ и рандомизированные алгоритмы; в первом издании зта тема упоминается в разных местах книги; ° глава 29 посвящена линейному программированию. ° Что касается глав, которые присутствовали в первом издании, в них добавлены новые разделы по таким вопросам: ° идеальное хеширование (раздел 11.5); ° два приложения динамического программирования (разделы 15.1 и !5.5); ° алгоритмы аппроксимации, в которых применяется рандомизация и линейное программирование (раздел 35.4).

° Чтобы поместить в начальную часть книги больше алгоритмов, три главы по основным разделам математики перенесены из части 1 в приложение (часть ЧП1). ° Добавлено более 40 новых задач и 185 новых упражнений. ° В явном виде были использованы инварианты цикла для доказательства корректности алгоритмов. Первый инвариант цикла используется в главе 2, и в дальнейшем в книге они применяются еще несколько десятков раз. 34 Введение ° Переделаны многие места, где проводится вероятностный анализ. В частности, более десяти раз используется метод "индикаторных случайных величин", упрощающих вероятностный анализ, особенно при наличии зависимости между случайными величинами.

Характеристики

Список файлов книги