С момента опубликования старого списка прошло уже много времени.
Да и пожелание было подробнее аннотации написать.
Пост будет большой, поэтому буду дополнять-редактировать по мере наличия свободного времени.
Итак начнем опять с классики: 0. Кнут Д. Искусство программирования, том 1, выпуск 1. MMIX — RISCкомпьютер нового тысячелетия : Пер. с англ.: М.: ООО "И.Д.Вильямс", 2007.
1. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3 изд.: Пер. с англ.: Уч. пос. — М.: Издательский дом «Вильямс», 2000.
2. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы, 3 изд.: Пер. с англ.: Уч. пос. — М.: Издательский дом «Вильямс», 2001.
3. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2 изд.: Пер. с англ.: Уч. пос. — М.: Издательский дом «Вильямс», 2000.
4. Кнут Д. Искусство программирования, том 4. Комбинаторные алгоритмы, часть 1: Пер. с англ.: М.: ООО "И.Д.Вильямс", 2013.
Дональд Кнут продолжил свою знаменитую серию книг.
В томе 1 (720 страниц) 2 части:
1. Основные понятия.
2. Информационные структуры.
В первой части описано понятие алгоритма на примере алгоритма Евклида (куда ж без него... ). Между прочим — аж 10 страниц...
Потом математическое введение. Здесь он полностью описывает весь математический аппарат, который будет использовать в дальнейшем.
Вообще-то это именно введение. Потому как если кто забыл математическую индукцию, степени и логарифмы, перестановки и факториалы, гармонические числа и числа Фибоначчи — вам сюда.
Ну, и, конечно, есть конкретно про анализ алгоритмов, О-нотацию и все с этим связанное.
Здесь же — описание виртуальной машины MIX — программы в этой серии книг представлены на ассемблере этой виртуальной машины.
Однако продолжение своих книжек Кнут начал с того, что написал номер 0.
И у себя на сайте кликнул клич волонтерам переписать интерпретатор и все проги на новом ассемблере.
Вообще-то эта часть — прекрасное введение в тему виртуальных машин (кому надо).
И, между прочим, про память и указатели — тоже можно брать отсюда.
Все структуры данных у него расписываются подробно: узел всегда показан в памяти MIX со всеми полями-указателями.
Можно использовать при изучении архитектуры ЭВМ — в теме про RISK-компьютеры.
Кстати, здесь же — о некоторых фундаментальных методах программирования:
Подпрограммы.
Сопрограммы.
Программы-интерпретаторы — конкретно описан (с программами на ассемблере MMIX) симулятор MMIX.
Далее — информационные структуры.
Кнут начинает с простейших вещей: про массивы и списки, про стеки, очереди и деки (я впервые про дек прочитал именно у него — аж в году примерно 1973, когда первый раз купил первый том). Про списки — подробно, разные виды.
Далее — деревья.
Классика — обход деревьев, представление бинарных деревьев, другие виды деревьев (но без балансированных — это в другом томе).
Довольно большая математическая часть о деревьях.
Но, внезапно, глава о сборке мусора — самая классика. Аж 5 алгоритмов маркировки узлов!
Далее — многосвязные структуры. Тут, между прочим, описано, как структуры ранее представлялись в COBOL и PL-1.
И получилось элементарное введение в реляционные таблицы.
Но далее — самое интересное из первого тома: динамическое распределение памяти.
Это — готовый раздел для изучения в курсе, например, по системному программированию или операционным системам.
Кнут описывает собственные исследования системы динамического распределения памяти и пишет, что основная проблема — фрагментация.
И описывает стратегии выделения памяти и свой собственный метод борьбы с фрагментацией — метод Кнута.
Также достаточно подробно описан метод близнецов.
В общем, я реально использую этот материал в лекциях.
Что еще хочется отметить (про все тома).
Огромное количество заданий-упражнений.
Каждой задание помечено числом, обозначающим трудность (Кнут об этом пишет в предисловии-введении).
И самое важное — есть ответы на все задания.
В первом томе ответы занимают 150 страниц (521-683).
Даже в номер 0 ответы к упражнениям занимают примерно 25 страниц (из 160).
Еще отмечу.
Алгоритмы сначала описываются на простом человеческом языке в виде последовательности шагов.
Очень часто приводится рисунок-схема алгоритма.
И только потом дается программа (не всегда, некоторые алгоритмы предлагается запрограммировать в виде упражнений)
Том 2 я использовал меньше, но содержание — впечатляет:
Глава 3. Случайные числа (у Кнута сквозная нумерация глав во всех томах).
Здесь про генерацию случайных чисел и статистические критерии.
Глава 4. Арифметика.
Здесь позиционные системы счисления (между прочим, про троичную систему счисления написано),
преобразование между системами счисления во все стороны (умножением и делением).
Арифметика чисел с плавающей точкой (всем, кто спрашивает про сравнение дробных чисел — сюда).
Арифметика многократной точности — здесь про быстрое умножение длинных чисел, про алгоритм Карацубы (тоже впервые читал у Кнута).
Арифметика рациональных чисел (привет опять алгоритму Евклида).
Полиномиальная арифметика, операции со степенными рядами.
В общем, можно использовать по полной для изучения математических основ шифрования и кодирования.
(например, в книжке Блейхута: http://www.ozon.ru/context/detail/id/8775180/ как минимум половина этого материала излагается)
Если нужно изучать позиционные системы счисления — ничего более объемного мне не встречалось.
Даже про дробное основание системы счисления Кнут написал.
И опять ответы к упражнениям — 200 страниц!
Том 3 — наиболее часто используемый том.
Глава 5. Сортировка.
В начале идет математика — комбинаторные свойства перестановок (и еще каждый алгоритм сортировки анализируется подробнейшим образом).
Потом сортировки. Но классификация у Кнута несколько своя:
Внутренняя сортировка.
Оптимальная сортировка.
Внешняя сортировка.
В первой части он описывает (очень подробно) сортировку вставками, сортировку обменами, сортировку слиянием, сортировку методом распределения.
Сортировка вставками, бинарными вставками и Шелла — почему-то сортировка Шелла отнесена Кнутом к сортировке вставок.
Описание алгоритма занимает не очень много места, а вот анализ и статистика — раза в три больше.
И важно, что здесь есть сортировка вставками списков — чего практически нет нигде (потом расскажу, где еще есть... )
Обменная сортировка — это пузырек.
Но модификации Кнут подробно не рассматривает.
Зато здесь описана параллельная сортировка Бэтчера и быстрая сортировка Хоора.
И здесь же — поразрядная сортировка, трактуемая как обменная — по старшему разряду.
Сортировка выбором — классика.
Тут же — пирамидальная сортировка. Кнут описывает усовершенствование выбора и естественным путем приходит к пирамидальной.
Ну, и здесь же — о приоритетных очередях, ибо основаны на пирамидах.
Сортировка слиянием — классика. Но Кнут дает несколько разновидностей слияния. И описывает сортировку списков слиянием.
Распределенная сортировка — это блочная сортировка. Исходные записи распределяются по блокам, а потом сливаются.
Но описывает Кнут здесь поразрядную сортировку по младшему разряду, причем сортирует список.
Оптимальная сортировка — это дополнительный анализ алгоритмов сортировки на предмет минимального и среднего числа сравнений.
Но здесь описываются сети сортировок и естественно, анализ.
Внешняя сортировка сейчас менее актуальна, но там описывается огромное количество разнообразных методов.
Большинство — варианты слияния.
Но есть и поразрядная внешняя, и осциллирующая.
И отдельно — особенности внешней сортировки на дисках и барабанах...
Глава 6. Поиск — это наше все...
Последовательный поиск: простой, с барьером, самоорганизующийся "файл" — первый раз у него прочитал.
Бинарный поиск, однородный бинарный поиск (3 модификации), фибоначчиев поиск, интерполяционный поиск — в сортированном массиве.
Далее поиск в бинарном дереве (для вставки)- сортировка вставкой в бинарное дерево (обходы были в первом томе).
И понеслась про оптимальные бинарные деревья — анализ. Есть, например, такой параграф: Оптимальные бинарные деревья и энтропия...
Далее балансированные деревья. Тут подробнейшим образом про АВЛ-деревья. Про красно-черные — нету.
Сильно ветвящиеся деревья — подробно о В-деревьях.
Цифровой поиск — это я не очень внимательно читал. Знатокам, наверное, все скажет английское название trie searh.
Переведено, как "лучевой поиск". Есть некий алгоритм "Патриция".
Ну, и — хеширование. Подробнейшим образом: хеш-функции, коллизии.
Важно, что описывается модификация Брента, которая улучшает время поиска при почти заполненной таблице — нигде больше не встречал.
Описывается также удаление из хеш-таблицы.
Подробнейший анализ с таблицами и графиками.
В общем — очень рекомендую.
Да, ответов к упражнениям порядка 160 страниц.
4 том. Часть 1.
Глава 7. Комбинаторный поиск — единственная глава.
Фактически это не алгоритмы, а книжка по отдельным главам дискретной математики.
С алгоритмами и без программ.
Теорем едва ли не больше алгоритмов...
Огромное количество заданий и упражнений.
Но это не студенческие задания и упражнения, а продолжение темы соответствующей главы.
Многие нюансы-особенности-развитие научных результатов и алгоритмов рассматриваются именно как задачи для решения.
Начинает Кнут с головоломок (пары Лэнгфорда и ортогональные латинские квадраты).
Но потом описывает составленный им словарь пятибуквенных английских слов.
И на этом словаре начинает показывать комбинаторные алгоритмы.
И переходит к графам, начиная с графов слов на этом словаре.
Основы графов — это у него примерно 50 страниц до основных тем книжки.
Минимальный ликбез по данной теме — вполне на уровне.
Тут я с удивлением отметил, что примечания переводчика относятся не к переводу, а непосредственно к графам...
Например, в дополнение к примерам графов Кнута переводчик показывает аналогичные примеры из нашей жизни:
граф республик СССР, граф областей Украины...
И в дальнейшем переводчик показывает наименьшее вершинное покрытие и наибольшее независимое множество для "наших" графов.
Это все было у Кнута до первого раздела главы 7. Дальше — классика.
— Основы булевой алгебры
— Булевы вычисления
— Битовые трюки и технологии. Тут сам Кнут в качестве развития темы называет книжку Уоррена "Алгоритмические трюки для программистов".
— Бинарные диаграммы решений. Тут у него существенно пересекается с графами.
Имеется ввиду "бинарная диаграмма решений для булевой функции..." — это прямо цитата из книжки.
Тут я совсем чайник...
А далее — Генерация всех возможных объектов.
— n-кортежи
— перестановки, сочетания, разбиения
— разбиение множеств
— все деревья.
Тут он помимо всего прочего много и подробно про коды Грея и про способы их вычисления рассказывает.
Ну, и ответов к упражнениям — более 300 страниц (577-904)!
Некое резюме по книжкам Кнута.
Стиль книжек — совсем не для студентов.
Это скорее систематизация научных знаний — чем дальше по нумерации, тем сильнее это видно.
Кнута сложно читать выборочно. Хотя отдельные темы (особенно 2 и 3 том) можно.
Кроме основного текста нужно смотреть задачи и упражнения — это практически обязательно.
И обязательно смотреть ответы — практически это продолжение чтения основного текста.
Далее по новым книжкам — отдельными постами.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
S>А по структурам данных ничего раньше не советовали? Может есть хорошая подборка?
В этом же посте далее будут другие книжки.
Но ведь и у Кнута структуры данных описываются: стеки, очереди, деки, списки, деревья, хеш-таблицы. Какие еще нужны?
До графов он еще не дошел даже в 4 томе...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Цифровой поиск — это я не очень внимательно читал. Знатокам, наверное, все скажет английское название trie searh. LVV>Переведено, как "лучевой поиск". Есть некий алгоритм "Патриция".
ага. а linear probing — как линейное исследование. ну их нафиг с такими переводами
LVV>Важно, что описывается модификация Брента, которая улучшает время поиска при почти заполненной таблице — нигде больше не встречал.
Здравствуйте, LaptevVV, Вы писали:
LVV>Но ведь и у Кнута структуры данных описываются: стеки, очереди, деки, списки, деревья, хеш-таблицы. Какие еще нужны?
Вы считаете этого достаточно чтобы пройти собеседования в серьёзных конторах, таких как MS и Google?
S>Вы считаете этого достаточно чтобы пройти собеседования в серьёзных конторах, таких как MS и Google?
Если вы будете знать эти структуры на таком уровне, как описано в этих книгах — да, более чем.
Но кроме структур надо еще много других, жизненных знаний. Технических.
Здравствуйте, SkyDance, Вы писали:
S>>Вы считаете этого достаточно чтобы пройти собеседования в серьёзных конторах, таких как MS и Google?
SD>Если вы будете знать эти структуры на таком уровне, как описано в этих книгах — да, более чем.
Здравствуйте, Submitter, Вы писали: S>То есть книг Кнута достаточно?
Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, Submitter, Вы писали: S>>То есть книг Кнута достаточно? __>Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее
Поддержу. IMHO, у Кнута просто фенонменально занудные книги. Точно не чтиво для фана.
Разве что для тех, у кого 'вкусы очень специфичны'.
Здравствуйте, __kot2, Вы писали:
__>Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее
ты просто не видел проф. программистов
а если серьёзно, то в советское время альтернативы ему не было. я знаю только вирта, но он появился ллет на 10-20 позже и по объёму не тянул и на один том кнута. а учитывая что интрентов и википедий тогда не было, это был просто единственно возмоджный источник знаний. не зря его называли библией программиста
__>Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее
Ну, посмотри на меня...
Я еще в советское время читал...
Я ж говорю — 1 и 3 том прямо в лекциях использую.
2 том читал выборочно, так как по молодости лет считал, что этот том — не для программистов....
Сейчас читаю 4 том, это практически дискретная математика, а не структуры данных.
Теорем (с доказательствами) больше, чем алгоритмов.
Но Кнут ИМХО больше математик.
И в книгах систематизирует знания (много исторических сведений), а не описывает структуры данных для учебного курса.
А программирование у него вроде необходимого инструмента.
Он жеж и TeX создавал для того, чтобы можно было математические тексты на компе набирать...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>С момента опубликования старого списка прошло уже много времени.
Хорошая идея. Может вики сделать?
Не забудьте пожалуйста сказать про недавно изданные книги.
Род Стивенс. "Алгоритмы. Теория и практическое применение"
Дж. Клейнберг Дж., Е. Тардос "Алгоритмы: разработка и применение. Классика Computers Science"
Немного раньше
Кормен "Алгоритмы. Вводный курс"
Санджой Дасгупта, Христос Пападимитриу "Алгоритмы"
И переизданные недавно
Альфред В. Ахо, Джон Э. Хопкрофт "Структуры данных и алгоритмы"
Роберт Лафоре "Структуры данных и алгоритмы в Java"
Похоже что по алгоритмам единственная область где на русский переведены все хорошие книги.
Здравствуйте, Submitter, Вы писали:
LVV>>Но ведь и у Кнута структуры данных описываются: стеки, очереди, деки, списки, деревья, хеш-таблицы. Какие еще нужны? S>Вы считаете этого достаточно чтобы пройти собеседования в серьёзных конторах, таких как MS и Google?
Это же классика:
Bill Gates:
If you think you're a really good programmer... read (Knuth's) Art of Computer Programming... You should definitely send me a résumé if you can read the whole thing.
LVV>>С момента опубликования старого списка прошло уже много времени. HH>Хорошая идея. Может вики сделать?
Ну, если кто-нить из команды захочет — пусть сделают.
Я уж по старинке... HH>Не забудьте пожалуйста сказать про недавно изданные книги.
Про все это я собирался написать. И еще есть несколько весьма достойных.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, SkyDance, Вы писали:
S>>То есть книг Кнута достаточно?
SD>Если вы их сможете понять, и решить упражнения (ну, понятное дело, кроме Великой Теоремы Ферма, которую он там под задачу замаскировал) — более чем.
И зачем человеку, который все это может, проходить собеседование в гугле и мелкософте?
Здравствуйте, LaptevVV, Вы писали:
LVV>Я ее читал еще в то время... LVV>Как и последующую книгу Гриса.
Книгу Дейкстры куда как более интересно читать, чем Гриса. Грис — унылый институтский учебник, а Дейкства пишет лихо, со своим весьма своеобразным чувством юмора, с тонким сарказмом.
В старом списке были указаны предыдущие издания. С тех пор появились переводы новых изданий.
Кормен.
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-полноту.
В общем выводы — полезно иметь сразу оба тома.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Мне известны три перевода Рода Стивенса.
Сначала была "Готовые алгоритмы на Бейсике"
Потом практически копипаст с нее: 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. Головоломки, встречающиеся на собеседованиях. Как задавать вопросы с подвохом и как отвечать на вопросы с подвохом.
В общем, еще раз рекомендую именно начинающим.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
У Никлауса Вирта по структурам данных выходила практически одна и та же книга — на разных языках программирования.
Сначала была "Алгоритмы+структуры данных = программы".
Была переведена в издательстве Мир еще аж в 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. Переводчик написал замечательное предисловие и послесловие.
В частности, описал цикл Дейкстры (кто тут упоминал книжку Дисциплина программирования ?)
Рекомендую как начальную книжку по теме.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Книжки МакКоннелла по алгоритмам переводились не менее 2 раз.
У меня на руках такая:
Дж. МакКоннелл. Анализ алгоритмов. Активный обучающий подход.
3-е дополненное издание. — М.: Техносфера, 2009. — 416 с.
Книжка весьма неплохая.
Глав всего 11. К каждой главе есть упражнения.
В начале каждой главы определены цели изучения и даны советы по изучению.
Видимо, это и называется активным обучающим подходом...
В конце книги приведены ответы к некоторой части упражнений.
Алгоритмы приводятся на псевдокоде, похожем на паскаль (как у Рода Стивенса).
Иногда с вкраплениями неформальных действий (как у Вирта в методе пошагового уточнения).
Алгоритмы с псевдокода легко конвертируются в Си-подобный язык.
Математики мало. Фактически и не математика (как у Кнута), а просто вывод простых комбинаторных формул в некоторых алгоритмах.
Содержание:
1. Основы анализа алгоритмов.
Ну, здесь достаточно простым языком объясняется, что анализируем, скорости роста, нижние границы...
Вспоминаем элементарную математику, логарифмы, суммы, факториалы и т.п.
2. Рекурсивные алгоритмы.
Тут математика рекуррентных соотношений и собственно анализ рекурсивных алгоритмов с их помощью.
Рассматриваются три задачи: пара ближайших точек, выпуклая оболочка и генерация перестановок.
Все довольно подробно объясняется словами, а вот математического анализа как такового нет. Так — пара формул приводится, и все.
Здесь же про связь рекрсии со стеком.
3. Поиск и выборки.
Поиск линейный и двоичный. Здесь анализ как раз есть — длинные формулы суммирования на пол-страницы.
Выборка — это поиск к-то по величине значения в массиве.
4. Сортировка. (ответы на упражнения начинаются с главы 4).
Тут классика: вставки, пузырек, Шелла, поразрядная (почему-то названная корневой),
пирамидальная, быстрая, слияние и внешнее многофазное слияние.
Анализ худшего и анализ среднего случаев. И в зависимости от сортировки — нюансы.
5. Численные алгоритмы.
Конспективная глава: схема Горнера, умножение матриц по Винограду и Штрассену,
решение систем линейных уравнений по схеме Жордана-Гаусса.
Никаких рассуждений не приводится, просто сразу даются таблички с формулами количества операций.
6. Алгоритмы формальных языков. В книжках по алгоритмам этого практически не встречается.
Главу смело можно рекомендовать как введение в формальные грамматики и автоматы.
Конечные автоматы детерминированные и недетерминированные, регулярные выражения и регулярные грамматики.
Эквивалентности, преобразование автомата в программу, проектирование, ограничения и возможности.
МП-автоматы детерминированные и недетерминированные, контекстно-свободные грамматики,
преобразование грамматик, нормальная форма Грейбах.
Преобразование грамматики в МП-автомат, проектирование МП-автомата, ограничения и возможности.
Введение в синтаксический разбор.
Теорем нет, математики нет, и изложение очень практическое. С элементами теории формальных языков, грамматик и автоматов.
7. Сравнение с образцом.
Это поиск подстроки в строке.
Простой, конечно-автоматный упоминается, Кнута-Морисса-Пратта — основное содержание главы.
И немного про приблизительное сравнение строк. Анализ есть не везде, а где есть — очень лаконично, буквально 1 абзац.
8. Алгоритмы на графах.
Тут классика в минимальном объеме: обходы, поиск путей, остовное дерево.
Алгоритм определения компонент двусвязности, разбиение множеств (на массивах.
А вот следующая глава — это фишка книги.
9. Параллельные алгоритмы.
Сначала — классификация Флинна, описывается неформально каждый класс.
Потом кратенькое введение в архитектуры параллельных машин.
Важный параграф — Модель памяти PRAM. Простые операции в разных моделях PRAM.
И понеслась — параллельные алгоритмы поиска, сортировки (четно-нечетная, на линейных сетяхи др.).
Численные — параллельное умножение матриц, решение системы линейных уравнений.
Параллельные алгоритмы на графах.
10. Вычислимое и невычислимое.
Здесь все про машины Тьюринга (много всяких описано) и NP — довольно неплохо, на 50 страницах.
11. Другие алгоритмические инструмента.
Здесь собраны жадные алгоритмы, алгоритмы с возвратом, ветвей и границ,
вероятностные (в частности, Монте-Карло, Лас-Вегас, Шервудские).
И динамическое программирование.
Хорошая глава.
И в приложении еще Генерирование случайных чисел есть.
В общем — весьма неплохая книжка.
Обращаю внимание — практически нет структур данных. Ничего нет о деревьях.
Зато есть темы, которые в других книжках совсем не затрагиваются.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Джон Бентли. Жемчужины программирования, 2-е издание. — СПб.: Питер, 2002.- 272 с.
Я читал еще первое издание.
Замечательная книга.
Книга не является учебником по алгоритмам.
Написана неформально, в виде дружеского разговора с читателем.
Но упражнения есть и есть даже решения.
Это даже не сами формальные решения, а больше размышления и соображения (или ссылки), приводящие к решениям.
Содержание приведу.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, 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
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>Неплохой перевод, а главное — приводятся примеры из практики, т.е. постановка задачи и выбор решения.
Рассмотрю подробнее.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
SVZ>>"Основы Систем Баз Данных" Изд. "Финансы и статистика" Москва 1983 SVZ>>"Principles of database systems" LVV>Есть такая книжка. Но это лучше писать в отдельный список по БД.
В список по БД лучше подходит "Системы баз данных" Гарсии-Молины и того же Ульмана.
А эта где-то на границе, ближе к прикладному использованию структур данных.
SVZ>>Акцент делается на то, что у СУБД "под капотом". Будет полезна тем, кто разрабатывает разлапистые структуры данных. LVV>Есть еще 2 современных на ту же тему. LVV>А начинать надо с Мартина, наверное...
Давай, Валерий Викторович, интересно почитать что-то свежее.
А то книг про "структуры данных для самых маленьких" только ленивый не пишет. А вот о проектировании структур данных и их правильном эффективном применении книг попадается мало.
_____________________
С уважением,
Stanislav V. Zudin
SVZ>Давай, Валерий Викторович, интересно почитать что-то свежее. SVZ>А то книг про "структуры данных для самых маленьких" только ленивый не пишет. А вот о проектировании структур данных и их правильном эффективном применении книг попадается мало.
Ну, Кавасаки я уже получил. Когда руки дойдут прочитать — пропишу
Но из практики программирования могу совершенно определенно сказать:
применять изощренные сложные структуры данных приходится чрезвычайно редко.
Как правило, чем проще структура данных, тем проще и понятней алгоритм ее обработки.
Да еще и ошибок в простом алгоритме совершается значительно меньше.
Скорость сейчас не так проблематична, ибо имеем многоядерный проц и практически всегда можно ускорить программу,
распараллелив ее на несколько потоков.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
SVZ>>Давай, Валерий Викторович, интересно почитать что-то свежее. SVZ>>А то книг про "структуры данных для самых маленьких" только ленивый не пишет. А вот о проектировании структур данных и их правильном эффективном применении книг попадается мало. LVV>Ну, Кавасаки я уже получил. Когда руки дойдут прочитать — пропишу
LVV>Но из практики программирования могу совершенно определенно сказать: LVV>применять изощренные сложные структуры данных приходится чрезвычайно редко.
Хе, практика-то у всех разная.
LVV>Как правило, чем проще структура данных, тем проще и понятней алгоритм ее обработки. LVV>Да еще и ошибок в простом алгоритме совершается значительно меньше.
А моя практика программирования показала, что алгоритм первичен.
Сперва выбирается алгоритм, а под него уже проектируются структуры данных. А там от требований зависит — простые структуры получатся или не очень.
Бо взять линейный алгоритм и превратить его в O(N^3) неудачной структурой данных — это как два байта переслать.
И, кстати, распространенная в книжках идея, что заграница абстракция/инкапсуляция нам поможет не переделывать данные при замене алгоритма — опасное заблуждение. Иногда переделывать приходится.
LVV>Скорость сейчас не так проблематична, ибо имеем многоядерный проц и практически всегда можно ускорить программу, LVV>распараллелив ее на несколько потоков.
Скорости, как и памяти, много не бывает. Всегда найдется, чем занять.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Pzz, Вы писали:
SD>>Если вы их сможете понять, и решить упражнения (ну, понятное дело, кроме Великой Теоремы Ферма, которую он там под задачу замаскировал) — более чем.
Pzz>И зачем человеку, который все это может, проходить собеседование в гугле и мелкософте?
А где предлагаете работать со всеми этими знаниями?
SVZ>А моя практика программирования показала, что алгоритм первичен.
Ну, еще Фредерик Брукс сказал (как давно это было!):
Покажите мне блок–схемы, не показывая таблиц, и я останусь в заблуждении.
Покажите мне ваши таблицы, и блок–схемы, скорее всего, не понадобятся: они будут очевидны.
SVZ>Скорости, как и памяти, много не бывает. Всегда найдется, чем занять.
Ну, это да...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Submitter, Вы писали:
SD>>>Если вы их сможете понять, и решить упражнения (ну, понятное дело, кроме Великой Теоремы Ферма, которую он там под задачу замаскировал) — более чем.
Pzz>>И зачем человеку, который все это может, проходить собеседование в гугле и мелкософте?
S>А где предлагаете работать со всеми этими знаниями?
Гугль и микрософт — это фабрика с конвеером. В таком месте хорошо поработать в молодости, а потом можно и что-нибудь поинтереснее себе подыскать.
Pzz>Гугль и микрософт — это фабрика с конвеером. В таком месте хорошо поработать в молодости, а потом можно и что-нибудь поинтереснее себе подыскать.
Молодость когда заканчивается?
Здравствуйте, dr. Acula, Вы писали:
Pzz>>Гугль и микрософт — это фабрика с конвеером. В таком месте хорошо поработать в молодости, а потом можно и что-нибудь поинтереснее себе подыскать. DA>Молодость когда заканчивается?
Когда трудовые сбережения достигают такого размера, что не боишься остаться без зарплаты на полгода.
Pzz>>>Гугль и микрософт — это фабрика с конвеером. В таком месте хорошо поработать в молодости, а потом можно и что-нибудь поинтереснее себе подыскать. DA>>Молодость когда заканчивается? Pzz>Когда трудовые сбережения достигают такого размера, что не боишься остаться без зарплаты на полгода.
Вот прямо в кэше/на счету или как-то еще?
Меня как-то не греет перспектива проедать сбережения даже полгода, если честно.
Значит ли это, что я ещё молодой и глупый?
Здравствуйте, dr. Acula, Вы писали:
Pzz>>Когда трудовые сбережения достигают такого размера, что не боишься остаться без зарплаты на полгода. DA>Вот прямо в кэше/на счету или как-то еще?
Ну да.
DA>Меня как-то не греет перспектива проедать сбережения даже полгода, если честно. DA>Значит ли это, что я ещё молодой и глупый?
А на что они еще нужны, кроме как чтобы их тратить?
Pzz>>>Когда трудовые сбережения достигают такого размера, что не боишься остаться без зарплаты на полгода. DA>>Вот прямо в кэше/на счету или как-то еще? Pzz>Ну да.
Ок.
DA>>Меня как-то не греет перспектива проедать сбережения даже полгода, если честно. DA>>Значит ли это, что я ещё молодой и глупый? Pzz>А на что они еще нужны, кроме как чтобы их тратить?
Ну я не знаю, типичное "улучшение жилищных условий", путешествия, машины, девочки, наркотики развлечения.
Или предполагается, что "полгода бе работы" не отличаются по стилю жизни от "полгода на работе"?
Ну тогда-то да, согласен.
Здравствуйте, dr. Acula, Вы писали:
Pzz>>А на что они еще нужны, кроме как чтобы их тратить? DA>Ну я не знаю, типичное "улучшение жилищных условий", путешествия, машины, девочки, наркотики развлечения. DA>Или предполагается, что "полгода бе работы" не отличаются по стилю жизни от "полгода на работе"? DA>Ну тогда-то да, согласен.
Ну почему не отличается? Без работы появляется очень много свободного времени. Можно попробовать переделать все дела, которые годами откладывались из-за работы. Если повезет, можно даже успеть
SVZ>На мой взгляд книга интереснее, чем книги Седжвига, много уделяется деталям реализации структур данных. SVZ>Но перевод хреновенький. Приходится в уме переводить на аглицкий, чтобы понять о чем речь.
Читать такие книги на русском это моветон. Даже отбросив корявости переводов в русской терминологии остается куча неуклюжих заимок которые только путают, вместо того чтобы быть самовыразительными как английский эквивалент.
Как например без подсказок понять что такое планарный граф? В английском от слова plane все сразу понятно.
Ну или остовное (wtf?) дерево vs spanning tree.
Куча такого.
R>1) Алгоритмы. Теория и практическое применение R>Род Стивенс
У меня описано 2 книжки Стивенса R>2)Построение компиляторов R>Никлаус Вирт
Прописал здесь Алгоритмы и структуры данных
Книжку по компиляторам ИМХО надо в другой подборке давать — по компиляторам.
Там вообще-то ДОФИГА книжек. R>3)Алгоритмические трюки для программистов R>Генри С. Уоррен мл.
Есть моя рецензия на сайте, и рецензия на Озоне.
Но пропишу здесь R>4)ведение в надежное и безопасное распределенное программирование R>Кристиан Качин , Рашид Гуерру , Луис Родригес
Эту вообще не знаю. Поищу.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
R>>>3)Алгоритмические трюки для программистов R>>>Генри С. Уоррен мл. LVV>>Есть моя рецензия на сайте, и рецензия на Озоне. R>На каком сайте?Здесь на рсдн, в Книгах. О первом издании. А на Озоне — о втором.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
LVV>Книжки МакКоннелла по алгоритмам переводились не менее 2 раз.
Обнаружил у себя предыдущее издание 2006 года (естественно — я ж не мог ее пропустить... ).
Книжка отличается.
Перечитал предисловие книжки 2009 года.
Там написано, что изменения, внесенные в это (2-е) издание сделаны с целью привести содержание
в соответствие с требованиями АСМ к курсу CS 210 "Анализ и разработка алгоритмов".
Однако первое издание отличается наличием замечательного дополнения,
написанного Михаилом Васильевичем Ульяновым (автор книги "Ресурсно-эффективные компьютерные алгоритмы" — отличная книга!).
Дополнение состоит из 3 глав.
Первая — классика теории алгоритмов:
анализ определений алгоритма, машина Тьюринга, машина Поста, неразрешимые проблемы, классы сложности алгоритмов, проблема P = NP.
Вторая глава — очень практическая.
Тут конкретно разбор и масса примеров оценки трудоемкости (термин Ульянова) алгоритмов,
в том числе подробно об оценках рекурсивных алгоритмов.
Третья глава — об эвристических алгоритмах, обычно связываемых с ИИ.
Генетические алгоритмы и довольно подробное описание идеи муравьиного алгоритма.
И в частности, применение этого алгоритма для решения задачи коммивояжера.
Так что рекомендую и эту книжку (а заодно — обратите внимание на книжки М.В.Ульянова).
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Не знаю было, случайно обнаружил, что довольно не плохие книги у Окулова
Абстрактные типы данных.
Программирование в алгоритмах.
Динамическое программирование.
Дискретная математика. Теория и практика решения задач по информатике. Учебное пособие.
Ханойские башни.
Алгоритмы обработки строк.
Методика решения задач по информатике. Международные олимпиады.
материал подан хорошо и подробно, с примерами, задачами и решением задач.
SL>Не знаю было, случайно обнаружил, что довольно не плохие книги у Окулова
Да, я знаю. У меня полный список — буду писать.
SL>Абстрактные типы данных. SL>Программирование в алгоритмах. SL>Динамическое программирование. SL>Дискретная математика. Теория и практика решения задач по информатике. Учебное пособие. SL>Ханойские башни. SL>Алгоритмы обработки строк. SL>Методика решения задач по информатике. Международные олимпиады.
Еще две книжки:
Абстрактные типы данных.
Алгоритмы компьютерной арифметики. SL>материал подан хорошо и подробно, с примерами, задачами и решением задач.
Да, Окулов хорошо пишет.
И книжки — не фолианты типа Кормена, а небольшого объема, но достаточно полно по каждой теме.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
R>Читать такие книги на русском это моветон. Даже отбросив корявости переводов в русской терминологии остается куча неуклюжих заимок которые только путают, вместо того чтобы быть самовыразительными как английский эквивалент. R>Как например без подсказок понять что такое планарный граф? В английском от слова plane все сразу понятно. R>Ну или остовное (wtf?) дерево vs spanning tree. R>Куча такого.
Книжки надо читать.
Стандартные термины теории графов.
Планарный граф — граф, который можно нарисовать на плоскости без пересечения ребер.
Остовное дерево — дерево (получающенеся из исходного графа), имеющее то же множество вершин,
что и исходный граф, но минимальное количество ребер.
Если в графе n вершин, то в дереве n-1 ребро.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Книжки надо читать. :) LVV>Стандартные термины теории графов.
«Стандартные термины теории графов» в русскоязычной традиции бывают весьма запутаны. Например, «cycle» переводят как «контур», а «циклом» называют другие понятие. «Directed» переводят как «ориентированный», а не «направленный». И это вызывает путаницу с (реже используемым) термином «oriented» (отдельный смысл, не тот, что у «directed»). Совершенно стандартная, общеизвестная и узнаваемая аббревиатура DAG на языке здорового человека будет «направленный ациклический граф» (прямая калька с «directed acyclic graph»), но на традиционном жаргоне русскоязычной теории графов «правильно» — «ориентированный бесконтурный граф».
Так что привычка читать переведённую литературу может сыграть злую шутку, когда надо будет читать или писать англоязычные статьи и книги.
Q>Так что привычка читать переведённую литературу может сыграть злую шутку, когда надо будет читать или писать англоязычные статьи и книги.
Я просто классиков теории графов читал.
И русских, и переведенных в СССР — там переводили в соответствии с нашей терминологией.
Поэтому разночтений не возникало.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>С момента опубликования старого списка прошло уже много времени.
Не хватает для полноты картиры книг по алгоритмам машинного обучения et al. по тематике.
). Между прочим — аж 10 страниц... 
Перекуём баги на фичи!
я думал, уже совсем забыли Билли.
)). 
