Category: it

Category was added automatically. Read all entries about "it".

calvin

Algorithm Design Manual

Всем программистам очень рекомендую книжку "Algorithm Design Manual" (Steve Skiena). В ней есть всё, что нужно знать об алгоритмах в обычной жизни - графы, бинарные деревья, анализ асимптотической сложности алгоритмов, динамическое программирование. Но там есть и намного больше - истории о том, как хорошо придуманный алгоритм решает реальные проблемы (War Stories) и целый справочник практических задач (Hitchhiker's Guide to Algorithms). И самое главное - книжка просто очень хорошо, интересно и увлекательно написана.

Нет, это не Кнут и даже не Кормэн. Там нет красно-черных деревьев, AVL, мастер-теорема не разобрана по всем ее математическим косточкам. Но поймите меня правильно. Я преклоняюсь перед людьми, которые прочитали Кнута и может быть даже получили от этого удовольствие, но, во-первых, где взять столько времени, а во-вторых, столько кофеина употреблять вредно. А классический учебник по алгоритмам Кормэна (CLRS) всем неплох, но скучен.

И напоследок смешное из книжки:
Об известной шахматной легенде:
The combinatorial explosion was first recognized with the legend that the inventor of chess demanded as payment one grain of rice for the first square of the board, and twice as much for the (i+1)st square than the ith square. The king was astonished to learn he had to cough up  36,893,488,147,419,103,231 grains of rice. In beheading the inventor, the wise king first established pruning as a technique for dealing with the combinatorial explosion.

О факториальной сложности алгоритмов:
For real circuit boards, where n≈1000, forget about it. All of the world’s computers working full time wouldn’t come close to finishing the problem before the end of the universe, at which point it presumably becomes moot.

Скиена демонстрирует студентам редукцию алгоритма к другому NP-complete алгоритму:
Now the back of the classroom was getting excited. They were starting to see a ray of hope that they would get to leave on time.