Предисловие консультанта по С++

Именно алгоритмы вовлекли меня в компьютерные науки. Изучение алгоритмов требует сочетания нескольких подходов: творческого - для выработки идеи решения задачи; логического - для анализа правильности решения; математического - для анализа производительности; и скрупулезного - для выражения идеи в виде подробной последовательности шагов, чтобы она могла превратиться в программу. Поскольку наибольшее удовлетворение при изучении алгоритмов мне доставляет их реализация в виде работающих компьютерных программ, я с радостью ухватился за возможность поработать с Бобом Седжвиком над книгой по алгоритмам, основанной на программах С++.

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

Однако, мы не воспользовались возможностью продемонстрировать множество других технологий С++. Например, обычно мы опускаем, по крайней мере, некоторые конструкторы, необходимые, чтобы любой класс был первым классом ; в большинстве конструкторов для хранения значений в членах данных используется присваивание, а не инициализация; вместо строк из библиотеки С++ мы использовали символьные строки в стиле С; мы не использовали большинство возможных упрощенных классов контейнеров; и, наконец, мы использовали простые, а не интеллектуальные указатели.

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

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

Я благодарю Джона Бентли (Jon Bentley), Брайана Кернигана (Brian Kernighan) и Тома Шимански (Тот Szymanski), от которых узнал многое о программировании; Дебби Лафферти (Debbie Lafferty), которая предложила мне принять участие в этом проекте; а также фирму Bell Labs, университету Дрю и Принстонскому университету за оказанную ими безвозмездную поддержку.

Кристофер Ван Вик Чатем, Нью-Джерси, 1998 г.

Примечания к упражнениям

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

Упражнения, которые проверяют понимание материала, помечены незаполненным треугольником:

> 9.54. Вычертить биномиальную очередь размера 29, воспользовавшись представлением в виде биномиального дерева.

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

Упражнения, которые дополняют текст новой и требующей размышлений информацией, помечены иезаполненной окружностью:

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

Такие упражнения заставляют подумать о важных концепциях, связанных с материалом, изложенным в тексте, или ответить на вопрос, который может возникнуть во время прочтения. Возможно, читатели сочтут полезным прочесть эти упражнения даже при отсутствии времени для их выполнения.

Упражнения, которые имеют целью поставить перед читателями задачу, помечены черной точкой:

9.63. Реализовать операцию вставить (insert) для биномиальных очередей путем явного использованием одной лишь операции объединить (join).

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

Несколько упражнений, которые особенно трудны (по сравнению с большинством других) помечены двумя черными точками:

9.64. Реализовать операцию изменить приоритет (change priority) и удалить (remove) для биномиальных очередей. Совет: Потребуется добавить третью связь, которая указывает на узлы вверх по дереву.

Эти упражнения аналогичны вопросам, которые могут ставиться в научной литературе, однако материал книги может так подготовить читателей, что им доставит удовольствие попытаться ответить на них (возможно, и преуспеть в этом).

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

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

1.22 Измените программу 1.4, чтобы она генерировала случайные пары целых чисел в диапазоне от О до TV- 1 вместо того, чтобы считывать их из стандартного ввода, и выполняла цикл до тех пор, пока не будет выполнено N- 1 операций union. Выполните программу для значений N ~ 10 , Ю *, 10 и 10 и выведите общее количество ребер, генерируемых для каждого значения N.

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

1.12 Вычислите среднее расстояние от узла до корня в худшем случае в дереве, построенном алгоритмом взвешенного быстрого объединения из 2 узлов.

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