Хорошо известно, что при написании сколько-нибудь содержательного программного текста непременно приходится иметь дело с алгоритмом — семантическим остовом этого текста.
Вообще говоря, алгоритмы — предмет интересов математиков, но с развитием программирования появился широкий круг задач, находящихся в постоянном поле зрения программистов. Взять, например, сортировку данных — программист непременно столкнется с необходимостью выбора того или иного приемлемого алгоритма, поэтому необходимо владеть если не искусством, то навыками, анализа алгоритмов. Таким образом, появление новой книги, посвященной анализу алгоритмов, вызовет интерес у широкого круга читателей.
Издательство «РИЦ «Техносфера» в серии «Мир программирования» выпустило перевод книги Джеффри Макконнелла, которая основана на использовании «активного обучающего подхода» к предмету. Этот подход предполагает, что читатель должен познакомиться не только с основами анализа алгоритмов, включая понимание его сущности, необходимыми математическими сведениями, с зависимостью времени счета от объема данных и вообще со сложностью алгоритмов и основами алгоритмического анализа программ, но и собственно с различными алгоритмами.
Основная часть книги и вводит читателя в круг наиболее интересных и часто используемых в практике программирования алгоритмов. Начало этого пути автор видит в изучении алгоритмов поиска и выборки, предлагая для этого рассмотреть последовательный и двоичный поиск и механизм выборки, давая оценку его сложности. Обучение анализу алгоритмов сортировки Макконнелл проводит на восьми различных примерах. Численные алгоритмы, для которых проводится анализ, связаны с линейной алгеброй (вычислением значений многочленов, умножением матриц и решением систем линейных уравнений). Другие полезные алгоритмы, рассмотренные в книге, относятся к так называемым сравнениям с образцами, в качестве которых часто выступают строки записей, и к графам, когда приходится анализировать их характеристики. Пожалуй, наиболее интересными в книге являются последние три главы, где анализ сосредоточен на параллельных, недетерминированных алгоритмах, а также на других инструментах.
При анализе параллельных алгоритмов автор исходит из задачи повышения производительности и стоимости. Повышение оценивается коэффициентом ускорения над оптимальным последовательным алгоритмом, а стоимость, как произведение его сложности на число используемых процессоров. Модели параллельных алгоритмов, рассматриваемые в книге, относятся к одной из четырех систем, когда машина, на которой реализуется алгоритм, обладает прямым доступом к любой заранее заданной ячейке памяти — так называемая PRAM-машина. Читатель познакомится с анализом простых параллельных операций, параллельным поиском, сортировками, а также численными алгоритмами и различными алгоритмами на графах.
Книга содержит также материал по задачам, для которых алгоритмы имеют сложность более высокую, чем полиномиальная. При этом основное внимание уделяется поиску приближенных решений для таких задач NP-сложности (недетерминированная полиномиальная сложность). Полезность этой главы для читателя заключается главным образом в знакомстве с классом NP-задач и приобретении навыков установления принадлежности к этому классу практически интересных задач, а также способов анализа алгоритмов.
Весьма интересной для читателя может быть последняя глава об алгоритмических инструментах для NP-задач, не имеющих (возможно пока) для своего решения алгоритмов полиномиальной сложности. Среди альтернативных возможностей автор относит в первую очередь вероятностные алгоритмы, алгоритмы динамического программирования, а также так называемые жадные алгоритмы.
Методически книга построена удобным образом для читателей с разной программистской подготовкой — в нее включены упражнения, касающиеся как работы по усвоению теоретических положений, так по конкретным приемам программирования. Каждая глава снабжена сведениями по необходимым предварительным знаниям, целевыми установками и советами по изучению материала. В приложениях к книге имеется таблица случайных чисел и приведены три практически полезных способа генерации псевдослучайных чисел. Список литературы соотнесен к главам и весьма представителен, однако, для отечественного читателя было бы полезно его дополнить ссылками на актуальные русскоязычные источники.
Дж. Макконнелл, Анализ алгоритмов. М.: «Техносфера», 2002. - 304 с.
Минобраз рекомендовал Superdome
В Московском государственном университете состоялась презентация книги В. В. Воеводина и В. Вл. Воеводина «Параллельные вычисления». Это первая монография в области параллельных вычислений, рекомендованная Министерством образования РФ в качестве учебного пособия для обучения дисциплине «Прикладная математика и информатика». Книга издана при поддержке компании Hewlett-Packard и посвящена обсуждению ключевых проблем современных параллельных вычислений. В ней с единых позиций рассматриваются архитектуры параллельных вычислительных систем, технологии параллельного программирования, численные методы решения задач. Наряду со строгим описанием новых положений теории информационной структуры программ и алгоритмов, книга содержит богатый справочный материал, необходимый для организации эффективного решения больших задач на компьютерах с параллельной архитектурой. Параллельные компьютеры с общей памятью в монографии рассматриваются на примере серверов НР Superdome, которым отведен подраздел «Параллельные компьютеры с общей памятью. Детальное рассмотрение компьютера HP Superdome. Ячейка компьютера. Локальные и удаленные ячейки. Процессор РА-8700. Работа с памятью». Книга издана издательством «БХВ-Петербург» при поддержке Hewlett-Packard тиражом 3 тыс. экземпляров.
