Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Благодарности. Многие читатели прислали мне исключительно полезные отзывы о предыдущих изда­ниях этой книги






Многие читатели прислали мне исключительно полезные отзывы о предыдущих изда­ниях этой книги. В частности, в течение ряда лет предварительные наброски книги ап­робировались на сотнях студентов в Принстоне и Брауне. Особую благодарность хотелось бы выразить Трине Авери и Тому Фримену за оказанную помощь в выпуске первого из­дания; Джанет Инсерпи за проявленные ею творческий подход и изобретательность, чтобы заставить аппаратные и программные средства нашей примитивной и давно устаревшей компьютеризированной издательской системы напечатать первое издание книги; Марку Брауну за его участие в исследованиях по визуализации алгоритмов, которые во многом способствовали появлению в книге многочисленных рисунков, а также Дэйву Хенсону и Эндрю Эппелю за их готовность ответить на мои вопросы, связанные с языками програм­мирования. Я хотел бы также поблагодарить многочисленных читателей, приславших от­зывы на различные издания этой книги, в том числе Гая Олмсу, Джона Бентли, Марка Брауна, Джея Гришера, Аллана Хейдона, Кеннеди Лемке, Юди Манбер, Дану Ричарде, Джона Рейфа, М. Роенфельда, Стивена Сейдмана, Майка Квина и Вильяма Варда.

При подготовке нового издания я имел удовольствие работать с Питером Гордоном, Дебби Лафферти и Хелен Гольштейн из издательства Addison-Wesley, которые терпели­во опекали этот проект с момента его зарождения. Большое удовольствие доставила мне совместная работа с другими штатными сотрудниками этого издательства. Характер про­екта сделал подготовку издания данной книги несколько непривычной задачей для мно­гих из них, и я высоко ценю проявленную ими снисходительность. В частности, Мэри-лин Рашш затратила немало усилий, чтобы втиснуть работу по изданию книги в жесткие временные рамки.


Предисловие



В процессе написания этой книги я приобрел трех новых наставников и хочу особо выразить им свою признательность. Во-первых, Стиву Саммиту, который внимательно проверил на техническом уровне первые варианты рукописи и предоставил буквально тысячи подробных комментариев, особенно в отношении программ. Стив хорошо пони­мал мое стремление снабдить книгу изящными и эффективные реализациями, и его ком­ментарии помогли мне не только обеспечить определенное единообразие реализаций, но и существенно улучшить многие из них. Во-вторых, я хочу поблагодарить Лин Дюпре за тысячи подробных комментариев в отношении рукописи, которые помогли автору не только избежать и исправить грамматические ошибки, но и (что значительно важнее) выработать последовательный и связный стиль написания, что позволило собрать воеди­но устрашающую массу технического материала. Я исключительно благодарен получен­ной возможности поучиться у Стива и Лин — их вклад в разработку этой книги оказался решающим. В третьих, Крис Ван Вик реализовал и отладил все разработанные мною ал­горитмы на C++, ответил на многочисленные вопросы, касающиеся C++, помог разра­ботать соответствующий стиль на C++ и дважды внимательно прочел рукопись. Крис тер­пеливо сносил все мои придирки к разработанным им программам на C++, не возмущался, когда я отвергал многие из них, но по мере того, как мои знания языка C++ росли, мне приходилось возвращать эти программы практически в том виде, в каком они были написаны Крисом. Я бесконечно благодарен возможности многому научиться у Сти­ва, Лин и Криса — они внесли решающий вклад в издание этой книги.

Многое из написанного здесь я узнал из лекций и трудов Дона Кнута - моего настав­ника в Стэнфорде. Хотя непосредственно Дон и не участвовал в написании этой книги, его влияние можно почувствовать на всем ее протяжении, ибо именно он поставил изу­чение алгоритмов на научную основу, благодаря чему вообще стало возможным появле­ние подобного рода книг. Мой друг и коллега Филлип Флажоле, благодаря которому ана­лиз алгоритмов стал вполне сформировавшейся областью исследований, оказал не меньшее влияние на этот труд.

Я глубоко признателен за оказанную мне поддержку Принстонскому университету, Брауновскому университету и Национальному институту исследований в области инфор­матики и автоматики, где была проделана большая часть работы над книгой, а также Ин­ституту исследований защиты и Исследовательскому центру компании Xerox в Пало-Аль-то, где была завершена немалая часть работы. В основу многих глав этой книги положены исследования, которые щедро финансировались Национальным научным фондом и От­делом военно-морских исследований. И в заключение, я благодарю Билла Боуэна, Ааро­на Лемоника и Нейла Руденштайна за то, что они способствовали созданию в Принсто-не академической обстановки, в которой я получил возможность подготовить эту книгу, несмотря на множество других возложенных на меня обязанностей.

Роберт Седжвик

Марли-де-Руа, Франция, февраль 1983 г.

Принстон, Нью-Джерси, январь 1990 г.

Джеймстаун, Род-Айленд, август 1997 г.



Часть 5. Алгоритмы на графах


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

Боб Сэджвик и я написали множество вариантов большей части программ, стремясь реализовать алгоритмы на графах в виде прозрачных и естественных программ. Посколь­ку существует великое разнообразие графов, порождающих множество касающихся их вопросов, мы согласились, что рано или поздно, но нам придется искать такую схему класса, которая будет работать на протяжении всей книги. Как ни странно, но эти по­иски закончились использованием только двух схем: простой схемы, применяемой в гла­вах 17-19, в которых ребра графа либо присутствуют, либо нет, и подхода, подобного контейнерам библиотеки STL (Standard Template Library — стандартная библиотека шаб­лонов) в главах 20-22, в которых с ребрами связана более обширная информация.

Классы C++ обладают существенными преимуществами для представления алгоритмов на графах. Мы используем классы для накопления полезных родовых функций на гра­фах (наподобие ввода/вывода). В главе 18 мы используем классы для выделения опера­ций, общих для нескольких различных методов поиска на графах. На протяжении всей книги мы применяем класс итератора к ребрам, исходящим из некоторой вершины, так что программы работают независимо от того, как хранится граф. Очень важно то, что мы упаковываем алгоритмы на графах в классы, конструктор которого осуществляют обра­ботку графа и функции-элементы которого предоставляют нам доступ к информации об обнаруженных свойствах. Такая организация позволяет алгоритмам на графах без труда применять другие алгоритмы на графах в виде подпрограмм, например, программу 19.13 (транзитивное замыкание на основе сильных компонент), программу 20.8 (алгоритм Крус­кала построения минимального остовного дерева), программу 21.4 (построение всех крат­чайших путей с использованием алгоритма Дейкстры), программу 21.6 (самый длинный путь в ориентированном ациклическом графе). Эта тенденция достигает наивысшей точ­ки в главе 22, большая часть программ которой построена на более высоком уровне аб­стракции с использованием классов, которые были определены в предыдущих частях дан­ной книги.

Дабы не входить в противоречие с материалом, изложенным в настоящей книге, наши программы используют разработанные в ней классы стеков и очередей, и мы применя­ем операции с явными указателями на односвязных списках в двухуровневых реализациях. Мы также принимаем два стилистических изменения из частей 1-4: конструкторы исполь­зуют инициализацию вместо присваивания, и мы используем векторы STL вместо масси­вов. Ниже мы приводим перечень всех функций на векторах STL, которые были задей­ствованы в наших программах:

■ Конструктор по умолчанию создает пустой вектор.

■ Конструктор vec(n) строит вектор из n элементов.

■ Конструктор vec(n, x) строит вектор из n элементов, каждый из которых инициа­
лизируется значением х.

■ Функция-элемент vec.assign(n, x) преобразует vec в вектор из n элементов, каждый
из которых инициализируется значением х.

■ Функция-элемент vec.resize(n) возрастает или убывает, получая пропускную способ­
ность n.


Предисловие



■ Функция-элемент vec.resize(n, x) увеличивает или уменьшает vec, получающий про­пускную способность n, и инициализирует любые новые элементы значением x.

STL также определяет оператор присваивания, конструктор копирования и деструк­тор, которые необходимы, чтобы сделать векторы объектами первого рода.

Прежде чем я приступил к работе над этими программами, я ознакомился с формаль­ными описаниями и псевдокодами множества этих алгоритмов, однако реализовал толь­ко некоторые из них. Разработка деталей, необходимая для преобразования алгоритмов в работающие программы, оказалась для меня весьма поучительной, и было очень инте­ресно наблюдать за тем, как они работают. Я надеюсь, что ознакомление с программа­ми, опубликованными в этой книге, и их выполнение поможет вам достичь большего по­нимания собственно алгоритмов.

Мои искренние благодарности я направляю Джону Бентли, Брайану Кернингану и Тому Шимански, от которых я узнал многое из того, что я сейчас знаю о программиро­вании; Дебби Лафферти, которая предложила мне принять участие этом проекте. Я так­же приношу свою благодарность университету города Дрю и Принстонскому универси­тету за безвозмездную поддержку.

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








© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.