LINUX.ORG.RU

Книги по проектированию алгоримов


0

3

Есть ли на русском языке литература по сабжу?

Интересует, какие есть методы «придумывания» алгоритмов для конкретной задачи? Например красно-черное дерево, в принципе ничего сложного, основано на рассмотрении разных возможных ситуаций после вставки/удаления. Но вот придумать его с нуля непростая (как мне кажется) задача (надо ведь еще осознавать что после всех манипуляций оно должно остаться сбалансированным).

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

★★★★

Ответ на: комментарий от baverman

Там кажется немного не об этом речь, там наоборот базовые концепции программирования и вычислений, разве нет? Я имел в виду не совсем это.

OxiD ★★★★
() автор топика

Алгоритм придумывания алгоритмов захотел? Жырно будет, учи готовое и придумывай по подобию того, что знаешь.

melkor217 ★★★★★
()

Многие алгоритмы придумывались «с фонаря», чисто интуитивно. Видел парочку алгоритмов в духе «доказать не удалось, но пока не найдено ни одного контрпримера».

melkor217 ★★★★★
()
Ответ на: комментарий от baverman

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

Потмоу что можно например реализовать 2-3 дерево вызвая тупо sort после каждой вставки, который будет вызывать cmp() который будет рекурсивно спускаться и находить минимальное значение в дереве.

А можно просто это минимальное значение поднимать снизу вверх и сортировка произойдет автоматически.

Вообщем хочу что-то типа «паттернов для построения рекурсивных алгоритмов»

Может у Кнута это есть? А то я 3ий том не дочитал.

OxiD ★★★★
() автор топика
Ответ на: комментарий от melkor217

2-3 дерево это как раз пример когда после просмотра описания алгоритма (после вставки узла надо отсортировать листья его родителя) можно написать какашку ;)

OxiD ★★★★
() автор топика
Ответ на: комментарий от OxiD

Ох, нет деревьев кроме AVL. Ну или хотя бы B-деревьев, если в память не влазит. Использование всего остального должно быть мотивировано %)

melkor217 ★★★★★
()
Ответ на: комментарий от OxiD

Тогда рекомендую ознакомится со стандартной библиотекой к своему языку, по части коллекций ­— какие вообще существуют. Как правило, к ним идет подробнейшая документация, в каких случаях применять, какова сложность добавления/извлечения элемента, потокобезопасность. После этого станет понятно когда что использовать. Только не надо писать свои велосипеды.

baverman ★★★
()
Ответ на: комментарий от baverman

Ну уж не знаю, тогда nginx это потрясающая коллекция велосипедов.

OxiD ★★★★
() автор топика

Ищешь книжку «как научить думать»? :) Не найдешь такой. Ну разве что изучай готовые алгоритмы, и применяй их на практике. Применяй - значит пиши реализацию сам, а не юзай готовую. На готовом не научишься. Конечно это не хорошо по отношению к заказчику и к команде. Но без здорового эгоизма не научишься.

dizza ★★★★★
()

«Алгоритмы. Построение и анализ» - но это перевод 2-го издания, а на английском уже есть 3-е издание (Introduction to Algorithms оно называется в оригинале). На английском есть еще Algorithms Design Manual, вроде неплохая

P.S. на русском была еще вроде книга Кнута по анализу алгоритмов

ott ★★★★★
()
Ответ на: комментарий от ott

да, называлась она «Математические методы анализа алгоритмов»

ott ★★★★★
()
Ответ на: комментарий от tensai_cirno

ну по проектированию в целом есть много хороших книг, тот же how to design programs, etc.

ott ★★★★★
()
Ответ на: комментарий от melkor217

Алгоритм придумывания алгоритмов, он же Теория Решения Изобретательских Задач (ТРИЗ) существует и гуглится по абривеатуре. Основано вроде в 70х годах Альтушлером.

Книги есть, советую книги Орлова - более интересное и современное изложение.

Dikar ★★
()

Ананий Левитин. Алгоритмы: введение в разработку и анализ. Ну и Кормен, конечно.

semantics
()
Ответ на: комментарий от OxiD

Потмоу что можно например реализовать 2-3 дерево вызвая тупо sort после каждой вставки, который будет вызывать cmp() который будет рекурсивно спускаться и находить минимальное значение в дереве.


А можно просто это минимальное значение поднимать снизу вверх и сортировка произойдет автоматически.


И? Выбирай оптимальный

Karapuz ★★★★★
()

Странно, автор, вроде знаешь Кнута. У Кнута по моему как раз об этом и написано. Кроме того, насколько мне известно, как таковой методологии разработки алгоритмов не существует. Понимание приходит с опытом написания многочисленных строк кода. Того же Кнута-то, далеко не все читали, но уважают. Просто потому, что человек изложил свой собственный опыт набранный за долгие годы деятельности в довольно понятном и доступном виде. Но все равно, для многих почему-то предпочтительным оказывается пройти процесс «открытия» многих истин самостоятельно.

nsf
()

>Интересует, какие есть методы «придумывания» алгоритмов для конкретной задачи

Учи матан. Иначе щас понакачаешь всяких книжек которые пишут всякие горе-советники.

Siado ★★★★★
()

> Например красно-черное дерево [...] придумать его с нуля непростая

Красно-чёрные деревья — это те же 2-3-4 деревья, так что есть такое подозрение, что их придумали не с нуля. Кстати, один и тот же человек сначала придумал B-деревья, а затем уже красно-чёрные.

ringill
()
Ответ на: комментарий от Siado

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

zfsed
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.