Книга «Искусство программирования», том 4А, «Комбинаторные алгоритмы, часть 1», опубликована в издательстве Addison-Wesley Professional

Всемирно известный автор серии классических книг по программированию Дональд Кнут опубликовал первую часть четвертого тома своего знаменитого труда. Со времени выпуска первой редакции третьего тома прошло 38 лет.

Книга «Искусство программирования», том 4А, «Комбинаторные алгоритмы, часть 1», опубликована в издательстве Addison-Wesley Professional. В книге 912 страниц.

«'Искусство программирования' Дональда Кнута, без сомнений, сыграло определяющую роль в деле превращения информатики из развивающейся науки в разряд фундаментальных дисциплин», — отметил Узи Вишкин, профессор Института передовых компьютерных исследований Университета штата Мэриленд.

К делу написания своих научных трудов Кнут подходит крайне тщательно. Первый том «Искусства программирования» он опубликовал в 1965 году, а всего затем было запланировано подготовить семь томов. Том 3 был опубликован в 1973-м, и с тех пор автор одновременно занимался переработкой предыдущих книг и составлением четвертого тома. В 1990-м Кнут досрочно вышел на пенсию, чтобы полностью отдать себя своему главному проекту.

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

В предисловии к четвертому тому автор признается, что когда он составлял планы томов, он рассчитывал, что материала по комбинаторным алгоритмам ему хватит лишь на тоненькую книгу. Однако исследования в этой области впоследствии кардинально расширились. Чтобы включить в книгу хотя бы наиболее практичные результаты всех новых исследований, Кнут разбил том на несколько частей, и в первой, 4a, охватываются только базовые знания. Он рассчитывает опубликовать следующие разделы — 4b, 4c и так далее в последующие годы.

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

Мощные новые алгоритмы позволяют с легкостью решить с виду неразрешимые комбинаторные задачи, объясняет Кнут. «Важность и привлекательность искусства написания таких программ в том, что одна хорошая идея может сэкономить годы или даже века машинного времени», — пишет автор в черновом варианте введения к книге.

Предыдущие тома «Искусства программирования» достигли легендарного статуса во многом благодаря их полноте и трудности усвоения материала. В аннотации к одному из томов книги Билл Гейтс, в то время генеральный директор корпорации Microsoft, предложил всем, кто прочтет книгу целиком, сразу отправлять ему резюме. Поговаривают, что генеральный директор Apple Стив Джобс хвалится тем, что прочел все тома, однако сам Кнут, тоже по слухам, в этом сомневается.