Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., Алгоритмы. Построение и анализ
INTRODUCTION TO ALGORITHMSВильямс, 2011 г., 1296 стр., 978-5-8459-0857-5, 0-07-013151-1 , 240*170*50 мм., тираж: 6000, 2-е
Описание книги
Ключевые слова
Поделиться ссылкой на книгу
Дополнительно о книге
Содержание книги
Часть 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.
Он соавтор (вместе с Томасом Корменом, Чарльзом Лейзерсоном и Рональдом Ривестом) второго издания знаменитой в среде программистов книги «Алгоритмы: построение и анализ».
Отзывы
До прочтения книги моя манера писать код временами была несколько сумбурна. После прочтения у меня в памяти отложилось не так уж много конкретных алгоритмов, но код я стал писать намного аккуратней, обращать внимание на вещи, о которых прежде не задумывался (например на граничные условия). В этом по моему мнению и есть главный плюс книги: она помогает навести порядок в голове (вполне умеренными усилиями).
Не смотря на всю простоту материала, книга полезна и профессионалам, в качестве справочника. Плюс - имеются усложнённые разделы со звёздочкой (*), для особо жаждующих знаний. Отлично подобраный набор упражнений и задач поможет лучше усвоить материал.
Единственный минус издания (именно издания, не контента) - перевод. Перевод ужасен. Переводы многих математических понятий не соотвтествуют общепринятым (с ходу вспоминается как right triangle перевели как "правильный треугольник". переводчиков даже не смутило, что у "правильного треугольника" в контексте внезапно имелись гипотенуза и катеты). И очень много опечаток. Редактор, судя по всему, отправил книгу в печать, только посмотрев на то, что рисунки в вёрстке отображаются нормально, даже не пытаясь читать.
Всем, кто хочет подтянуть свои знания алгоритмов на _серьезный_ уровень.
На мой личный взгляд, не так утомительна, как Кнут.
Всё это относится именно к этому изданию, про прошлое ничего сказать не могу...
Последние поступления в рубрике "Основы программирования и алгоритмы"
Программирование на visual c# 2013. Учебное пособие для прикладного бакалавриата Казанский А.
Эта книга предназначена для изучения программирования на одном из самых современных и мощных языков — Visual C# 2013. Язык C# создан для программирования в Windows и вместе со средой разработки IDE Microsoft Visual Studio 2013 позволяет разрабатывать эффективные приложения, имеющие удобный графический интерфейс для решения прикладных задач.... | |
Программирование на языке высокого уровня С/С++. Конспект лекций Зоткин С.
Приведены основные элементы языков программирования C/C++: типы данных, операторы и операции, структура программы, работа с файлами, основы численных методов решения инженерных задач, организация данных в виде стека, очереди, списка и дерева.Для студентов первого курса бакалавриата направления подготовки 09.03.... | |
Примеры и задачи по программированию на Паскале и Питоне. Фонд оценочных средств для промежуточных аттестаций. Часть 1. Учебное пособие Пылькин А.Н., Москвина О.П.
В сборнике рассмотрены примеры разработки алгоритмов и программ по различным разделам программирования. Приведены практические примеры программ на языках Паскаль и Питон. По каждой теме даны наборы заданий различной степени сложности.... |
Если Вы задавались вопросами "где найти книгу в интернете?", "где купить книгу?" и "в каком книжном интернет-магазине нужная книга стоит дешевле?", то наш сайт именно для Вас. На сайте книжной поисковой системы Книгопоиск Вы можете узнать наличие книги Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., Алгоритмы. Построение и анализ в интернет-магазинах. Также Вы можете перейти на страницу понравившегося интернет-магазина и купить книгу на сайте магазина. Учтите, что стоимость товара и его наличие в нашей поисковой системе и на сайте интернет-магазина книг может отличаться, в виду задержки обновления информации.