Информация о книге

978-5-8459-0857-5, 0-07-013151-1

Главная  » Научно-техническая литература » Информационные технологии. Компьютеры » Программирование » Основы программирования и алгоритмы » Алгоритмы. Построение и анализ

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

INTRODUCTION TO ALGORITHMS
Вильямс, 2011 г., 1296 стр., 978-5-8459-0857-5, 0-07-013151-1 , 240*170*50 мм., тираж: 6000, 2-е


Описание книги

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

Ключевые слова

Поделиться ссылкой на книгу



Дополнительно о книге

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

Содержание книги

Введение 30
Часть I. Основы 43
Глава 1. Роль алгоритмов в вычислениях 46
Глава 2. Приступаем к изучению 57
Глава 3. Рост функций 87
Глава 4. Рекуррентные соотношения 109
Глава 5. Вероятностный анализ и рандомизированные алгоритмы 140
Часть II. Сортировка и порядковая статистика 173
Глава 6. Пирамидальная сортировка 178
Глава 7. Быстрая сортировка 198
Глава 8. Сортировка за линейное время 220
Глава 9. Медианы и порядковые статистики 240
Часть III. Структуры данных 255
Глава 10. Элементарные структуры данных 260
Глава 11. Хеш-таблицы 282
Глава 12. Бинарные деревья поиска 316
Глава 13. Красно-черные деревья 336
Глава 14. Расширение структур данных 365
Часть IV. Усовершенствованные методы разработки и анализа 383
Глава 15. Динамическое программирование 386
Глава 16. Жадные алгоритмы 442
Глава 17. Амортизационный анализ 482
Часть V. Сложные структуры данных 511
Глава 18. B-деревья 515
Глава 19. Биномиальные пирамиды 537
Глава 20. Фибоначчиевы пирамиды 558
Глава 21. Структуры данных для непересекающихся множеств 581
Часть VI. Алгоритмы для работы с графами 607
Глава 22. Элементарные алгоритмы для работы с графами 609
Глава 23. Минимальные остовные деревья 644
Глава 24. Кратчайшие пути из одной вершины 663
Глава 25. Кратчайшие пути между всеми парами вершин 708
Глава 26. Задача о максимальном потоке 734
Часть VII. Избранные темы 795
Глава 27. Сортирующие сети 799
Глава 28. Работа с матрицами 823
Глава 29. Линейное программирование 869
Глава 30. Полиномы и быстрое преобразование Фурье 926
Глава 31. Теоретико-числовые алгоритмы 954
Глава 32. Поиск подстрок 1017
Глава 33. Вычислительная геометрия 1047
Глава 34. NP-полнота 1085
Глава 35. Приближенные алгоритмы 1151
Часть VIII. Приложения: математические основы 1189
Приложение А. Ряды 1191
Приложение Б. Множества и прочие художества 1202
Приложение В. Комбинаторика и теория вероятности 1226
Библиография 1257
Предметный указатель 1277


Об авторе

Кормен Т.
Томас Кормен — профессор, американский специалист по компьютерным наукам, преподаёт в Дартмутском колледже. Также занимает место директора по написанию программ (Writing Program) в этом учреждении. Кормен получил степень бакалавра в Принстоне (1978), магистра (1986) и доктора философии (1992) в Массачусетском технологическом институте. Вместе с Чарльзом Лейзерсоном, Рональдом Ривестом и Клиффордом Штайном он — соавтор знаменитой в среде программистов книги «Алгоритмы: построение и анализ».

Лейзерсон Ч.
Чарльз Эрик Лейзерсон — профессор, американский специалист в области компьютерных наук, информатики. Специализируется на теории параллельных и распределённых вычислений и частично — практическим её применениям. Работая в этом направлении, разработал язык программирования Cilk для многопотоковых вычислений, который использует один из лучших алгоритмов захвата задачи (англ. work-stealing) при планировании.
Он изобрёл топологию «толстое дерево» — универсальную схему сетевого соединения, применяющуюся во многих суперкомпьютерах, в том числе в «Машине соединений» CM5. Лейзерсон помогал в разработке основ теории СБИС — свербольших интегральных схем, в частности метода хронометража для цифровой оптимизации (совместно с Джеймсом Б. Саксом) и систолическими массивами (совместно с К. Ч. Кунгом). Он также предложил идею нетребовательных к кэшу алгоритмов (en:cache-oblivious), которые не имеют настроечных параметров (по размеру и длине строки) для использования кэша, но всё же используют его почти с максимальной эффективностью.
Лейзерсон получил степень бакалавра по компьютерным наукам и математике в Йельском университете в 1975 году, и степень доктора философии по компьютерным наукам в Университете Карнеги — Меллон в 1981, его научными руководителями были Джон Бентли и К. Ч. Кунг.
Позже он перешёл в Массачусетский технологический институт, где сейчас преподаёт. Кроме того, он руководитель исследовательской группы Теории вычислений на Кафедре компьютерных наук и искусственного интеллекта, а раньше он был директором исследовательского отдела компании Akamai Technologies. Он основатель и начальник технологического отдела корпорации Cilk Arts, недавно созданной фирмы по развитию концепции Cilk для многоядерных вычислительных машин.
Диссертация Лейзерсона, «Зонально эффективные вычисления с помощью СБИС» (Area-Efficient VLSI Computation), выиграла первую награду на конкурсе Ассоциации вычислительной техники по докторским диссертациям. В 1985 году Национальный научный фонд США вручил ему «Президентскую награду для молодых исследователей». В 2006 году он получил звание Действительного члена Ассоциации вычислительной техники.
Совместно с Томасом Корменом, Рональдом Ривестом и Клиффордом Штайном, он является автором учебника «Алгоритмы: построение и анализ», которая стала фундаментальным трудом в этой области.

Ривест Р.
Рональд Линн Ривест (род. 1947, Скенектади, Нью-Йорк) — американский специалист по криптографии. Он имеет звание Профессора имени Эндрю и Эрны Витерби по компьютерным наукам на Факультете электротехники и компьютерных наук (EECS) и состоит в штате кафедры CSAIL в Массачусетском технологическом институте.
Ривест — один из авторов алгоритма RSA (вместе с Ади Шамиром и Леонардом Адлеманом), идея алгоритма осенила его ночью после Пасхального седера, в которой участвовала вся троица алгоритма RSA. Он изобрёл такие симметричные алгоритмы шифрования как RC2, RC4, RC5 и принимал участие в разработке RC6 (В RC3 во время разработки обнаружилась уязвимость, RC1 также никогда не был опубликован). Вообще, буквы «RC» означают «шифр Ривеста» (Rivest Cipher) или, неформально, «код Рона» (Ron’s Code). Помимо RC, он автор хэш-функций MD2, MD4, MD5, MD6.
В 2006 году он опубликовал работы по созданию инновационной системы голосования «ThreeBallot», которая предоставляет возможность избирателю удостовериться, что его голос учтён, при этом сохраняя полную конфиденциальность. Что интересно, система никоим образом не относится с криптографией. Ривест опубликовал систему как общественное достояние, под девизом «Наша демократия слишком важна».

Штайн К.
Клиффорд Штайн — профессор, американский специалист в области компьютерных наук. В настоящее время преподаёт в Колумбийском университете (Нью-Йорк), а ранее вёл курсы в Дартмутском колледже (Нью-Гэмпшир). Получил степень бакалавра в Принстоне в 1987 году, магистра — в Массачусетском технологическом институте и доктора философии — там же в 1992.
Он соавтор (вместе с Томасом Корменом, Чарльзом Лейзерсоном и Рональдом Ривестом) второго издания знаменитой в среде программистов книги «Алгоритмы: построение и анализ».

Отзывы

Великолепная книга  [21 April 2013]
Что тут можно говорить, книга просто великолепна. Ее можно начинать читать буквально сразу же после знакомства с основами алгоритмизации и программирования, хотя поначалу далеко не все места в книге будут понятны. Книга очень большая, содержит огромную массу материала по алгоритмам и их анализу. Рекомендую читать ее от корки до корки. Ее освоение потребует значительного количества времени, но при методичном чтении поможет проделать путь от новичка до профессионала и даже после этого к ней можно будет возвращаться снова и снова. Книга обязательно должна лежать на столе у всех, кто интересуется алгоритмизацией и программированием.
Хорошая книга, но требует вдумчивого чтения  [21 April 2013]
Купил книгу, когда занимался олимпиадным программированием. Книга хорошая как по стилю изложения, так и по глубине освещаемых вопросов: приводятся алгоритмы работы с графами, списками, очередями, различными видами деревьев (красно-черными, бинарными, B), алгоритмы сортировки. Помимо этого большое внимание уделяется оценке времени работы алгоритма и его росту в зависимости от размера данных. Видимо для лучшего усвоения излагаемых вопросов авторы используют псевдоязык, похожий на Pascal. Судя по всему, предполагается, что человек, разобравшийся в алгоритме затем легко его реализует на любом выбранном им языке.
Одна из любимых книг  [26 February 2013]
Никогда не считал себя крутым алгоритмистом и не "упарывался" AVL-деревьями и криптографией. И, может быть, именно поэтому мне очень понравилась данная книга. В ней все описано достаточно просто. Изложение строгое, но не занудное. Уделяется внимание составлению у читателя, насколько это возможно, интуитивного представления о каждом алгоритме. В отличие от формального и тяжелого Кнута, эта книга читается достаточно легко. Отдельно отмечу приятное оформление книги: много иллюстраций, крупный шрифт, аккуратный и наглядный псевдокод.
До прочтения книги моя манера писать код временами была несколько сумбурна. После прочтения у меня в памяти отложилось не так уж много конкретных алгоритмов, но код я стал писать намного аккуратней, обращать внимание на вещи, о которых прежде не задумывался (например на граничные условия). В этом по моему мнению и есть главный плюс книги: она помогает навести порядок в голове (вполне умеренными усилиями).
Годится  [26 July 2012]
Хорошая книга. Приятно, что очень низкий входной порог для читателей, при достаточно высоком качестве излагаемого материала. Достаточно знать курс матана, и то не весь (первых двух семестров в тех.вузе будет достаточно) и иметь мозг. Для тех, кто матан подзабудет к моменту начала чтения книги, в приложениях изложен вполне исчерпывающий материал, необходимый для понимания анализа алгоритмов.
Не смотря на всю простоту материала, книга полезна и профессионалам, в качестве справочника. Плюс - имеются усложнённые разделы со звёздочкой (*), для особо жаждующих знаний. Отлично подобраный набор упражнений и задач поможет лучше усвоить материал.
Единственный минус издания (именно издания, не контента) - перевод. Перевод ужасен. Переводы многих математических понятий не соотвтествуют общепринятым (с ходу вспоминается как right triangle перевели как "правильный треугольник". переводчиков даже не смутило, что у "правильного треугольника" в контексте внезапно имелись гипотенуза и катеты). И очень много опечаток. Редактор, судя по всему, отправил книгу в печать, только посмотрев на то, что рисунки в вёрстке отображаются нормально, даже не пытаясь читать.
Отличный учебник.  [27 April 2012]
Замечательная книга. Один из лучших учебников по алгоритмам, что мне попадались. Но требует от читателя некоторых знаний, поэтому для совсем начинающих я бы не стал её рекомендовать. Для остальных же, кто интересуется разработкой алгоритмов и их теоретическими основами к прочтению просто обязательна. Так же осенью издательство обещает выпустить перевод третьего издания.
Очень неплохо.  [ 4 April 2012]
Очень хороший базовый учебник. Такую бы книгу, да объемом раза в три побольше - просто мечта! Все-таки много необходимого и нужного в нее не включено, а надо бы. Для алгоритмистов неплохое подспорье. И конечно, на английском языке. Переводы в последнее время все более пестрят ошибками.
Классика, но...  [29 June 2010]
Несмотря на свой огромный размер, вес и множество рассматриваемых тем, к сожалению, эта книга не избавит от необходимости иметь еще пару книг по алгоритмам, т.к. многим темам не хватает широты охвата. Например, по такой важной теме как сбалансированные двоичные деревья, рассматриваются только "красно-черные" деревья. Возможно они сейчас наиболее популярны, но АВЛ деревья тоже еще встречаются (АВЛ дерево дает лучшую сбалансированность, хотя и более сложными и заратными методами). Справедливости ради хочу отметить, что я еще пока не встречал книги по алгоритмам, которая бы охватывала весь предмет (не теряя при этом в качестве) и могла бы быть _единственной_ книгой по алгоритмам для практикующего программиста :)
Рекомендую  [16 April 2010]
Книга хорошая. Уровень достаточно высокий. Местами читается с трудом, требуется время для "переваривания".

Всем, кто хочет подтянуть свои знания алгоритмов на _серьезный_ уровень.

На мой личный взгляд, не так утомительна, как Кнут.
Ждёмс....  [17 October 2009]
В июне 2010 Вильямс собирается выпустить в свет перевод третьего издания, книга безусловно хороша. Но с переводом, как тут уже отмечали есть действительно проблемы в некоторых местах. Надеюсь со следующим изданием не будет таких проблем. И стоит конечно дорого она, я бы купил эту книгу только если бы цена была меньше 1000 рублей
Рекомендую, но...  [26 September 2007]
...только при наличии англоязычного оригинала. Перевод местами хорош, а местами просто ужасен! Кажется, как будто некоторые участки книги переводил дилетант, абсолютно ничего не смыслящий в данной области! Особенно это касается задач, поэтому, если вы сомневаетесь в корректности условия задачи, обязательно посмотрите в англоязычний вариант, наверняка выяснится, что это очередная "импровизация" переводчика.
Всё это относится именно к этому изданию, про прошлое ничего сказать не могу...

Последние поступления в рубрике "Основы программирования и алгоритмы"



Программирование на visual c# 2013. Учебное пособие для прикладного бакалавриата Программирование на visual c# 2013. Учебное пособие для прикладного бакалавриата Казанский А.

Эта книга предназначена для изучения программирования на одном из самых современных и мощных языков — Visual C# 2013. Язык C# создан для программирования в Windows и вместе со средой разработки IDE Microsoft Visual Studio 2013 позволяет разрабатывать эффективные приложения, имеющие удобный графический интерфейс для решения прикладных задач....

Программирование на языке высокого уровня С/С++. Конспект лекций Программирование на языке высокого уровня С/С++. Конспект лекций Зоткин С.

Приведены основные элементы языков программирования C/C++: типы данных, операторы и операции, структура программы, работа с файлами, основы численных методов решения инженерных задач, организация данных в виде стека, очереди, списка и дерева.Для студентов первого курса бакалавриата направления подготовки 09.03....

Примеры и задачи по программированию на Паскале и Питоне. Фонд оценочных средств для промежуточных аттестаций. Часть 1. Учебное пособие Примеры и задачи по программированию на Паскале и Питоне. Фонд оценочных средств для промежуточных аттестаций. Часть 1. Учебное пособие Пылькин А.Н., Москвина О.П.

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

Если Вы задавались вопросами "где найти книгу в интернете?", "где купить книгу?" и "в каком книжном интернет-магазине нужная книга стоит дешевле?", то наш сайт именно для Вас. На сайте книжной поисковой системы Книгопоиск Вы можете узнать наличие книги Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., Алгоритмы. Построение и анализ в интернет-магазинах. Также Вы можете перейти на страницу понравившегося интернет-магазина и купить книгу на сайте магазина. Учтите, что стоимость товара и его наличие в нашей поисковой системе и на сайте интернет-магазина книг может отличаться, в виду задержки обновления информации.