РЕЦЕНЗИИ
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: изд-во МЦНМО, 2000. - 960 с.
Зима - самое подходящее время для серьезного чтения. Предлагаемая вашему вниманию книга - перевод одного из наиболее популярных в США учебников “по алгоритмам” (в оригинале - Introduction to Algorithms). В нем излагаются методы построения быстрых алгоритмов и способы анализа их эффективности. Как указано в предисловии, авторы старались добиться его пригодности на разных “уровнях”: от начального знакомства с программированием и структурами данных до аспирантских курсов по эффективным алгоритмам. Материала здесь значительно больше, чем нужно для занятий в течение семестра, главы достаточно независимы, так что каждый читатель может выбрать свой маршрут при изучении материала.
Чтобы представить себе объем этой книги, вспомните большой том англо-русского словаря под редакцией Мюллера на 53 тысячи слов и прибавьте к его толщине еще сантиметра полтора... Вес ее составляет три с половиной килограмма, так что о перелистывании и просмотре “по дороге” не может быть и речи.
Впервые вышедшая в США в 1990 г., книга выдержала 15 переизданий и была переведена на многие языки. Создавалась она в знаменитом Массачусетском технологическом институте (MIT). Ее авторы - известные ученые. Одного из них хорошо должны знать те, кто хотя бы немного слышал о современной криптографии. Это Р. Ривест, которому принадлежит буква R в аббревиатуре RSA - названии всемирно известной криптосистемы с открытым ключом.
В первой, подготовительной части, состоящей из пяти глав, даны математические основы анализа алгоритмов. Здесь собраны разъяснения и примеры, обозначения и понятия, связанные с асимптотикой функций, с методами вычислений и оценки сумм (подробнее с ними можно ознакомиться по учебнику матанализа), с использованием рекуррентных соотношений. Там содержатся определения множеств, отношений, графов, деревьев, элементы комбинаторики и теории вероятностей. Значительную часть этого материала можно пропустить при первом чтении, а потом по мере надобности возвращаться к пропущенному.
Вторая часть озаглавлена “Сортировка и порядковые статистики”. Здесь сравнивается трудоемкость вычислений для методов сортировки вставками (Insertion-Sort), слиянием (Merge-Sort), с помощью кучи (Heapsort), “быстрой” сортировки (Quicksort), т. е. в случаях, когда для упорядочения используются только попарные сравнения объектов, но не их внутренняя структура. Далее показывается, как можно добиться значительного ускорения работы, если при выполнении вычислений допустимо привлекать знания о тех или иных особенностях обрабатываемой структуры данных.
Характерной чертой методики изложения этой части, как и книги в целом, следует считать ориентированность на оценку эффективности алгоритмов - практически все рассматриваемые методы сопровождаются такими оценками, соответствующие тексты программ почти в каждой строке комментируются: скольких и каких операций будет это стоить.
В третьей части (еще пять глав) рассмотрены структуры данных, используемые в программировании для хранения изменяющихся множеств: стеки, очереди, связанные списки, деревья, хэш-таблицы.
Следующая часть посвящена трем важным методам построения эффективных алгоритмов: динамическому программированию, так называемым жадным алгоритмам (greedy algorithms) и амортизационному анализу. Последний термин связан отнюдь не с бухгалтерским учетом, а относится к задачам по оценке суммарного времени выполнения последовательности операций с какой-либо структурой данных (например, стеком). Как правило, используется завышенная оценка: берется максимальная длительность одной операции и умножается на число операций в последовательности. Оказывается, после выполнения начальных операций последовательности зачастую появляется информация, позволяющая выполнить последующие вычисления более экономно.
Пятая часть книги (это еще три главы) содержит подробный анализ специальных структур данных, хранящих изменяющиеся множества (В-деревья, биномиальные и фибоначчиевы кучи и т. п.), и операций с ними. В шестой части рассматриваются структуры для представления графов и несколько основных алгоритмов обработки таких структур, а также основные задачи, формализуемые с помощью графов.
В завершающей части книги собраны темы, дополняющие в том или ином смысле предыдущие части. Таких дополнений чрезвычайно много: новые модели вычислений (схемы из функциональных элементов, параллельно работающие процессоры), вычисления с матрицами, многочлены и быстрое преобразование Фурье, теория чисел, разложение на множители и проверка чисел на простоту, шифрование с открытым ключом и электронная подпись, алгоритмы поиска подстрок, вычислительная геометрия. Две последние главы посвящены обсуждению фундаментальных факторов, важных при оценке принципиальной возможности решения той или иной вычислительной задачи за практически приемлемое время (NP-полнота).
Многие рассмотренные в книге алгоритмы в настоящее время доступны широкому кругу компьютерных пользователей через инструментальные панели и меню офисных пакетов и СУБД, например алгоритмы сортировки. Мы нажимаем на кнопки в офисных пакетах Word, Excel и MS Access, и элементы наших таблиц и списков послушно выстраиваются по возрастанию или по убыванию. Еще один алгоритм, ставший “кнопкой”, - это столь привычная пользователям текстовых редакторов операция по нахождению заданной подстроки в тексте. Другие примеры можно найти в САПРовских, графических, криптографических, статистических и иных системах. В подавляющем большинстве пользователи не подозревают о все новых и новых программистских ухищрениях, обеспечивающих предоставляемый сервис.
В классическом рассказе А. Азимова “Чувство силы” (“Сколько будет девятью семь”), написанном еще аж в 1959 г., подобная ситуация была предсказана в завершенно-утрированном виде. Рисуя картину будущего супертехнологичного общества, писатель рассказывает о скромном служащем вычислительного центра, который обнаруживает у себя атавистические способности: он может выполнять на бумаге столбиком арифметические операции: сложение, вычитание, умножение... Такие навыки давно утрачены человечеством ввиду полной и окончательной компьютеризации, поэтому окружающие долго не могут понять, что за каракули рисует этот то ли фокусник, то ли сумасшедший. И главное - зачем? Однако выясняется, что “новый” способ считать не так уж плох и способен дать выигрыш в надежности... Эта история вспомнилось мне во время чтения “Алгоритмов”. Имя автора и название рассказа я забыл, зато знал, что в тексте встречается слово “счетчик” и упоминается сложение столбиком. Чтобы найти этот рассказ теперь, мне пришлось несколько раз воспользоваться кнопкой “Найти” в поисковой машине Интернета Aport.
Завершается книга обширной (в разумных пределах) библиографией, дополненной ссылками на отечественные работы, а также подробными предметным и именным указателями, которые пригодятся тем, кто пожелает лишь вспомнить (или даже впервые прочесть) забытое определение или схему алгоритма.
На последних страницах дается справка о выпущенных и планируемых к выпуску книгах издательства МЦНМО (Московского центра непрерывного математического образования), есть ссылки на Интернет-адреса, по которым отдельные книги доступны для свободного скачивания. Например, это касается известной книги А. Шеня “Программирование: теоремы и задачи” (МЦНМО, 1995. - 264 с.). Указан адрес сервера “Математического библиоклуба” при издательстве (mbc.mccme.ru), а также сообщается о существовании специализированного математического книжного магазина в Б. Власьевском пер., 11, (телефон: (095) 241-7285, E-mail: mbc@ mccme.ru). Именно там можно купить “Алгоритмы”. Добравшись до указанного переулка в канун Нового года, я приобрел еще несколько книг, которые вряд ли появятся в широкой продаже. Упомяну только одну, близкую по теме: “Особенности национальных задач по информатике” (Киров, 2000. - 160 с.). Ее авторы, тренеры сборной России и члены научного комитета Всероссийской олимпиады по информатике, приводят много интересных формулировок и методик решения олимпиадных задач. Начинается эта книга с фразы: “Российская система образования в области точных наук по праву считается одной из лучших в мире...”.
Что касается особенностей “Алгоритмов”, то они в следующем: хотя начальные и последующие главы не требуют фундаментальной математической подготовки, легким это чтением не назовешь. Не все элементарное - просто. В то же время чрезвычайно высока добротность изложения. Внимательное последовательное изучение материала и разбор предлагаемых примеров, которые очень хорошо иллюстрированы, позволяют неуклонно продвигаться вперед в понимании предмета. Авторы нигде резко не поднимают планку, требуя от читателя что-то самостоятельно домыслить и сообразить, не сообщая, как это сделать (такими “примерами” изобилуют многие наши учебники). И начинаешь догадываться, как же это из “малообразованных” американских школьников, о вопиющей безграмотности которых так много говорилось у нас при сравнении отечественной системы образования с западными, получаются, причем в достаточном количестве, очень эрудированные математики, физики, химики, инженеры, врачи и т. д. Пожалуй, это и выделяет обсуждаемую книгу из ряда других на ту же тему, уже изданных у нас.
