Сообщение Re: Кормен и Сэджвик от 01.04.2016 8:00
Изменено 10.04.2016 10:24 LaptevVV
В старом списке были указаны предыдущие издания. С тех пор появились переводы новых изданий.
Кормен.
1. Кормен Т., Лейзерсон Ч., Ривест Р., Стайн К. Алгоритмы: построение и анализ, 3-е изд. — М.: ООО "ИД Вильямс", 2013. — 1328 страниц.
Это МИТовский курс по алгоритмам. В настоящее время считается "библией" — как по объему, так и по качеству изложения.
Курс именно для изучения алгоритмов. Теоретический, а не программистский.
Анализ разных вариантов и случаев — очень подробный, собственно это основное содержание книжки, а отнюдь не сами алгоритмы.
Программ нет ни на каком языке, алгоритмы приводятся на околоматематическом англоязычном псевдокоде.
Но комментарии в алгоритмах — переведены и вполне органично поясняют псевдокод.
МНОГО поясняющих иллюстраций.
Подчеркну: картинки очень хорошо дополняют текст и наглядно показывают работу алгоритма прямо по шагам.
Упражнений достаточно много, но без ответов.
Теорем тоже достаточно много, причем с доказательствами.
7 (семь) частей основного текста и 8 часть — приложения.
35 глав и 4 приложения.
Часть 1. Основы. Тут все математические основы анализа алгоритмов.
Уже глава 2 — серьезный текст, требующий изучения.
Тут рассматривается в качестве примера сортировка вставкой, потом пример ее анализа.
Далее перечисляются методы разработки алгоритмов (разделяй и властвуй и т.п.)
Опять пример (применение метода разделяй и властвуй) — сортировки слиянием.
Поясняющие картинки хороши.
Глава 3 — Рост функций.
Важная глава, без которой дальше анализ понять будет затруднительно.
Глава 4. Разделяй и властвуй — тут о методах решений рекуррентных соотношений.
И основная теорема — тут. С доказательствами, естественно.
И задачи тоже рассматриваются.
В частности, алгоритм Штрассена для умножения матриц как иллюстрация метода разделяй и властвуй.
Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
Название говорит само за себя. Индикаторные случайные величины — со всех сторон...
В частности тут рассматривается парадокс дней рождений.
Собственно алгоритмы начинаются с части 2. Сортировка и порядковая статистика.
— двоичная пирамида, пирамидальная сортировка и очередь с приоритетами
— быстрая сортировка
— сортировка за линейное время (подсчетом, поразрядная, карманнная — которая блочная)
— медианы и порядковые статистики
Опять же — все с картинками, которые весьма хорошо поясняют алгоритмы.
Все простые структуры данных — в части 3.
Стеки, очереди, списки, хеш-таблицы, бинарные деревья, балансированные деревья — это здесь (ну, и еще деревья отрезков).
Естественно, с подробнейшим анализом.
Балансированные деревья — красно-черные. АВЛ не рассматриваются.
Часть 4 - это методы.
— Динамическое программирование.
— Жадные алгоритмы.
Динамическое программирование рассматривается подробнейшим образом.
Сначала на задаче разрезания стержня (во 2 издании была другая задача — о работе конвейера по обработке неких деталей)
Потом классика: расстановка скобок при умножении ряда матриц.
Тут же — наидлиннейшая общая последовательность.
И опять же здесь же — оптимальные двоичные деревья.
Ничего лучше я про динамическое программирование не читал.
Кстати, среди задач к данной главе:
— расстояние редактирования
— алгоритм Виттерби (распознавания речи)
— масштабирование изображений
и еще много чего.
Жадные алгоритмы — задача планирования процессов.
Здесь же коды Хаффмена.
Матроиды — здесь (тут я чайник).
И рассматривается задача планирования как матроид.
Ну, и в этой же части — амортизационный анализ(групповой, метод бухучета, метод потенцалов)
Часть 5 — сложные структуры данных.
Тут В-деревья (что есть почти во всех других учебниках).
А чего мне не встречалось:
— Фибоначчевы пирамиды подробнейшим образом.
— деревья ван Эмде Боаса. Этого совсем нигде не видел, но написано,
что любая операция (вставка, удаление, поиск и т.п.) на этом дереве выполняется за О(lglgN) — в наихудшем случае!
Ну, и структуры для непересекающихся множеств.
Пишут, что в некоторых задачах выполняется группировка n объектов в набор непересекающихся множеств.
И две основные операции: поиск множества с заданным элементом и объединение двух множеств.
Предлагается рассмотреть структуры данных для этих операций.
Часть 6 — это графы.
Вся классика: обходы, кратчайшие пути, остовные деревья, потоки в сетях.
А вот часть 7 - самая большая. И тут собрано все, что не вошло в предыдущие части.
По сравнению с предыдущим изданием здесь появились многопоточные алгоритмы (глава 27).
Рассматривается многопоточное умножение матриц и многопоточная сортировка слиянием.
Глава 28 — решение систем линейных уравнений. Здесь и обращение матриц и метод наименьших квадратов.
Глава 29 — Линейное программирование.
Ну, в этой части и быстрое преобразование Фурье (30), и числовые алгоритмы (31 — это пересекается со 2 томом Кнута: модульная арифметика, китайская теорема об остатках, целочисленное разлоржение, проверка простоты, криптосистемы с открытым ключом...)
В этой части (32 глава) и алгоритмы поиска подстрок (Рабина-Карпа, конечный автомат, Кнута-Морриса-Пратта)
Вычислительная геометрия на примере поиска выпуклой оболочки и поиске пары ближайших точек.
NP-полнота — глава 34.
И в 35 главе — приближенные алгоритмы на нескольких задачах (коммивояжера, вершинное покрытие графа и других)
В общем, том — впечатляет.
Видимо столкнувшись с тем, что народ с трудом осваивает этот фолиант, Кормен написал книжку алгоритмов для чайников...
2. Кормен Т. Алгоритмы: вводный курс. — М.: ООО "ИД Вильямс", 2014. — 208 страниц
http://www.ozon.ru/context/detail/id/24903185/
На озоне содержание есть, поэтому просто приведу мой отзыв с Озона:
И опять же — много картинок. А вот заданий нет совсем.
Еще добавлю, что в главе по сжатию есть не только Хаффмен, но и Лемпель-Зив.
Роберт Сэджвик.
1. Сэджвик Р. Алгоритмы на С++. — М.: ООО "И.Д. Вильямс", 2011. — 1056 сраниц.
Название говорит само за себя: курс алгоритмов с прогами на С++.
Материал построен именно от программ, а не от математики.
Все программы, которые я проверял, — все работали без ошибок.
Упражнений и заданий — дофига, но ответов не приводится.
По содержанию — книга состоит из 5 частей
1. Анализ
2. Структуры данных
3. Сортировка
4. Поиск
5. Алгоритмы на графах.
В первой части — математики самый минимум.
Только то, что реально необходимо на практике для оценки О() алгоритма.
Рассматривается практически на примерах. Теоремы отсутствуют как класс...
Только оценка быстродействия последовательного поиска сформулирована как 2 леммы.
И тут же — бинарный поиск.
Про рекуррентные соотношения — чуть-чуть формул. И название — программерское: Простейшие рекурсии...
Ну, и рост функций — опять же чисто с практической стороны.
В общем — как раз для программистов, которые математику не любят, а оценивать быстродействие алгоритмов как-то надо.
Вторая часть — опять же соответствует названию.
Глава 3. Элементарные структуры данных.
Начинает про типы данных, числа, функции.
Продолжает: массивы и связные списки.
Для списков сразу определяет структуру node с конструктором и typedef node * link;
Потом — все операции со списками. Все — с картинками. Все присвоения указателей — на картинках.
Сортировка метолом вставки в список.
И (ВНИМАНИЕ! ) задача обращения списка — маленькая функция из 5 строчек... 
!
Задача Иосифа и циклические списки — тоже здесь.
Потом — выделение памяти для списка.
Маленький простейший аллокатор для узлов списка на основе динамического массива.
Потом — строки и минимум информации про них.
А потом — использование массивов и списков для представления графов: матрица смежности, список списков.
Глава 4. Абстрактные типы данных.
Тут начинается применение классов для реализации АТД.
Сначала рассказывается про классы. И кстати, шаблоны — тоже тут.
А потом рассматривается стек и показывается его использование. В частности: польская запись.
Потом показывается реализация стека на массиве и на списке.
Потом, естественно, очередь...
Ну, и попутно рассматриваются еще примеры.
АТД первого класса — это реализованные типы, которые можно использовать в программе точно так же, как встроенные.
Это Сэджвик такое определение дает и приводит примеры реализации таких чисел.
В конце — класс полиномов.
Четко разделяет интерфейс и реализацию.
Глава 5. Рекурсия.
Глава — хороша для студентов.
Просто и понятно объясняются рекурсивные функции на массе примеров.
Даже поиск максимума в массиве сделан рекурсивным способом — весьма показательно о том,
что даже чисто итеративные задачи вполне себе можно рекурсивно писать...
Естественно, ханойские башни.
Хорошо описывается прием "разделяй и властвуй" при решении задач рекурсивным способом.
А далее — динамическое программирование.
Рассматривается вычисление чисел Фибоначчи и задача о рюкзаке двумя способами: рекурсивный и динамическое программирование.
Потом — деревья. Всякие, не только двоичные.
Но математические свойства — для бинарных деревьев описываются.
Ну, а потом — обходы деревьев (и другие алгоритмы на бинарных деревьях — рекурсивные;
в частности, построение дерева синтаксического анализа)
и графов (в глубину — рекурсивный, и в ширину — не рекурсивный).
Хорошая глава для начинающих.
Третья часть — сортировки.
Это классика, поэтому просто перечислю, что здесь есть:
— элементарные сортировки;
— быстрая (достаточно подробно несколько вариантов; и тут же — медиана)
— слияние (много разных слияний; сортировка списков слиянием; связь с рекурсией)
— пирамидальная (и очереди с приоритетами)
— поразрядная (восходящая и нисходящая)
— специальные (Бэтчер, сети сортировки, внешняя, параллельное слияние)
В первой главе этой части — много всего.
Кроме выбора, вставок и пузырька там же еще и сортировка Шелла, и сортировка списков.
И еще сортировка не самих элементов, а индексов и указателей.
Ну, и тут же — сортировка подсчетом (в связи с сортировкой индексов)
И, естественно, характеристики производительности сортировок (не сам математический анализ, а именно уже посчитанные О() ).
В общем — хорошо написано, мне нравится.
Четвертая часть — это
Кормен.
1. Кормен Т., Лейзерсон Ч., Ривест Р., Стайн К. Алгоритмы: построение и анализ, 3-е изд. — М.: ООО "ИД Вильямс", 2013. — 1328 страниц.
Это МИТовский курс по алгоритмам. В настоящее время считается "библией" — как по объему, так и по качеству изложения.
Курс именно для изучения алгоритмов. Теоретический, а не программистский.
Анализ разных вариантов и случаев — очень подробный, собственно это основное содержание книжки, а отнюдь не сами алгоритмы.
Программ нет ни на каком языке, алгоритмы приводятся на околоматематическом англоязычном псевдокоде.
Но комментарии в алгоритмах — переведены и вполне органично поясняют псевдокод.
МНОГО поясняющих иллюстраций.
Подчеркну: картинки очень хорошо дополняют текст и наглядно показывают работу алгоритма прямо по шагам.
Упражнений достаточно много, но без ответов.
Теорем тоже достаточно много, причем с доказательствами.
7 (семь) частей основного текста и 8 часть — приложения.
35 глав и 4 приложения.
Часть 1. Основы. Тут все математические основы анализа алгоритмов.
Уже глава 2 — серьезный текст, требующий изучения.
Тут рассматривается в качестве примера сортировка вставкой, потом пример ее анализа.
Далее перечисляются методы разработки алгоритмов (разделяй и властвуй и т.п.)
Опять пример (применение метода разделяй и властвуй) — сортировки слиянием.
Поясняющие картинки хороши.
Глава 3 — Рост функций.
Важная глава, без которой дальше анализ понять будет затруднительно.
Глава 4. Разделяй и властвуй — тут о методах решений рекуррентных соотношений.
И основная теорема — тут. С доказательствами, естественно.
И задачи тоже рассматриваются.
В частности, алгоритм Штрассена для умножения матриц как иллюстрация метода разделяй и властвуй.
Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
Название говорит само за себя. Индикаторные случайные величины — со всех сторон...
В частности тут рассматривается парадокс дней рождений.
Собственно алгоритмы начинаются с части 2. Сортировка и порядковая статистика.
— двоичная пирамида, пирамидальная сортировка и очередь с приоритетами
— быстрая сортировка
— сортировка за линейное время (подсчетом, поразрядная, карманнная — которая блочная)
— медианы и порядковые статистики
Опять же — все с картинками, которые весьма хорошо поясняют алгоритмы.
Все простые структуры данных — в части 3.
Стеки, очереди, списки, хеш-таблицы, бинарные деревья, балансированные деревья — это здесь (ну, и еще деревья отрезков).
Естественно, с подробнейшим анализом.
Балансированные деревья — красно-черные. АВЛ не рассматриваются.
Часть 4 - это методы.
— Динамическое программирование.
— Жадные алгоритмы.
Динамическое программирование рассматривается подробнейшим образом.
Сначала на задаче разрезания стержня (во 2 издании была другая задача — о работе конвейера по обработке неких деталей)
Потом классика: расстановка скобок при умножении ряда матриц.
Тут же — наидлиннейшая общая последовательность.
И опять же здесь же — оптимальные двоичные деревья.
Ничего лучше я про динамическое программирование не читал.
Кстати, среди задач к данной главе:
— расстояние редактирования
— алгоритм Виттерби (распознавания речи)
— масштабирование изображений
и еще много чего.
Жадные алгоритмы — задача планирования процессов.
Здесь же коды Хаффмена.
Матроиды — здесь (тут я чайник).
И рассматривается задача планирования как матроид.
Ну, и в этой же части — амортизационный анализ(групповой, метод бухучета, метод потенцалов)
Часть 5 — сложные структуры данных.
Тут В-деревья (что есть почти во всех других учебниках).
А чего мне не встречалось:
— Фибоначчевы пирамиды подробнейшим образом.
— деревья ван Эмде Боаса. Этого совсем нигде не видел, но написано,
что любая операция (вставка, удаление, поиск и т.п.) на этом дереве выполняется за О(lglgN) — в наихудшем случае!
Ну, и структуры для непересекающихся множеств.
Пишут, что в некоторых задачах выполняется группировка n объектов в набор непересекающихся множеств.
И две основные операции: поиск множества с заданным элементом и объединение двух множеств.
Предлагается рассмотреть структуры данных для этих операций.
Часть 6 — это графы.
Вся классика: обходы, кратчайшие пути, остовные деревья, потоки в сетях.
А вот часть 7 - самая большая. И тут собрано все, что не вошло в предыдущие части.
По сравнению с предыдущим изданием здесь появились многопоточные алгоритмы (глава 27).
Рассматривается многопоточное умножение матриц и многопоточная сортировка слиянием.
Глава 28 — решение систем линейных уравнений. Здесь и обращение матриц и метод наименьших квадратов.
Глава 29 — Линейное программирование.
Ну, в этой части и быстрое преобразование Фурье (30), и числовые алгоритмы (31 — это пересекается со 2 томом Кнута: модульная арифметика, китайская теорема об остатках, целочисленное разлоржение, проверка простоты, криптосистемы с открытым ключом...)
В этой части (32 глава) и алгоритмы поиска подстрок (Рабина-Карпа, конечный автомат, Кнута-Морриса-Пратта)
Вычислительная геометрия на примере поиска выпуклой оболочки и поиске пары ближайших точек.
NP-полнота — глава 34.
И в 35 главе — приближенные алгоритмы на нескольких задачах (коммивояжера, вершинное покрытие графа и других)
В общем, том — впечатляет.
Видимо столкнувшись с тем, что народ с трудом осваивает этот фолиант, Кормен написал книжку алгоритмов для чайников...
2. Кормен Т. Алгоритмы: вводный курс. — М.: ООО "ИД Вильямс", 2014. — 208 страниц
http://www.ozon.ru/context/detail/id/24903185/
На озоне содержание есть, поэтому просто приведу мой отзыв с Озона:
Добавлю, что алгоритмы написаны в стиле Кнута: по шагам на русском языке.Книга — для студентов, 26 февраля 2014 г.
Кормен написал маленькую книжку, как я понял, специально для студентов, которые не хотят (или не могут) освоить его основной труд — "библию" по алгоритмам. В книге всего 10 глав, тем не менее, в книге затронуты многие вопросы построения хороших алгоритмов. Математики (то есть анализа алгоритмов) практически нет.
Кормен, понимая, с каким читателем имеет дело, сразу написал: Я не знаю, чему может научить вас эта книга...
Как преподаватель могу его только поддержать: научить человека чему-нибудь — невозможно. Человек может только САМ научиться. В этом смысле книжка дает разгон для того, чтобы после нее все же решиться и прочитать основной труд Кормена по алгоритмам.
Рекомендую студентам (и преподавателям).
И опять же — много картинок. А вот заданий нет совсем.
Еще добавлю, что в главе по сжатию есть не только Хаффмен, но и Лемпель-Зив.
Роберт Сэджвик.
1. Сэджвик Р. Алгоритмы на С++. — М.: ООО "И.Д. Вильямс", 2011. — 1056 сраниц.
Название говорит само за себя: курс алгоритмов с прогами на С++.
Материал построен именно от программ, а не от математики.
Все программы, которые я проверял, — все работали без ошибок.
Упражнений и заданий — дофига, но ответов не приводится.
По содержанию — книга состоит из 5 частей
1. Анализ
2. Структуры данных
3. Сортировка
4. Поиск
5. Алгоритмы на графах.
В первой части — математики самый минимум.
Только то, что реально необходимо на практике для оценки О() алгоритма.
Рассматривается практически на примерах. Теоремы отсутствуют как класс...
Только оценка быстродействия последовательного поиска сформулирована как 2 леммы.
И тут же — бинарный поиск.
Про рекуррентные соотношения — чуть-чуть формул. И название — программерское: Простейшие рекурсии...
Ну, и рост функций — опять же чисто с практической стороны.
В общем — как раз для программистов, которые математику не любят, а оценивать быстродействие алгоритмов как-то надо.
Вторая часть — опять же соответствует названию.
Глава 3. Элементарные структуры данных.
Начинает про типы данных, числа, функции.
Продолжает: массивы и связные списки.
Для списков сразу определяет структуру node с конструктором и typedef node * link;
Потом — все операции со списками. Все — с картинками. Все присвоения указателей — на картинках.
Сортировка метолом вставки в список.
И (ВНИМАНИЕ!
) задача обращения списка — маленькая функция из 5 строчек... ! Задача Иосифа и циклические списки — тоже здесь.
Потом — выделение памяти для списка.
Маленький простейший аллокатор для узлов списка на основе динамического массива.
Потом — строки и минимум информации про них.
А потом — использование массивов и списков для представления графов: матрица смежности, список списков.
Глава 4. Абстрактные типы данных.
Тут начинается применение классов для реализации АТД.
Сначала рассказывается про классы. И кстати, шаблоны — тоже тут.
А потом рассматривается стек и показывается его использование. В частности: польская запись.
Потом показывается реализация стека на массиве и на списке.
Потом, естественно, очередь...
Ну, и попутно рассматриваются еще примеры.
АТД первого класса — это реализованные типы, которые можно использовать в программе точно так же, как встроенные.
Это Сэджвик такое определение дает и приводит примеры реализации таких чисел.
В конце — класс полиномов.
Четко разделяет интерфейс и реализацию.
Глава 5. Рекурсия.
Глава — хороша для студентов.
Просто и понятно объясняются рекурсивные функции на массе примеров.
Даже поиск максимума в массиве сделан рекурсивным способом — весьма показательно о том,
что даже чисто итеративные задачи вполне себе можно рекурсивно писать...
Естественно, ханойские башни.
Хорошо описывается прием "разделяй и властвуй" при решении задач рекурсивным способом.
А далее — динамическое программирование.
Рассматривается вычисление чисел Фибоначчи и задача о рюкзаке двумя способами: рекурсивный и динамическое программирование.
Потом — деревья. Всякие, не только двоичные.
Но математические свойства — для бинарных деревьев описываются.
Ну, а потом — обходы деревьев (и другие алгоритмы на бинарных деревьях — рекурсивные;
в частности, построение дерева синтаксического анализа)
и графов (в глубину — рекурсивный, и в ширину — не рекурсивный).
Хорошая глава для начинающих.
Третья часть — сортировки.
Это классика, поэтому просто перечислю, что здесь есть:
— элементарные сортировки;
— быстрая (достаточно подробно несколько вариантов; и тут же — медиана)
— слияние (много разных слияний; сортировка списков слиянием; связь с рекурсией)
— пирамидальная (и очереди с приоритетами)
— поразрядная (восходящая и нисходящая)
— специальные (Бэтчер, сети сортировки, внешняя, параллельное слияние)
В первой главе этой части — много всего.
Кроме выбора, вставок и пузырька там же еще и сортировка Шелла, и сортировка списков.
И еще сортировка не самих элементов, а индексов и указателей.
Ну, и тут же — сортировка подсчетом (в связи с сортировкой индексов)
И, естественно, характеристики производительности сортировок (не сам математический анализ, а именно уже посчитанные О() ).
В общем — хорошо написано, мне нравится.
Четвертая часть — это
Re: Кормен и Сэджвик
В старом списке были указаны предыдущие издания. С тех пор появились переводы новых изданий.
Кормен.
1. Кормен Т., Лейзерсон Ч., Ривест Р., Стайн К. Алгоритмы: построение и анализ, 3-е изд. — М.: ООО "ИД Вильямс", 2013. — 1328 страниц.
Это МИТовский курс по алгоритмам. В настоящее время считается "библией" — как по объему, так и по качеству изложения.
Курс именно для изучения алгоритмов. Теоретический, а не программистский.
Анализ разных вариантов и случаев — очень подробный, собственно это основное содержание книжки, а отнюдь не сами алгоритмы.
Программ нет ни на каком языке, алгоритмы приводятся на околоматематическом англоязычном псевдокоде.
Но комментарии в алгоритмах — переведены и вполне органично поясняют псевдокод.
МНОГО поясняющих иллюстраций.
Подчеркну: картинки очень хорошо дополняют текст и наглядно показывают работу алгоритма прямо по шагам.
Упражнений достаточно много, но без ответов.
Теорем тоже достаточно много, причем с доказательствами.
7 (семь) частей основного текста и 8 часть — приложения.
35 глав и 4 приложения.
Часть 1. Основы. Тут все математические основы анализа алгоритмов.
Уже глава 2 — серьезный текст, требующий изучения.
Тут рассматривается в качестве примера сортировка вставкой, потом пример ее анализа.
Далее перечисляются методы разработки алгоритмов (разделяй и властвуй и т.п.)
Опять пример (применение метода разделяй и властвуй) — сортировки слиянием.
Поясняющие картинки хороши.
Глава 3 — Рост функций.
Важная глава, без которой дальше анализ понять будет затруднительно.
Глава 4. Разделяй и властвуй — тут о методах решений рекуррентных соотношений.
И основная теорема — тут. С доказательствами, естественно.
И задачи тоже рассматриваются.
В частности, алгоритм Штрассена для умножения матриц как иллюстрация метода разделяй и властвуй.
Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
Название говорит само за себя. Индикаторные случайные величины — со всех сторон...
В частности тут рассматривается парадокс дней рождений.
Собственно алгоритмы начинаются с части 2. Сортировка и порядковая статистика.
— двоичная пирамида, пирамидальная сортировка и очередь с приоритетами
— быстрая сортировка
— сортировка за линейное время (подсчетом, поразрядная, карманнная — которая блочная)
— медианы и порядковые статистики
Опять же — все с картинками, которые весьма хорошо поясняют алгоритмы.
Все простые структуры данных — в части 3.
Стеки, очереди, списки, хеш-таблицы, бинарные деревья, балансированные деревья — это здесь (ну, и еще деревья отрезков).
Естественно, с подробнейшим анализом.
Балансированные деревья — красно-черные. АВЛ не рассматриваются.
Часть 4 - это методы.
— Динамическое программирование.
— Жадные алгоритмы.
Динамическое программирование рассматривается подробнейшим образом.
Сначала на задаче разрезания стержня (во 2 издании была другая задача — о работе конвейера по обработке неких деталей)
Потом классика: расстановка скобок при умножении ряда матриц.
Тут же — наидлиннейшая общая последовательность.
И опять же здесь же — оптимальные двоичные деревья.
Ничего лучше я про динамическое программирование не читал.
Кстати, среди задач к данной главе:
— расстояние редактирования
— алгоритм Виттерби (распознавания речи)
— масштабирование изображений
и еще много чего.
Жадные алгоритмы — задача планирования процессов.
Здесь же коды Хаффмена.
Матроиды — здесь (тут я чайник).
И рассматривается задача планирования как матроид.
Ну, и в этой же части — амортизационный анализ(групповой, метод бухучета, метод потенцалов)
Часть 5 — сложные структуры данных.
Тут В-деревья (что есть почти во всех других учебниках).
А чего мне не встречалось:
— Фибоначчевы пирамиды подробнейшим образом.
— деревья ван Эмде Боаса. Этого совсем нигде не видел, но написано,
что любая операция (вставка, удаление, поиск и т.п.) на этом дереве выполняется за О(lglgN) — в наихудшем случае!
Ну, и структуры для непересекающихся множеств.
Пишут, что в некоторых задачах выполняется группировка n объектов в набор непересекающихся множеств.
И две основные операции: поиск множества с заданным элементом и объединение двух множеств.
Предлагается рассмотреть структуры данных для этих операций.
Часть 6 — это графы.
Вся классика: обходы, кратчайшие пути, остовные деревья, потоки в сетях.
А вот часть 7 - самая большая. И тут собрано все, что не вошло в предыдущие части.
По сравнению с предыдущим изданием здесь появились многопоточные алгоритмы (глава 27).
Рассматривается многопоточное умножение матриц и многопоточная сортировка слиянием.
Глава 28 — решение систем линейных уравнений. Здесь и обращение матриц и метод наименьших квадратов.
Глава 29 — Линейное программирование.
Ну, в этой части и быстрое преобразование Фурье (30), и числовые алгоритмы (31 — это пересекается со 2 томом Кнута: модульная арифметика, китайская теорема об остатках, целочисленное разлоржение, проверка простоты, криптосистемы с открытым ключом...)
В этой части (32 глава) и алгоритмы поиска подстрок (Рабина-Карпа, конечный автомат, Кнута-Морриса-Пратта)
Вычислительная геометрия на примере поиска выпуклой оболочки и поиске пары ближайших точек.
NP-полнота — глава 34.
И в 35 главе — приближенные алгоритмы на нескольких задачах (коммивояжера, вершинное покрытие графа и других)
В общем, том — впечатляет.
Видимо столкнувшись с тем, что народ с трудом осваивает этот фолиант, Кормен написал книжку алгоритмов для чайников...
2. Кормен Т. Алгоритмы: вводный курс. — М.: ООО "ИД Вильямс", 2014. — 208 страниц
http://www.ozon.ru/context/detail/id/24903185/
На озоне содержание есть, поэтому просто приведу мой отзыв с Озона:
И опять же — много картинок. А вот заданий нет совсем.
Еще добавлю, что в главе по сжатию есть не только Хаффмен, но и Лемпель-Зив.
Роберт Сэджвик.
1. Сэджвик Р. Алгоритмы на С++. — М.: ООО "И.Д. Вильямс", 2011. — 1056 сраниц.
Эта книжка — для программистов.
Математики практически нет.
Зато много картинок, поясняющих алгоритмы.
И все алгоритмы представлены С++программами. Где в виде функцуий, а где и полноценные классы.
Все программы, которые я проверял — работают.
Однако
#include <iostream.h>
#include <math.h>
Упражнений — дофига.
Но ответов нет.
В оглавлении прописано 5 частей:
1. Анализ
2. Структуры данных
3. Сортировка
4. Поиск
5. Алгоритмы на графах.
Однако в параграфе 1.5 упоминаются еще части:
6. Строки
7. Геометрические алгоритмы
8. Дополнительные главы.
Написано, что эти части (как и графы) — в отдельных книжках.
Но мне не встречались переводы этих частей для С++.
Строки довольно подробно описаны в другой книжке Сэджвика (см. ниже).
В первой части — математики самый минимум.
Только то, что реально необходимо на практике для оценки О() алгоритма.
Рассматривается практически на примерах. Теоремы отсутствуют как класс...
Только оценка быстродействия последовательного поиска сформулирована как 2 леммы.
И тут же — бинарный поиск.
Про рекуррентные соотношения — чуть-чуть формул. И название — программерское: Простейшие рекурсии...
Ну, и рост функций — опять же чисто с практической стороны.
В общем — как раз для программистов, которые математику не любят, а оценивать быстродействие алгоритмов как-то надо.
Вторая часть — опять же соответствует названию.
Глава 3. Элементарные структуры данных.
Начинает про типы данных, числа, функции.
Продолжает: массивы и связные списки.
Для списков сразу определяет структуру node с конструктором и typedef node * link;
Потом — все операции со списками. Все — с картинками. Все присвоения указателей — на картинках.
Сортировка метолом вставки в список.
И (ВНИМАНИЕ! ) задача обращения списка — маленькая функция из 5 строчек... !
Задача Иосифа и циклические списки — тоже здесь.
Потом — выделение памяти для списка.
Маленький простейший аллокатор для узлов списка на основе динамического массива.
Потом — строки и минимум информации про них.
А потом — использование массивов и списков для представления графов: матрица смежности, список списков.
Глава 4. Абстрактные типы данных.
Тут начинается применение классов для реализации АТД.
Сначала рассказывается про классы. И кстати, шаблоны — тоже тут.
А потом рассматривается стек и показывается его использование. В частности: польская запись.
Потом показывается реализация стека на массиве и на списке.
Потом, естественно, очередь...
Ну, и попутно рассматриваются еще примеры.
АТД первого класса — это реализованные типы, которые можно использовать в программе точно так же, как встроенные.
Это Сэджвик такое определение дает и приводит примеры реализации таких чисел.
В конце — класс полиномов.
Четко разделяет интерфейс и реализацию.
Глава 5. Рекурсия.
Глава — хороша для студентов.
Просто и понятно объясняются рекурсивные функции на массе примеров.
Даже поиск максимума в массиве сделан рекурсивным способом — весьма показательно о том,
что даже чисто итеративные задачи вполне себе можно рекурсивно писать...
Естественно, ханойские башни.
Хорошо описывается прием "разделяй и властвуй" при решении задач рекурсивным способом.
А далее — динамическое программирование.
Рассматривается вычисление чисел Фибоначчи и задача о рюкзаке двумя способами: рекурсивный и динамическое программирование.
Потом — деревья. Всякие, не только двоичные.
Но математические свойства — для бинарных деревьев описываются.
Ну, а потом — обходы деревьев (и другие алгоритмы на бинарных деревьях — рекурсивные;
в частности, построение дерева синтаксического анализа)
и графов (в глубину — рекурсивный, и в ширину — не рекурсивный).
Хорошая глава для начинающих.
Третья часть — сортировки.
Это классика, поэтому просто перечислю, что здесь есть:
— элементарные сортировки;
— быстрая (достаточно подробно несколько вариантов; и тут же — медиана)
— слияние (много разных слияний; сортировка списков слиянием; связь с рекурсией)
— пирамидальная (и очереди с приоритетами)
— поразрядная (восходящая и нисходящая)
— специальные (Бэтчер, сети сортировки, внешняя, параллельное слияние)
В первой главе этой части — много всего.
Кроме выбора, вставок и пузырька там же еще и сортировка Шелла, и сортировка списков.
И еще сортировка не самих элементов, а индексов и указателей.
Ну, и тут же — сортировка подсчетом (в связи с сортировкой индексов)
И, естественно, характеристики производительности сортировок (не сам математический анализ, а именно уже посчитанные О() ).
В общем — хорошо написано, мне нравится.
Часть 4. Поиск.
Сначала определяется АТД таблицы символов — шаблон класса.
И реализация таблицы на массиве и на списке
А потом всякие поиски: последовательный (на упорядоченнном и нет контейнере), бинарный поиск — подробно.
Потом — дереья бинарного поиска (таблица символов опять — на дереве)
и много-много про действия с бинарными деревьями.
глава 13 — балансированные деревьЯ.
Тут много разных видов: скошенные (косые), нисходящие 2-3-4-деревья, красно-черные.
И тут же — слоеные списки. Больше нигде не встречал.
Глава 14 — Хеширование.
Кроме классики (хеш-функции, коллизии) тут есть динамические хеш-таблицы.
Глава 15. Поразрядный поиск.
Тут — деревья цифрового поиска (digital search tree — dst), trie-деревья, patricia-деревья.
И более сложные структуры: многопутевые trie-деревья и tst-деревья.
Глава 16. Внешний поиск.
Индесно-последовательный доступ и В-деревья...
Расширяемое хещирование — альтернатива В-деревку. Вроде тоже нигде в учебниках не писали про это.
Часть 5. Графы.
Ну, графы — они и есть графы.
Кроме классики (поиск (подробности обходов, компоненты связности), кратчайшие пути,
остовные деревья, потоки в сетях) есть генерация графов.
И довольно много про ациклические графы (direct acyclic graph-dag)
В общем добротная такая часть для программистов.
Еще раз подчеркну: все алгоритмы — на С++ и все работают.
Можно просто брать и использовать.
2. Сэджвик Р., Уэйн К. Алгоритмы на Java. — М.: ООО "И.Д. Вильямс", 2013. — 848 страниц.
Эта книжка не является калькой с предыдущей, хотя и написана позже.
Конечно, элементы предыдущей книжки присутствуют, но это не копи-паст из предыдущей книжки.
Тут 6 глав, которые вполне потянут на части:
1. Основные понятия.
2. Сортировка
3. Поиск
4. Графы
5. Строки
6. Контекст
Опять же — огромное количество иллюстраций, поясняющих алгоритмы.
Упражнений дофига, но ответов нет.
Но есть еще и творческие задачи, на некоторые из которых ответы есть. Полные или частичные.
А есть еще Эксперименты — задания, в которых надо написать (модифицировать) прогу для сбора некоей статистики.
Например, посчитать среднюю высоту RB-дерева, или среднее количество поворотов.
Кроме того, еще дофига просто вопросов — вот они все с ответами.
И еще что понравилось по сравнению с первой книжкой.
В первой книжке текст идет сплошняком, поэтому иногда сложно выделить,
где заканчивается описание одной операции и начинается описание другой.
Здесь же — каждая операция выделена в отдельный параграф с заголовком.
Хотя бы и текста всего 3-4 строчки — все равно.
Как-то ориентироваться в этой книжке — легче.
И еще у меня сложилось впечатление, что переводил более грамотный товарищ, чем переводчик первой книжки.
Навскидку примеров не приведу, но ощущение более правильного перевода устойчивое.
Первая глава — это фактически обучение программированию на Java в контексте алгоритмов и простейших струкктур данных.
1.1 Базовая модель программирования
1.2 Абстракция данных
1.3 Контейнеры, очереди и стеки
1.4 Анализ алгоритмов (опять же практически без математики)
1.5 Учебный пример: объединение-сортировка (задача на связность из первой книжки)
Определяет API-интерфейсы статических библиотек и приводит свои библиотеки, которые потом использует.
Например, для вывода графиков и гистограмм при иллюстрации алгоритмов.
В других главах описывает необходимые API.
Все проги — на Java.
Сам не проверял, но думаю, что с точностью до опечаток все должно работать.
Глава 2. Сортировка
Это уменьшенная часть из первой книжки.
Например, совсем нет поразрядных сортировок.
Но есть пункт 2.5 Применение — рассматриваются разные практические проблемы.
Например, элементы с несколькими ключами, сортировка указателей, компараторы, устойчивость... и т.п.
Здесь же — о медиане и порядковых статистиках.
Глава 3. Поиск
Материал, естественно, пересекается с первой книжкой.
1. Таблица имен
В первом пункте сразу определяется API, и рассматриваются всякие варианты.
Здесь — последовательный и бинарный поиск.
2. Деревья бинарного поиска — конспект из первой книжки, только программы на Java.
3. Сбалансированные деревья поиска — 2-3-деревья и красно-черные.
4. Хеш-таблицы — конспект первой книжки
5. Применения
Это довольно длинный раздел, в котором много чего чисто практического понаписано.
И в частности, про разреженные векторы и матрицы.
Глава 4. Графы — это опять классика.
Ориентированные и неориентированные графы, минимальные остовные деревья и кратчайшие пути.
Глава 5. Строки — не было в первой книжке.
1. Способы сортировки строк
Тут сначала про алфавиты.
А потом — сортировка подсчетом для строк, поразрядная (нисходящая и восходящая — по младшим, по старшим).
Интересная модификация быстрой сортировки.
2. Trie-деревья — очень приличная глава
Тут таблица имен на основе trie-дерева.
TST — дерево (ternary search trie).
3. Поиск подстрок.
Простой, Кнута-Морриса-Пратта, Бойера-Мура, Рабина-Карпа.
Что неожиданно: описание КМП дано в терминах ДКА.
Интересно и гораздо более понятно, чем в других книжках.
В алгоритме Рабина-Карпа написан метод Горнера
4. Регулярные выражения
Здесь не только про РВ, но и про недетерминированные конечные автоматы НКА) — связь их с РВ.
5. Сжатие данных.
Годное введение. Тут начинается с бинарных файлов в Java
Потом 2-битный код.
Хаффмен и LZW — вполне на уровне.
В общем, мне глава понравилась.
Глава 6. Контекст.
Несколько странное название, без оригинала не очень понятно.
Эта часть отмечена ляпами перевода.
1. Событийное моделирование.
Рассматривается модель столкновения неупругих частиц (переведено, как модель жестких дисков...
)).
2. В-деревья — тут классика.
3. Суффиксные массивы — для индексации больших текстов.
Нигде в учебниках не встречал (мож по-другому названы? )
4. Потоки в сетях
5. СведЕние и неразрешимось.
Элементарное введение в NP-полноту.
В общем выводы — полезно иметь сразу оба тома.
Кормен.
1. Кормен Т., Лейзерсон Ч., Ривест Р., Стайн К. Алгоритмы: построение и анализ, 3-е изд. — М.: ООО "ИД Вильямс", 2013. — 1328 страниц.
Это МИТовский курс по алгоритмам. В настоящее время считается "библией" — как по объему, так и по качеству изложения.
Курс именно для изучения алгоритмов. Теоретический, а не программистский.
Анализ разных вариантов и случаев — очень подробный, собственно это основное содержание книжки, а отнюдь не сами алгоритмы.
Программ нет ни на каком языке, алгоритмы приводятся на околоматематическом англоязычном псевдокоде.
Но комментарии в алгоритмах — переведены и вполне органично поясняют псевдокод.
МНОГО поясняющих иллюстраций.
Подчеркну: картинки очень хорошо дополняют текст и наглядно показывают работу алгоритма прямо по шагам.
Упражнений достаточно много, но без ответов.
Теорем тоже достаточно много, причем с доказательствами.
7 (семь) частей основного текста и 8 часть — приложения.
35 глав и 4 приложения.
Часть 1. Основы. Тут все математические основы анализа алгоритмов.
Уже глава 2 — серьезный текст, требующий изучения.
Тут рассматривается в качестве примера сортировка вставкой, потом пример ее анализа.
Далее перечисляются методы разработки алгоритмов (разделяй и властвуй и т.п.)
Опять пример (применение метода разделяй и властвуй) — сортировки слиянием.
Поясняющие картинки хороши.
Глава 3 — Рост функций.
Важная глава, без которой дальше анализ понять будет затруднительно.
Глава 4. Разделяй и властвуй — тут о методах решений рекуррентных соотношений.
И основная теорема — тут. С доказательствами, естественно.
И задачи тоже рассматриваются.
В частности, алгоритм Штрассена для умножения матриц как иллюстрация метода разделяй и властвуй.
Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
Название говорит само за себя. Индикаторные случайные величины — со всех сторон...
В частности тут рассматривается парадокс дней рождений.
Собственно алгоритмы начинаются с части 2. Сортировка и порядковая статистика.
— двоичная пирамида, пирамидальная сортировка и очередь с приоритетами
— быстрая сортировка
— сортировка за линейное время (подсчетом, поразрядная, карманнная — которая блочная)
— медианы и порядковые статистики
Опять же — все с картинками, которые весьма хорошо поясняют алгоритмы.
Все простые структуры данных — в части 3.
Стеки, очереди, списки, хеш-таблицы, бинарные деревья, балансированные деревья — это здесь (ну, и еще деревья отрезков).
Естественно, с подробнейшим анализом.
Балансированные деревья — красно-черные. АВЛ не рассматриваются.
Часть 4 - это методы.
— Динамическое программирование.
— Жадные алгоритмы.
Динамическое программирование рассматривается подробнейшим образом.
Сначала на задаче разрезания стержня (во 2 издании была другая задача — о работе конвейера по обработке неких деталей)
Потом классика: расстановка скобок при умножении ряда матриц.
Тут же — наидлиннейшая общая последовательность.
И опять же здесь же — оптимальные двоичные деревья.
Ничего лучше я про динамическое программирование не читал.
Кстати, среди задач к данной главе:
— расстояние редактирования
— алгоритм Виттерби (распознавания речи)
— масштабирование изображений
и еще много чего.
Жадные алгоритмы — задача планирования процессов.
Здесь же коды Хаффмена.
Матроиды — здесь (тут я чайник).
И рассматривается задача планирования как матроид.
Ну, и в этой же части — амортизационный анализ(групповой, метод бухучета, метод потенцалов)
Часть 5 — сложные структуры данных.
Тут В-деревья (что есть почти во всех других учебниках).
А чего мне не встречалось:
— Фибоначчевы пирамиды подробнейшим образом.
— деревья ван Эмде Боаса. Этого совсем нигде не видел, но написано,
что любая операция (вставка, удаление, поиск и т.п.) на этом дереве выполняется за О(lglgN) — в наихудшем случае!
Ну, и структуры для непересекающихся множеств.
Пишут, что в некоторых задачах выполняется группировка n объектов в набор непересекающихся множеств.
И две основные операции: поиск множества с заданным элементом и объединение двух множеств.
Предлагается рассмотреть структуры данных для этих операций.
Часть 6 — это графы.
Вся классика: обходы, кратчайшие пути, остовные деревья, потоки в сетях.
А вот часть 7 - самая большая. И тут собрано все, что не вошло в предыдущие части.
По сравнению с предыдущим изданием здесь появились многопоточные алгоритмы (глава 27).
Рассматривается многопоточное умножение матриц и многопоточная сортировка слиянием.
Глава 28 — решение систем линейных уравнений. Здесь и обращение матриц и метод наименьших квадратов.
Глава 29 — Линейное программирование.
Ну, в этой части и быстрое преобразование Фурье (30), и числовые алгоритмы (31 — это пересекается со 2 томом Кнута: модульная арифметика, китайская теорема об остатках, целочисленное разлоржение, проверка простоты, криптосистемы с открытым ключом...)
В этой части (32 глава) и алгоритмы поиска подстрок (Рабина-Карпа, конечный автомат, Кнута-Морриса-Пратта)
Вычислительная геометрия на примере поиска выпуклой оболочки и поиске пары ближайших точек.
NP-полнота — глава 34.
И в 35 главе — приближенные алгоритмы на нескольких задачах (коммивояжера, вершинное покрытие графа и других)
В общем, том — впечатляет.
Видимо столкнувшись с тем, что народ с трудом осваивает этот фолиант, Кормен написал книжку алгоритмов для чайников...
2. Кормен Т. Алгоритмы: вводный курс. — М.: ООО "ИД Вильямс", 2014. — 208 страниц
http://www.ozon.ru/context/detail/id/24903185/
На озоне содержание есть, поэтому просто приведу мой отзыв с Озона:
Добавлю, что алгоритмы написаны в стиле Кнута: по шагам на русском языке.Книга — для студентов, 26 февраля 2014 г.
Кормен написал маленькую книжку, как я понял, специально для студентов, которые не хотят (или не могут) освоить его основной труд — "библию" по алгоритмам. В книге всего 10 глав, тем не менее, в книге затронуты многие вопросы построения хороших алгоритмов. Математики (то есть анализа алгоритмов) практически нет.
Кормен, понимая, с каким читателем имеет дело, сразу написал: Я не знаю, чему может научить вас эта книга...
Как преподаватель могу его только поддержать: научить человека чему-нибудь — невозможно. Человек может только САМ научиться. В этом смысле книжка дает разгон для того, чтобы после нее все же решиться и прочитать основной труд Кормена по алгоритмам.
Рекомендую студентам (и преподавателям).
И опять же — много картинок. А вот заданий нет совсем.
Еще добавлю, что в главе по сжатию есть не только Хаффмен, но и Лемпель-Зив.
Роберт Сэджвик.
1. Сэджвик Р. Алгоритмы на С++. — М.: ООО "И.Д. Вильямс", 2011. — 1056 сраниц.
Эта книжка — для программистов.
Математики практически нет.
Зато много картинок, поясняющих алгоритмы.
И все алгоритмы представлены С++программами. Где в виде функцуий, а где и полноценные классы.
Все программы, которые я проверял — работают.
Однако
#include <iostream.h>
#include <math.h>
Упражнений — дофига.
Но ответов нет.
В оглавлении прописано 5 частей:
1. Анализ
2. Структуры данных
3. Сортировка
4. Поиск
5. Алгоритмы на графах.
Однако в параграфе 1.5 упоминаются еще части:
6. Строки
7. Геометрические алгоритмы
8. Дополнительные главы.
Написано, что эти части (как и графы) — в отдельных книжках.
Но мне не встречались переводы этих частей для С++.
Строки довольно подробно описаны в другой книжке Сэджвика (см. ниже).
В первой части — математики самый минимум.
Только то, что реально необходимо на практике для оценки О() алгоритма.
Рассматривается практически на примерах. Теоремы отсутствуют как класс...
Только оценка быстродействия последовательного поиска сформулирована как 2 леммы.
И тут же — бинарный поиск.
Про рекуррентные соотношения — чуть-чуть формул. И название — программерское: Простейшие рекурсии...
Ну, и рост функций — опять же чисто с практической стороны.
В общем — как раз для программистов, которые математику не любят, а оценивать быстродействие алгоритмов как-то надо.
Вторая часть — опять же соответствует названию.
Глава 3. Элементарные структуры данных.
Начинает про типы данных, числа, функции.
Продолжает: массивы и связные списки.
Для списков сразу определяет структуру node с конструктором и typedef node * link;
Потом — все операции со списками. Все — с картинками. Все присвоения указателей — на картинках.
Сортировка метолом вставки в список.
И (ВНИМАНИЕ!
) задача обращения списка — маленькая функция из 5 строчек... ! Задача Иосифа и циклические списки — тоже здесь.
Потом — выделение памяти для списка.
Маленький простейший аллокатор для узлов списка на основе динамического массива.
Потом — строки и минимум информации про них.
А потом — использование массивов и списков для представления графов: матрица смежности, список списков.
Глава 4. Абстрактные типы данных.
Тут начинается применение классов для реализации АТД.
Сначала рассказывается про классы. И кстати, шаблоны — тоже тут.
А потом рассматривается стек и показывается его использование. В частности: польская запись.
Потом показывается реализация стека на массиве и на списке.
Потом, естественно, очередь...
Ну, и попутно рассматриваются еще примеры.
АТД первого класса — это реализованные типы, которые можно использовать в программе точно так же, как встроенные.
Это Сэджвик такое определение дает и приводит примеры реализации таких чисел.
В конце — класс полиномов.
Четко разделяет интерфейс и реализацию.
Глава 5. Рекурсия.
Глава — хороша для студентов.
Просто и понятно объясняются рекурсивные функции на массе примеров.
Даже поиск максимума в массиве сделан рекурсивным способом — весьма показательно о том,
что даже чисто итеративные задачи вполне себе можно рекурсивно писать...
Естественно, ханойские башни.
Хорошо описывается прием "разделяй и властвуй" при решении задач рекурсивным способом.
А далее — динамическое программирование.
Рассматривается вычисление чисел Фибоначчи и задача о рюкзаке двумя способами: рекурсивный и динамическое программирование.
Потом — деревья. Всякие, не только двоичные.
Но математические свойства — для бинарных деревьев описываются.
Ну, а потом — обходы деревьев (и другие алгоритмы на бинарных деревьях — рекурсивные;
в частности, построение дерева синтаксического анализа)
и графов (в глубину — рекурсивный, и в ширину — не рекурсивный).
Хорошая глава для начинающих.
Третья часть — сортировки.
Это классика, поэтому просто перечислю, что здесь есть:
— элементарные сортировки;
— быстрая (достаточно подробно несколько вариантов; и тут же — медиана)
— слияние (много разных слияний; сортировка списков слиянием; связь с рекурсией)
— пирамидальная (и очереди с приоритетами)
— поразрядная (восходящая и нисходящая)
— специальные (Бэтчер, сети сортировки, внешняя, параллельное слияние)
В первой главе этой части — много всего.
Кроме выбора, вставок и пузырька там же еще и сортировка Шелла, и сортировка списков.
И еще сортировка не самих элементов, а индексов и указателей.
Ну, и тут же — сортировка подсчетом (в связи с сортировкой индексов)
И, естественно, характеристики производительности сортировок (не сам математический анализ, а именно уже посчитанные О() ).
В общем — хорошо написано, мне нравится.
Часть 4. Поиск.
Сначала определяется АТД таблицы символов — шаблон класса.
И реализация таблицы на массиве и на списке
А потом всякие поиски: последовательный (на упорядоченнном и нет контейнере), бинарный поиск — подробно.
Потом — дереья бинарного поиска (таблица символов опять — на дереве)
и много-много про действия с бинарными деревьями.
глава 13 — балансированные деревьЯ.
Тут много разных видов: скошенные (косые), нисходящие 2-3-4-деревья, красно-черные.
И тут же — слоеные списки. Больше нигде не встречал.
Глава 14 — Хеширование.
Кроме классики (хеш-функции, коллизии) тут есть динамические хеш-таблицы.
Глава 15. Поразрядный поиск.
Тут — деревья цифрового поиска (digital search tree — dst), trie-деревья, patricia-деревья.
И более сложные структуры: многопутевые trie-деревья и tst-деревья.
Глава 16. Внешний поиск.
Индесно-последовательный доступ и В-деревья...
Расширяемое хещирование — альтернатива В-деревку. Вроде тоже нигде в учебниках не писали про это.
Часть 5. Графы.
Ну, графы — они и есть графы.
Кроме классики (поиск (подробности обходов, компоненты связности), кратчайшие пути,
остовные деревья, потоки в сетях) есть генерация графов.
И довольно много про ациклические графы (direct acyclic graph-dag)
В общем добротная такая часть для программистов.
Еще раз подчеркну: все алгоритмы — на С++ и все работают.
Можно просто брать и использовать.
2. Сэджвик Р., Уэйн К. Алгоритмы на Java. — М.: ООО "И.Д. Вильямс", 2013. — 848 страниц.
Эта книжка не является калькой с предыдущей, хотя и написана позже.
Конечно, элементы предыдущей книжки присутствуют, но это не копи-паст из предыдущей книжки.
Тут 6 глав, которые вполне потянут на части:
1. Основные понятия.
2. Сортировка
3. Поиск
4. Графы
5. Строки
6. Контекст
Опять же — огромное количество иллюстраций, поясняющих алгоритмы.
Упражнений дофига, но ответов нет.
Но есть еще и творческие задачи, на некоторые из которых ответы есть. Полные или частичные.
А есть еще Эксперименты — задания, в которых надо написать (модифицировать) прогу для сбора некоей статистики.
Например, посчитать среднюю высоту RB-дерева, или среднее количество поворотов.
Кроме того, еще дофига просто вопросов — вот они все с ответами.
И еще что понравилось по сравнению с первой книжкой.
В первой книжке текст идет сплошняком, поэтому иногда сложно выделить,
где заканчивается описание одной операции и начинается описание другой.
Здесь же — каждая операция выделена в отдельный параграф с заголовком.
Хотя бы и текста всего 3-4 строчки — все равно.
Как-то ориентироваться в этой книжке — легче.
И еще у меня сложилось впечатление, что переводил более грамотный товарищ, чем переводчик первой книжки.
Навскидку примеров не приведу, но ощущение более правильного перевода устойчивое.
Первая глава — это фактически обучение программированию на Java в контексте алгоритмов и простейших струкктур данных.
1.1 Базовая модель программирования
1.2 Абстракция данных
1.3 Контейнеры, очереди и стеки
1.4 Анализ алгоритмов (опять же практически без математики)
1.5 Учебный пример: объединение-сортировка (задача на связность из первой книжки)
Определяет API-интерфейсы статических библиотек и приводит свои библиотеки, которые потом использует.
Например, для вывода графиков и гистограмм при иллюстрации алгоритмов.
В других главах описывает необходимые API.
Все проги — на Java.
Сам не проверял, но думаю, что с точностью до опечаток все должно работать.
Глава 2. Сортировка
Это уменьшенная часть из первой книжки.
Например, совсем нет поразрядных сортировок.
Но есть пункт 2.5 Применение — рассматриваются разные практические проблемы.
Например, элементы с несколькими ключами, сортировка указателей, компараторы, устойчивость... и т.п.
Здесь же — о медиане и порядковых статистиках.
Глава 3. Поиск
Материал, естественно, пересекается с первой книжкой.
1. Таблица имен
В первом пункте сразу определяется API, и рассматриваются всякие варианты.
Здесь — последовательный и бинарный поиск.
2. Деревья бинарного поиска — конспект из первой книжки, только программы на Java.
3. Сбалансированные деревья поиска — 2-3-деревья и красно-черные.
4. Хеш-таблицы — конспект первой книжки
5. Применения
Это довольно длинный раздел, в котором много чего чисто практического понаписано.
И в частности, про разреженные векторы и матрицы.
Глава 4. Графы — это опять классика.
Ориентированные и неориентированные графы, минимальные остовные деревья и кратчайшие пути.
Глава 5. Строки — не было в первой книжке.
1. Способы сортировки строк
Тут сначала про алфавиты.
А потом — сортировка подсчетом для строк, поразрядная (нисходящая и восходящая — по младшим, по старшим).
Интересная модификация быстрой сортировки.
2. Trie-деревья — очень приличная глава
Тут таблица имен на основе trie-дерева.
TST — дерево (ternary search trie).
3. Поиск подстрок.
Простой, Кнута-Морриса-Пратта, Бойера-Мура, Рабина-Карпа.
Что неожиданно: описание КМП дано в терминах ДКА.
Интересно и гораздо более понятно, чем в других книжках.
В алгоритме Рабина-Карпа написан метод Горнера
4. Регулярные выражения
Здесь не только про РВ, но и про недетерминированные конечные автоматы НКА) — связь их с РВ.
5. Сжатие данных.
Годное введение. Тут начинается с бинарных файлов в Java
Потом 2-битный код.
Хаффмен и LZW — вполне на уровне.
В общем, мне глава понравилась.
Глава 6. Контекст.
Несколько странное название, без оригинала не очень понятно.
Эта часть отмечена ляпами перевода.
1. Событийное моделирование.
Рассматривается модель столкновения неупругих частиц (переведено, как модель жестких дисков...
)). 2. В-деревья — тут классика.
3. Суффиксные массивы — для индексации больших текстов.
Нигде в учебниках не встречал (мож по-другому названы? )
4. Потоки в сетях
5. СведЕние и неразрешимось.
Элементарное введение в NP-полноту.
В общем выводы — полезно иметь сразу оба тома.