Re[5]: Норвый список книг по алгоритмам
От: SkyDance Земля  
Дата: 26.03.16 08:05
Оценка: +2
EP>Это же классика:

Таки кто-то вспомнил я думал, уже совсем забыли Билли.
Re: Новый список книг по алгоритмам
От: Pzz Россия https://github.com/alexpevzner
Дата: 26.03.16 09:12
Оценка: :)
Здравствуйте, LaptevVV, Вы писали:

LVV>С момента опубликования старого списка прошло уже много времени.


Донавьте в свой список.

http://www.ozon.ru/context/detail/id/32324326/
Re[7]: Норвый список книг по алгоритмам
От: Pzz Россия https://github.com/alexpevzner
Дата: 26.03.16 09:15
Оценка:
Здравствуйте, SkyDance, Вы писали:

S>>То есть книг Кнута достаточно?


SD>Если вы их сможете понять, и решить упражнения (ну, понятное дело, кроме Великой Теоремы Ферма, которую он там под задачу замаскировал) — более чем.


И зачем человеку, который все это может, проходить собеседование в гугле и мелкософте?
Re[2]: Новый список книг по алгоритмам
От: LaptevVV Россия  
Дата: 26.03.16 09:28
Оценка:
Pzz>Донавьте в свой список.
Pzz>http://www.ozon.ru/context/detail/id/32324326/
Я ее читал еще в то время...
Как и последующую книгу Гриса.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: Новый список книг по алгоритмам
От: Pzz Россия https://github.com/alexpevzner
Дата: 26.03.16 09:31
Оценка: +1
Здравствуйте, LaptevVV, Вы писали:

LVV>Я ее читал еще в то время...

LVV>Как и последующую книгу Гриса.

Книгу Дейкстры куда как более интересно читать, чем Гриса. Грис — унылый институтский учебник, а Дейкства пишет лихо, со своим весьма своеобразным чувством юмора, с тонким сарказмом.
Re: Кормен и Сэджвик
От: LaptevVV Россия  
Дата: 01.04.16 08:00
Оценка: 6 (2)
В старом списке были указаны предыдущие издания. С тех пор появились переводы новых изданий.
Кормен.
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-полноту.

В общем выводы — полезно иметь сразу оба тома.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Отредактировано 10.04.2016 10:24 LaptevVV . Предыдущая версия . Еще …
Отредактировано 03.04.2016 12:25 LaptevVV . Предыдущая версия .
Отредактировано 01.04.2016 8:06 LaptevVV . Предыдущая версия .
Re: Книги Рода Стивенса
От: LaptevVV Россия  
Дата: 10.04.16 10:33
Оценка:
Мне известны три перевода Рода Стивенса.
Сначала была "Готовые алгоритмы на Бейсике"
Потом практически копипаст с нее: Delphi. Готовые алгоритмы.
Английский оригинал: Ready-to-run Delphi Algorithms.
И наконец, в этом году появился перевод книжки Essential Algorithms: http://www.ozon.ru/context/detail/id/135297188/
Книжки написаны удивительно простым и понятным языком.

По первой книге. Все проги, естественно, на Дельфи.
Сам не проверял, но есть Приложение 1 и приложение 2, где прописан полный список примеров, откуда их брать и как запускать.
В книге 13 глав
1. Основные понятия. Здесь минимальный ликбез про О(). Математики опять же — никакой, логарифмы только...
2. Списки. Сначала под списком понимается динамический массив (как набор элементов),
а потом вводится традиционный связанный список. Операции, естественно.
И много разновидностей связных списков. Например, многосвязный список, который обозван переводчиком "список с потоками"...
А также другие связанные структуры — маленький обзор с картинками.
3. Стеки и очереди. Вся классика. Циклические очереди хорошо расписаны.
Но тут и очереди с приоритетами — элементарное введение, без пирамиды, как упорядоченный список.
И опять же "многопоточные" очереди — очереди с несколькими головами и одним хвостом... Змей Горыныч натуральный...
4. Массивы. Тут разные нестандартные массивы: треугольные, разреженные, сильно разреженные.
5. Рекурсия. Тут классика: факториал, НОД, Фибоначчи, кривые Гильберта и Серпинского.
Но описаны способы устранения рекрсии — хвостовой и в общем случае.
6. Деревья. Вся классика.
Описаны деревья со ссылками (у кого-то встречал термин "прошитые" про такие деревья).
Интересные Q-деревья (quadtree) — описывают пространственные отношения между элементами в пределах какой-либо ограниченной области.
Это определение из книжки.
7. Сбалансированные деревья. Здесь АВЛ и В-деревья.
8. Деревья решений.
Это поиск в игровых деревьях: минимакс и его улучшение (на примере крестиков — ноликов 3х3)
Далее метод ветвей и границ, и эвристические методы полного перебора.
Здесь же сложные задачи: задача о выполнимости, о разбиении, коммивояжера...
9. Сортировки. Ну, тут практически вся классика. Пирамиды здесь тоже есть.
10. Поиск. Здесь, помимо простых, интерполяционный поиск, и следящий поиск.
11. Хеширование. Типовая классика.
12. Сетевые алгоритмы. Они же — алгоритмы на графах. Обходы, пути, остовное дерево, максимальный поток.
13. ООП. Здесь кое-какие паттерны объясняются: фасад, итератор, mvc, visitor (называется контролирующий объект — visitor object) и т.д.

Упражнений нет вообще.
Но в общем, книжка неплохая.

Essential Algorithms
Это уже полноценный учебник. Содержит 19 глав.
Алгоритмы приводятся на понятном англоязычном псевдокоде, похожем на Паскаль и на Бейсик одновременно...
Во всяком случае это — программный псевдокод, а не математический, как у Кормена.
Упражнения и ответы к ним (приложение Б — ~70 страниц).
Приложение 1 и Глоссарий содержат определения и разъяснения огромного количества терминов.

Мой отзыв на Озоне:

Очень неплохая книга для изучения основ. Написана конкретно для новичков.
Поэтому в самом начале рассматриваются темы, которые обычно отсутствуют в профессиональных учебниках: работа с числами, массивы, списки.
Но в книге есть темы, которые обычно не рассматриваются в книгах по алгоритмам и структурам данных: деревья решений (рассматривается минимакс, метод ветвей и границ, эвристики), криптография (перестановочные шифры, подстановки, блочные шифры, RSA).
Весьма полезна для начинающих глава о рекурсии, где помимо традиционных задач (8 ферзей, обход конем и т.п) рассматривается проблема удаления рекурсии (и хвостовой, и общей).
Есть главы и об алгоритмах на графах, и строковые алгоритмы (не только поиск подстрок, но и вычисление расстояния, и анализ арифметических выражений).
Естественно, есть глава о вычислительной сложности.
И весьма полезна для начинающих глава о параллельных вычислениях — рассмотрены все основы.
В общем, очень рекомендую как первую книгу по алгоритмам и структурам данных.

Второй отзыв на Озоне:

Согласен в Валерием, что книга очень неплохая. По крайней мере, ее стоит почитать-поглядеть. Но ни в коем случае не покупайте ее в переводе от ЭКСМО. Эти друзья испортили все впечатление от книги. Я на эту книгу наткнулся на английском языке. Начал читать и понял, что должен ее купить, чтобы отдать дань уважения автору. Но не за такой же перевод. Я прочитал две главы. И уже во время чтения второй наткнулся на несколько неточностей перевода, которые меняют смысл прочитанного. Ответы к задачам первой главы перепутаны. Вернее зачем-то еще пронумерованы отдельные абзацы в ответах, в итоге их стало больше, чем самих задач. Это здорово запутывает. После этого очень сложно избавиться от мысли, что не сможешь разглядеть очередной косяк переводчика и вообще непонятно, что ждать дальше по ходу чтения.

Содержание.
1. Основы алгоритмизации. Здесь объясняется псевдокод и сложность алгоритма (О-нотация). Математики практически нет.
2. Численные алгоритмы. Генерация случайных чисел, НОД, возведение в степень, простые числа, численное интегрирование (в том числе Монте-Карло), нахождение корней (Ньютон)
3. Связанные списки. Почти все, что можно написать о списках.
4. Массивы. Опять же — для начинающих — много интересного.
5. Сортировка. Абсолютно классическое изложение: 3 простых, 3 быстрых, подсчетом и блочная.
6. Поиск. Линейный, бинарный, интерполяционный — на массивах.
7. Хеширование. Классика. Здесь ляп перевода прямо в содержании. Термин "опробывание" (который вообще-то рехеширование) написан как "пробирование". Видимо, от слова "проба"...
9. Рекурсия. См. мой отзыв ниже.
10. Деревья. Вся классика: обходы, операции.
Но есть параграф "Специализированные алгоритмы", где префиксные деревья, деревья квадрантов (см. в предыдущей книге), деревья выражений.
11. Сбалансированные деревья. АВЛ, 2-3 и В-деревья.
12. Деревья принятия решений.
13. Основные сетевые алгоритмы.
14. Дополнительные сетевые алгоритмы.
15. Строковые алгоритмы.
16. Криптография. Здесь перестановочные шифры, шифры подстановки, блочные шифры, шифрование с открытым ключом.
17. Теория вычислительной сложности.
18. Распределенные алгоритмы. Ценная глава для начинающих.
19. Головоломки, встречающиеся на собеседованиях. Как задавать вопросы с подвохом и как отвечать на вопросы с подвохом.

В общем, еще раз рекомендую именно начинающим.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Отредактировано 28.04.2016 14:30 LaptevVV . Предыдущая версия . Еще …
Отредактировано 28.04.2016 14:12 LaptevVV . Предыдущая версия .
Отредактировано 28.04.2016 14:07 LaptevVV . Предыдущая версия .
Отредактировано 28.04.2016 13:58 LaptevVV . Предыдущая версия .
Отредактировано 23.04.2016 14:33 LaptevVV . Предыдущая версия .
Отредактировано 23.04.2016 14:14 LaptevVV . Предыдущая версия .
Отредактировано 22.04.2016 6:07 LaptevVV . Предыдущая версия .
Re: Книги Никлауса Вирта
От: LaptevVV Россия  
Дата: 10.04.16 10:34
Оценка: +1
#Имя: КнигиВирта
У Никлауса Вирта по структурам данных выходила практически одна и та же книга — на разных языках программирования.
Сначала была "Алгоритмы+структуры данных = программы".
Была переведена в издательстве Мир еще аж в 1985 году.
Отличается от прочих наличием хорошей главы по компиляторам.
Программы, естественно, на Паскале.

Вторая книга: Алгоритмы и структуры данных.
Была переведена в издательстве Мир в 1989 году.
Отличается от предыдущей:
— отсутствие главы по компиляторам (вынесено в отдельную книгу Проектирование компиляторов)
— наличие главы по поиску в строках
Программы, естественно, на Модуле-2.
Потом наши самолично переиздали эту же книжку уже в 2001 году
и еще потом переиздвали: http://forcoder.ru/algorithm/algoritmy-i-struktury-dannyh-44

И наконец, в 2010 году была переведена последняя версия этой книги: http://www.ozon.ru/context/detail/id/6146670/
Хотя книжка имеет подзаголовок "Новая версия для Оберона",
программы написаны на Компонентном Паскале в среде BlackBox Component Builder.

Книжка — небольшая, вместе с предметным указателем — 272 страницы.
Есть упражнения, но ответов нет.

Глав всего 5
1. Фундаментальные структуры данных.
Здесь, помимо введение структуры данных Компонентного паскаля, параграф про поиск в массивах (простой, с барьером, двоичный)
и поиск подстроки в строке (простой, Кнута-Морриса-Пратта, Бойера-Мура — с картинками)
2. Сортировка — классика.
Сначала выбор-вставка-пузырек. Потом Шелла, пирамидальная (названная турнирной), быстрая (здесь же — медиана).
Потом довольно много про всякие сортировки слиянием.
3. Рекурсивные алгоритмы.
Здесь кривые Гильберта и Серпинского, алгоритмы с возвратом (задача о 8 ферзях, о стабильных браках и задача оптимального выбора)
4. Динамические структуры данных.
Здесь сначала: рекурсивные структуры данных, указатели.
Потом классика: списки, деревья, балансированные деревья (АВЛ), деревья оптимального поиска,
В-деревья, приоритетные деревья поиска (МакКрейт)
5. Хеширование. Классический минимум.

Что хочется отметить.
0. Помимо собственно алгоритмов и структур данных Вирт объясняет и использует для разработки алгоритмов метод пошагового уточнения.
Особенно это наглядно продемонстрировано в главе о рекурсивных алгоритмах.
В результате программы получаются очень прозрачные и понятные.
1. Перевод выполнен очень тщательно.
Переводил человек, кровно заинтересованный в качестве, ибо сам преподает программирование для физиков МГУ конкретно по этой книжке.
2. В процессе перевода были реализованы ВСЕ примеры, найдены неточности и ошибки.
Исправления были согласованы с самим Виртом, и внесены в английский оригинал.
3. К книжке прилагается сидюк со средой BlackBox Component Builder и кучей руссифицированной документации.
Все примеры в среде открываются и работают — можно посмотреть непосредственно.
4. Переводчик написал замечательное предисловие и послесловие.
В частности, описал цикл Дейкстры (кто тут упоминал книжку Дисциплина программирования ?)

Рекомендую как начальную книжку по теме.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Отредактировано 03.05.2016 6:41 LaptevVV . Предыдущая версия .
Re: МакКоннелл
От: LaptevVV Россия  
Дата: 23.04.16 14:34
Оценка: 3 (1)
Книжки МакКоннелла по алгоритмам переводились не менее 2 раз.
У меня на руках такая:
Дж. МакКоннелл. Анализ алгоритмов. Активный обучающий подход.
3-е дополненное издание. — М.: Техносфера, 2009. — 416 с.

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

В конце книги приведены ответы к некоторой части упражнений.

Алгоритмы приводятся на псевдокоде, похожем на паскаль (как у Рода Стивенса).
Иногда с вкраплениями неформальных действий (как у Вирта в методе пошагового уточнения).
Алгоритмы с псевдокода легко конвертируются в Си-подобный язык.
Математики мало. Фактически и не математика (как у Кнута), а просто вывод простых комбинаторных формул в некоторых алгоритмах.

Содержание:
1. Основы анализа алгоритмов.
Ну, здесь достаточно простым языком объясняется, что анализируем, скорости роста, нижние границы...
Вспоминаем элементарную математику, логарифмы, суммы, факториалы и т.п.

2. Рекурсивные алгоритмы.
Тут математика рекуррентных соотношений и собственно анализ рекурсивных алгоритмов с их помощью.
Рассматриваются три задачи: пара ближайших точек, выпуклая оболочка и генерация перестановок.
Все довольно подробно объясняется словами, а вот математического анализа как такового нет. Так — пара формул приводится, и все.
Здесь же про связь рекрсии со стеком.

3. Поиск и выборки.
Поиск линейный и двоичный. Здесь анализ как раз есть — длинные формулы суммирования на пол-страницы.
Выборка — это поиск к-то по величине значения в массиве.

4. Сортировка. (ответы на упражнения начинаются с главы 4).
Тут классика: вставки, пузырек, Шелла, поразрядная (почему-то названная корневой),
пирамидальная, быстрая, слияние и внешнее многофазное слияние.
Анализ худшего и анализ среднего случаев. И в зависимости от сортировки — нюансы.

5. Численные алгоритмы.
Конспективная глава: схема Горнера, умножение матриц по Винограду и Штрассену,
решение систем линейных уравнений по схеме Жордана-Гаусса.
Никаких рассуждений не приводится, просто сразу даются таблички с формулами количества операций.

6. Алгоритмы формальных языков. В книжках по алгоритмам этого практически не встречается.
Главу смело можно рекомендовать как введение в формальные грамматики и автоматы.
Конечные автоматы детерминированные и недетерминированные, регулярные выражения и регулярные грамматики.
Эквивалентности, преобразование автомата в программу, проектирование, ограничения и возможности.
МП-автоматы детерминированные и недетерминированные, контекстно-свободные грамматики,
преобразование грамматик, нормальная форма Грейбах.
Преобразование грамматики в МП-автомат, проектирование МП-автомата, ограничения и возможности.
Введение в синтаксический разбор.
Теорем нет, математики нет, и изложение очень практическое. С элементами теории формальных языков, грамматик и автоматов.

7. Сравнение с образцом.
Это поиск подстроки в строке.
Простой, конечно-автоматный упоминается, Кнута-Морисса-Пратта — основное содержание главы.
И немного про приблизительное сравнение строк. Анализ есть не везде, а где есть — очень лаконично, буквально 1 абзац.

8. Алгоритмы на графах.
Тут классика в минимальном объеме: обходы, поиск путей, остовное дерево.
Алгоритм определения компонент двусвязности, разбиение множеств (на массивах.

А вот следующая глава — это фишка книги.
9. Параллельные алгоритмы.
Сначала — классификация Флинна, описывается неформально каждый класс.
Потом кратенькое введение в архитектуры параллельных машин.
Важный параграф — Модель памяти PRAM. Простые операции в разных моделях PRAM.
И понеслась — параллельные алгоритмы поиска, сортировки (четно-нечетная, на линейных сетяхи др.).
Численные — параллельное умножение матриц, решение системы линейных уравнений.
Параллельные алгоритмы на графах.

10. Вычислимое и невычислимое.
Здесь все про машины Тьюринга (много всяких описано) и NP — довольно неплохо, на 50 страницах.

11. Другие алгоритмические инструмента.
Здесь собраны жадные алгоритмы, алгоритмы с возвратом, ветвей и границ,
вероятностные (в частности, Монте-Карло, Лас-Вегас, Шервудские).
И динамическое программирование.
Хорошая глава.


И в приложении еще Генерирование случайных чисел есть.
В общем — весьма неплохая книжка.
Обращаю внимание — практически нет структур данных. Ничего нет о деревьях.
Зато есть темы, которые в других книжках совсем не затрагиваются.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Отредактировано 10.05.2016 7:58 LaptevVV . Предыдущая версия . Еще …
Отредактировано 09.05.2016 10:23 LaptevVV . Предыдущая версия .
Отредактировано 09.05.2016 9:41 LaptevVV . Предыдущая версия .
Отредактировано 09.05.2016 9:19 LaptevVV . Предыдущая версия .
Отредактировано 09.05.2016 9:03 LaptevVV . Предыдущая версия .
Отредактировано 08.05.2016 12:21 LaptevVV . Предыдущая версия .
Re: Новый список книг по алгоритмам
От: _DAle_ Беларусь  
Дата: 25.04.16 14:06
Оценка: 3 (1) +1
Здравствуйте, LaptevVV, Вы писали:

Есть еще, например, отличная книга Дэна Гасфилда "Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология".
Re: Жемчужины программирования. Джон Бентли
От: LaptevVV Россия  
Дата: 03.05.16 06:57
Оценка: +1
Джон Бентли. Жемчужины программирования, 2-е издание. — СПб.: Питер, 2002.- 272 с.

Я читал еще первое издание.
Замечательная книга.

Книга не является учебником по алгоритмам.
Написана неформально, в виде дружеского разговора с читателем.
Но упражнения есть и есть даже решения.
Это даже не сами формальные решения, а больше размышления и соображения (или ссылки), приводящие к решениям.

Содержание приведу.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Отредактировано 10.05.2016 8:10 LaptevVV . Предыдущая версия .
Re: Марк Аллен Уайс
От: LaptevVV Россия  
Дата: 03.05.16 06:58
Оценка: 2 (1)
Организация структур данных и решение задач на С++

Отличная книжка для Сиплюсников.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Отредактировано 10.05.2016 8:10 LaptevVV . Предыдущая версия .
Re: Дж. Ульман, Скиена и др.
От: Stanislav V. Zudin Россия  
Дата: 03.05.16 08:12
Оценка: +1
Здравствуйте, LaptevVV, Вы писали:

LVV>С момента опубликования старого списка прошло уже много времени.

LVV>Да и пожелание было подробнее аннотации написать.
LVV>Пост будет большой, поэтому буду дополнять-редактировать по мере наличия свободного времени.
LVV>Итак начнем опять с классики:

Незаслуженно забыли другого классика — Дж. Ульмана сотоварищи.

1. Винтаж.
"Основы Систем Баз Данных" Изд. "Финансы и статистика" Москва 1983
"Principles of database systems"

Физическая организация данных
Модели данных
Теория проектирования реляционных баз данных
Оптимизация запросов

Акцент делается на то, что у СУБД "под капотом". Будет полезна тем, кто разрабатывает разлапистые структуры данных.

2. "Структуры данных и алгоритмы" А.В.Ахо, Дж. Э. Хопкрофт, Дж. Д. Ульман. Изд. "Вильямс" 2001.
"Data structures and algorithms"

1.Построение и анализ алгоритмов
2.Основные абстрактные типы данных.
(списки, стеки, очереди, мапы и проч)
3.Деревья
(двоичные и не только, разные способы реализации, в том числе и с помощью массивов )
4.Основные операторы множеств
(словари, хеши, очереди с приоритетами, мультисписки)
5.Специальные методы представления множеств
(нагруженные деревья, сбалансированные деревья)
6.Ориентированные графы
(обход графов, поиск кратчайшего пути)
7.Неориентированные графы
8.Сортировка
9.Методы анализа алгоритмов
10.Методы разработки алгоритмов
11.Структуры данных и алгоритмов для внешней памяти
12.Управление памятью

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

3. Dragon-book
без комментариев.

Ну и забыли Скиену.
4. Стивен С. Скиена "Алгоритмы. Руководство по разработке" "БХВ-Петербург" 2011.
"The Algorithm Design Manual"

Неплохой перевод, а главное — приводятся примеры из практики, т.е. постановка задачи и выбор решения.
_____________________
С уважением,
Stanislav V. Zudin
Re[2]: Дж. Ульман, Скиена и др.
От: LaptevVV Россия  
Дата: 03.05.16 08:41
Оценка:
SVZ>Незаслуженно забыли другого классика — Дж. Ульмана сотоварищи.
Не забыл. Просто еще руки не дошли...
SVZ>1. Винтаж.
SVZ>"Основы Систем Баз Данных" Изд. "Финансы и статистика" Москва 1983
SVZ>"Principles of database systems"
Есть такая книжка. Но это лучше писать в отдельный список по БД.
SVZ>Акцент делается на то, что у СУБД "под капотом". Будет полезна тем, кто разрабатывает разлапистые структуры данных.
Есть еще 2 современных на ту же тему.
А начинать надо с Мартина, наверное...

SVZ>2. "Структуры данных и алгоритмы" А.В.Ахо, Дж. Э. Хопкрофт, Дж. Д. Ульман. Изд. "Вильямс" 2001.

SVZ>"Data structures and algorithms"
Про это собирался писать.
SVZ>1.Построение и анализ алгоритмов
SVZ>2.Основные абстрактные типы данных.
SVZ>(списки, стеки, очереди, мапы и проч)
SVZ>3.Деревья
SVZ>(двоичные и не только, разные способы реализации, в том числе и с помощью массивов )
SVZ>4.Основные операторы множеств
SVZ>(словари, хеши, очереди с приоритетами, мультисписки)
SVZ>5.Специальные методы представления множеств
SVZ>(нагруженные деревья, сбалансированные деревья)
SVZ>6.Ориентированные графы
SVZ>(обход графов, поиск кратчайшего пути)
SVZ>7.Неориентированные графы
SVZ>8.Сортировка
SVZ>9.Методы анализа алгоритмов
SVZ>10.Методы разработки алгоритмов
SVZ>11.Структуры данных и алгоритмов для внешней памяти
SVZ>12.Управление памятью
SVZ>На мой взгляд книга интереснее, чем книги Седжвига, много уделяется деталям реализации структур данных.
SVZ>Но перевод хреновенький. Приходится в уме переводить на аглицкий, чтобы понять о чем речь.
Но раз вы написали, я сильно подробно не буду — только личные впечатления.
SVZ>3. Dragon-book
SVZ>без комментариев.
Ну, это надо в отдельный список книг по компиляторам...
SVZ>Ну и забыли Скиену.
Не забыл. Сегодня только смотрел, где она у меня лежит. Собирался дать следующим после уже прописанных заголовков.
SVZ>4. Стивен С. Скиена "Алгоритмы. Руководство по разработке" "БХВ-Петербург" 2011.
SVZ>"The Algorithm Design Manual"
SVZ>Неплохой перевод, а главное — приводятся примеры из практики, т.е. постановка задачи и выбор решения.
Рассмотрю подробнее.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: Дж. Ульман, Скиена и др.
От: Stanislav V. Zudin Россия  
Дата: 03.05.16 09:03
Оценка:
Здравствуйте, LaptevVV, Вы писали:

SVZ>>"Основы Систем Баз Данных" Изд. "Финансы и статистика" Москва 1983

SVZ>>"Principles of database systems"
LVV>Есть такая книжка. Но это лучше писать в отдельный список по БД.

В список по БД лучше подходит "Системы баз данных" Гарсии-Молины и того же Ульмана.
А эта где-то на границе, ближе к прикладному использованию структур данных.

SVZ>>Акцент делается на то, что у СУБД "под капотом". Будет полезна тем, кто разрабатывает разлапистые структуры данных.

LVV>Есть еще 2 современных на ту же тему.
LVV>А начинать надо с Мартина, наверное...

Давай, Валерий Викторович, интересно почитать что-то свежее.
А то книг про "структуры данных для самых маленьких" только ленивый не пишет. А вот о проектировании структур данных и их правильном эффективном применении книг попадается мало.
_____________________
С уважением,
Stanislav V. Zudin
Re[4]: Дж. Ульман, Скиена и др.
От: LaptevVV Россия  
Дата: 03.05.16 09:40
Оценка: :)
SVZ>Давай, Валерий Викторович, интересно почитать что-то свежее.
SVZ>А то книг про "структуры данных для самых маленьких" только ленивый не пишет. А вот о проектировании структур данных и их правильном эффективном применении книг попадается мало.
Ну, Кавасаки я уже получил. Когда руки дойдут прочитать — пропишу
Но из практики программирования могу совершенно определенно сказать:
применять изощренные сложные структуры данных приходится чрезвычайно редко.
Как правило, чем проще структура данных, тем проще и понятней алгоритм ее обработки.
Да еще и ошибок в простом алгоритме совершается значительно меньше.
Скорость сейчас не так проблематична, ибо имеем многоядерный проц и практически всегда можно ускорить программу,
распараллелив ее на несколько потоков.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[5]: Дж. Ульман, Скиена и др.
От: Stanislav V. Zudin Россия  
Дата: 03.05.16 10:14
Оценка:
Здравствуйте, LaptevVV, Вы писали:

SVZ>>Давай, Валерий Викторович, интересно почитать что-то свежее.

SVZ>>А то книг про "структуры данных для самых маленьких" только ленивый не пишет. А вот о проектировании структур данных и их правильном эффективном применении книг попадается мало.
LVV>Ну, Кавасаки я уже получил. Когда руки дойдут прочитать — пропишу



LVV>Но из практики программирования могу совершенно определенно сказать:

LVV>применять изощренные сложные структуры данных приходится чрезвычайно редко.

Хе, практика-то у всех разная.

LVV>Как правило, чем проще структура данных, тем проще и понятней алгоритм ее обработки.

LVV>Да еще и ошибок в простом алгоритме совершается значительно меньше.

А моя практика программирования показала, что алгоритм первичен.
Сперва выбирается алгоритм, а под него уже проектируются структуры данных. А там от требований зависит — простые структуры получатся или не очень.
Бо взять линейный алгоритм и превратить его в O(N^3) неудачной структурой данных — это как два байта переслать.
И, кстати, распространенная в книжках идея, что заграница абстракция/инкапсуляция нам поможет не переделывать данные при замене алгоритма — опасное заблуждение. Иногда переделывать приходится.

LVV>Скорость сейчас не так проблематична, ибо имеем многоядерный проц и практически всегда можно ускорить программу,

LVV>распараллелив ее на несколько потоков.

Скорости, как и памяти, много не бывает. Всегда найдется, чем занять.
_____________________
С уважением,
Stanislav V. Zudin
Re[8]: Норвый список книг по алгоритмам
От: Submitter  
Дата: 03.05.16 10:38
Оценка:
Здравствуйте, Pzz, Вы писали:

SD>>Если вы их сможете понять, и решить упражнения (ну, понятное дело, кроме Великой Теоремы Ферма, которую он там под задачу замаскировал) — более чем.


Pzz>И зачем человеку, который все это может, проходить собеседование в гугле и мелкософте?


А где предлагаете работать со всеми этими знаниями?
Re[6]: Дж. Ульман, Скиена и др.
От: LaptevVV Россия  
Дата: 03.05.16 11:15
Оценка:
SVZ>А моя практика программирования показала, что алгоритм первичен.
Ну, еще Фредерик Брукс сказал (как давно это было!):

Покажите мне блок–схемы, не показывая таблиц, и я останусь в заблуждении.
Покажите мне ваши таблицы, и блок–схемы, скорее всего, не понадобятся: они будут очевидны.

SVZ>Скорости, как и памяти, много не бывает. Всегда найдется, чем занять.
Ну, это да...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[9]: Норвый список книг по алгоритмам
От: Pzz Россия https://github.com/alexpevzner
Дата: 04.05.16 07:36
Оценка: +1 -1
Здравствуйте, Submitter, Вы писали:

SD>>>Если вы их сможете понять, и решить упражнения (ну, понятное дело, кроме Великой Теоремы Ферма, которую он там под задачу замаскировал) — более чем.


Pzz>>И зачем человеку, который все это может, проходить собеседование в гугле и мелкософте?


S>А где предлагаете работать со всеми этими знаниями?


Гугль и микрософт — это фабрика с конвеером. В таком месте хорошо поработать в молодости, а потом можно и что-нибудь поинтереснее себе подыскать.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.