Сообщение Re: Кормен и Сэджвик от 01.04.2016 8:00
Изменено 03.04.2016 12:25 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. Кормен Т., Лейзерсон Ч., Ривест Р., Стайн К. Алгоритмы: построение и анализ, 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. Кормен Т., Лейзерсон Ч., Ривест Р., Стайн К. Алгоритмы: построение и анализ, 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. Рекурсия.
Глава — хороша для студентов.
Просто и понятно объясняются рекурсивные функции на массе примеров.
Даже поиск максимума в массиве сделан рекурсивным способом — весьма показательно о том,
что даже чисто итеративные задачи вполне себе можно рекурсивно писать...
Естественно, ханойские башни.
Хорошо описывается прием "разделяй и властвуй" при решении задач рекурсивным способом.
А далее — динамическое программирование.
Рассматривается вычисление чисел Фибоначчи и задача о рюкзаке двумя способами: рекурсивный и динамическое программирование.
Потом — деревья. Всякие, не только двоичные.
Но математические свойства — для бинарных деревьев описываются.
Ну, а потом — обходы деревьев (и другие алгоритмы на бинарных деревьях — рекурсивные;
в частности, построение дерева синтаксического анализа)
и графов (в глубину — рекурсивный, и в ширину — не рекурсивный).
Хорошая глава для начинающих.
Третья часть — сортировки.
Это классика, поэтому просто перечислю, что здесь есть:
— элементарные сортировки;
— быстрая (достаточно подробно несколько вариантов; и тут же — медиана)
— слияние (много разных слияний; сортировка списков слиянием; связь с рекурсией)
— пирамидальная (и очереди с приоритетами)
— поразрядная (восходящая и нисходящая)
— специальные (Бэтчер, сети сортировки, внешняя, параллельное слияние)
В первой главе этой части — много всего.
Кроме выбора, вставок и пузырька там же еще и сортировка Шелла, и сортировка списков.
И еще сортировка не самих элементов, а индексов и указателей.
Ну, и тут же — сортировка подсчетом (в связи с сортировкой индексов)
И, естественно, характеристики производительности сортировок (не сам математический анализ, а именно уже посчитанные О() ).
В общем — хорошо написано, мне нравится.
Четвертая часть — это