Новый список книг по алгоритмам
От: LaptevVV Россия  
Дата: 25.03.16 07:46
Оценка: 106 (14)
С момента опубликования старого списка прошло уже много времени.
Да и пожелание было подробнее аннотации написать.
Пост будет большой, поэтому буду дополнять-редактировать по мере наличия свободного времени.
Итак начнем опять с классики:
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 том) можно.
Кроме основного текста нужно смотреть задачи и упражнения — это практически обязательно.
И обязательно смотреть ответы — практически это продолжение чтения основного текста.

Далее по новым книжкам — отдельными постами.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Отредактировано 26.03.2016 13:36 LaptevVV . Предыдущая версия . Еще …
Отредактировано 25.03.2016 16:39 LaptevVV . Предыдущая версия .
Отредактировано 25.03.2016 8:00 LaptevVV . Предыдущая версия .
Отредактировано 25.03.2016 7:57 LaptevVV . Предыдущая версия .
Re: Норвый список книг по алгоритмам
От: Submitter  
Дата: 25.03.16 07:52
Оценка: 3 (1)
Здравствуйте, LaptevVV, Вы писали:

А по структурам данных ничего раньше не советовали? Может есть хорошая подборка?
Re[2]: Норвый список книг по алгоритмам
От: LaptevVV Россия  
Дата: 25.03.16 08:01
Оценка:
S>А по структурам данных ничего раньше не советовали? Может есть хорошая подборка?
В этом же посте далее будут другие книжки.
Но ведь и у Кнута структуры данных описываются: стеки, очереди, деки, списки, деревья, хеш-таблицы. Какие еще нужны?
До графов он еще не дошел даже в 4 томе...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: Новый список книг по алгоритмам
От: BulatZiganshin  
Дата: 25.03.16 08:05
Оценка:
Здравствуйте, LaptevVV, Вы писали:

LVV>Цифровой поиск — это я не очень внимательно читал. Знатокам, наверное, все скажет английское название trie searh.

LVV>Переведено, как "лучевой поиск". Есть некий алгоритм "Патриция".

ага. а linear probing — как линейное исследование. ну их нафиг с такими переводами

LVV>Важно, что описывается модификация Брента, которая улучшает время поиска при почти заполненной таблице — нигде больше не встречал.


https://en.wikipedia.org/wiki/Cuckoo_hashing
Люди, я люблю вас! Будьте бдительны!!!
Re[2]: Норвый список книг по алгоритмам
От: Кодт Россия  
Дата: 25.03.16 08:22
Оценка: 26 (1)
Здравствуйте, Submitter, Вы писали:

S>А по структурам данных ничего раньше не советовали? Может есть хорошая подборка?


Крис Окасаки же! Тут недавно пробегал анонс русского перевода. http://rsdn.ru/forum/decl/6388649.1
Автор: HrorH
Дата: 19.03.16
Перекуём баги на фичи!
Re[2]: Норвый список книг по алгоритмам
От: SkyDance Земля  
Дата: 25.03.16 09:08
Оценка: +2
S>А по структурам данных ничего раньше не советовали? Может есть хорошая подборка?

Кормен и Седжвик же, классика.
Re: Новый список книг по алгоритмам
От: SkyDance Земля  
Дата: 25.03.16 09:11
Оценка: 83 (7)
Добавлю в список:

Toby Segaran, Jeff Hammerbacher "Beautiful Data: The Stories Behind Elegant Data Solutions"

Потрясающе толковая книга по современным алгоритмам. Многие вещи кажутся такими очевидными, когда о них прочитаешь в этой книге.

Собственно, я эту книгу нашел тогда, когда потребовалось решить практическую задачу (разделить текст без пробелов на слова).
Re[3]: Норвый список книг по алгоритмам
От: Submitter  
Дата: 25.03.16 09:47
Оценка:
Здравствуйте, LaptevVV, Вы писали:

LVV>Но ведь и у Кнута структуры данных описываются: стеки, очереди, деки, списки, деревья, хеш-таблицы. Какие еще нужны?


Вы считаете этого достаточно чтобы пройти собеседования в серьёзных конторах, таких как MS и Google?
Re[3]: Норвый список книг по алгоритмам
От: LaptevVV Россия  
Дата: 25.03.16 10:52
Оценка:
SD>Кормен и Седжвик же, классика.
Дальше про них тоже напишу.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[4]: Норвый список книг по алгоритмам
От: SkyDance Земля  
Дата: 25.03.16 11:07
Оценка:
S>Вы считаете этого достаточно чтобы пройти собеседования в серьёзных конторах, таких как MS и Google?

Если вы будете знать эти структуры на таком уровне, как описано в этих книгах — да, более чем.
Но кроме структур надо еще много других, жизненных знаний. Технических.
Re[5]: Норвый список книг по алгоритмам
От: Submitter  
Дата: 25.03.16 11:17
Оценка:
Здравствуйте, SkyDance, Вы писали:

S>>Вы считаете этого достаточно чтобы пройти собеседования в серьёзных конторах, таких как MS и Google?


SD>Если вы будете знать эти структуры на таком уровне, как описано в этих книгах — да, более чем.


То есть книг Кнута достаточно?
Re[6]: Норвый список книг по алгоритмам
От: __kot2  
Дата: 25.03.16 15:40
Оценка: +4
Здравствуйте, Submitter, Вы писали:
S>То есть книг Кнута достаточно?
Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее
Re[7]: Норвый список книг по алгоритмам
От: bnk СССР http://unmanagedvisio.com/
Дата: 25.03.16 16:59
Оценка: +1
Здравствуйте, __kot2, Вы писали:

__>Здравствуйте, Submitter, Вы писали:

S>>То есть книг Кнута достаточно?
__>Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее

Поддержу. IMHO, у Кнута просто фенонменально занудные книги. Точно не чтиво для фана.
Разве что для тех, у кого 'вкусы очень специфичны'.
Re[7]: Норвый список книг по алгоритмам
От: BulatZiganshin  
Дата: 26.03.16 02:32
Оценка: +2
Здравствуйте, __kot2, Вы писали:

__>Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее


ты просто не видел проф. программистов

а если серьёзно, то в советское время альтернативы ему не было. я знаю только вирта, но он появился ллет на 10-20 позже и по объёму не тянул и на один том кнута. а учитывая что интрентов и википедий тогда не было, это был просто единственно возмоджный источник знаний. не зря его называли библией программиста
Люди, я люблю вас! Будьте бдительны!!!
Re[7]: Норвый список книг по алгоритмам
От: LaptevVV Россия  
Дата: 26.03.16 06:26
Оценка: +1
__>Кнут — зануда. Не знаю ни одного кто больше полтома осилил. Кормен читается легче и интереснее
Ну, посмотри на меня...
Я еще в советское время читал...
Я ж говорю — 1 и 3 том прямо в лекциях использую.
2 том читал выборочно, так как по молодости лет считал, что этот том — не для программистов....
Сейчас читаю 4 том, это практически дискретная математика, а не структуры данных.
Теорем (с доказательствами) больше, чем алгоритмов.
Но Кнут ИМХО больше математик.
И в книгах систематизирует знания (много исторических сведений), а не описывает структуры данных для учебного курса.
А программирование у него вроде необходимого инструмента.
Он жеж и TeX создавал для того, чтобы можно было математические тексты на компе набирать...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[2]: Новый список книг по алгоритмам
От: LaptevVV Россия  
Дата: 26.03.16 06:28
Оценка:
SD>Toby Segaran, Jeff Hammerbacher "Beautiful Data: The Stories Behind Elegant Data Solutions"
Кстати, легко находится в сети pdf-файл
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[6]: Норвый список книг по алгоритмам
От: SkyDance Земля  
Дата: 26.03.16 07:35
Оценка:
S>То есть книг Кнута достаточно?

Если вы их сможете понять, и решить упражнения (ну, понятное дело, кроме Великой Теоремы Ферма, которую он там под задачу замаскировал) — более чем.
Re: Новый список книг по алгоритмам
От: HrorH  
Дата: 26.03.16 07:40
Оценка: 3 (1) +2
Здравствуйте, LaptevVV, Вы писали:

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

Хорошая идея. Может вики сделать?
Не забудьте пожалуйста сказать про недавно изданные книги.
Род Стивенс. "Алгоритмы. Теория и практическое применение"
Дж. Клейнберг Дж., Е. Тардос "Алгоритмы: разработка и применение. Классика Computers Science"

Немного раньше
Кормен "Алгоритмы. Вводный курс"
Санджой Дасгупта, Христос Пападимитриу "Алгоритмы"

И переизданные недавно
Альфред В. Ахо, Джон Э. Хопкрофт "Структуры данных и алгоритмы"
Роберт Лафоре "Структуры данных и алгоритмы в Java"

Похоже что по алгоритмам единственная область где на русский переведены все хорошие книги.
Re[4]: Норвый список книг по алгоритмам
От: Evgeny.Panasyuk Россия  
Дата: 26.03.16 07:42
Оценка: +1
Здравствуйте, 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.

Re[2]: Новый список книг по алгоритмам
От: LaptevVV Россия  
Дата: 26.03.16 08:02
Оценка:
LVV>>С момента опубликования старого списка прошло уже много времени.
HH>Хорошая идея. Может вики сделать?
Ну, если кто-нить из команды захочет — пусть сделают.
Я уж по старинке...
HH>Не забудьте пожалуйста сказать про недавно изданные книги.
Про все это я собирался написать. И еще есть несколько весьма достойных.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.