Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 5
Текст из файла (страница 5)
° Дополнены и обновлены заключительные замечания к главам и библиография. Библиография увеличилась более чем на 50;4. Кроме того, упоминаются многие новые результаты, которые были достигнуты в теории алгоритмов после выхода первого издания. Также внесены перечисленные ниже изменения.
° В главе, посвященной решению рекуррентных соотношений, больше не содержится информация об итеративном методе. Вместо этого в разделе 4.2 на первый план выступают деревья рекурсии, сами по себе представляющие определенный метод. Авторы пришли к выводу, что использование деревьев рекурсии в меньшей мере связано с риском допустить ошибку. Однако следует заметить, что деревья лучше всего использовать для генерации предположений, которые затем проверяются методом подстановок.
° Несколько по-иному излагается метод разбиения, который применялся для быстрой сортировки (раздел 7.1), и алгоритм порядковой статистики, математическое ожидание времени работы которого выражается линейной функцией (раздел 9.2). В данном издании используется метод, разработанный Ломуто (1ошшо), который наряду с индикаторными случайными величинами позволяет несколько упростить анализ. Предложенный Хоаром (Ноаге) метод, который содержался в первом издании, включен в качестве задачи в главе 7. ° Внесены модификации в обсуждение универсального хеширования в разделе 11.3.3, после чего оно интегрируется в представление идеального хеширования.
° Значительно упрощен анализ высоты бинарного дерева поиска, построенного в разделе 12.4 случайным образом. ° Существенно расширено обсуждение элементов динамического программирования (раздел 15.3) и жадных алгоритмов (раздел 16.2). Исследование задачи о выборе задания, которым начинается глава о жадных алгоритмах, помогает прояснить взаимосвязь между динамическим программированием и жадными алгоритмами.
° Доказательство времени работы для объединения непересекающихся множеств заменено в разделе 21.4 доказательством, в котором точные границы определяются с помощью метода потенциалов. ° Значительно упрощено доказательство корректности алгоритма из раздела 22.5, предназначенного для сильно связных компонентов. Введение 35 ° Реорганизована глава 24, посвященная задаче о кратчайших путях из одной вершины: доказательства существенных свойств в ней вынесены в отдельный раздел.
° В разделе 34.5 расширен обзор ЫР-полноты, приводятся новые доказательства ЫР-полноты задачи поиска гамильтонова цикла и задачи о сумме подмножества. Наконец, почти каждый раздел подредактирован, в результате чего в них внесены исправления, упрощения, а также даны более четкие объяснения и доказательства.
ЖеЬ-узел Еще одно изменение по сравнению с первым изданием данной книги заключается в том, что теперь книга имеет свой ччеЬ узел: !тсср: //тзсргезз.жзс. еои/а1догз~1лаа/. С помощью этого %еЬ-узла можно сообщить об ошибках, получить список известных ошибок нли внести предложения; авторы будут рады узнать мнение читателей. Особенно приветствуются идеи по поводу новых задач и упражнений, однако их следует предлагать вместе с решениями. Авторы выражают сожаление, что не могут лично ответить на все замечания. Благодарности к первому изданию Большой вклад в эту книгу внесли многие друзья и коллеги, что способствовало повышению ее качества. Выражаем всем благодарность за помощь и конструктивные замечания.
Лаборатория вычислительной техники Массачуссетского технологического института предоставила идеальные рабочие условия. Особенно большую поддержку оказали наши коллеги из группы Теории вычислений, входящей в состав лаборатории. Особую благодарность мы выражаем Баруху Авербаху (ВагпсЬ А~чегЬисЬ), Шафи Гольдвассеру (БЬаб Оо!биаззег), Лео Гибасу (1.ео Оп1Ьаз), Тому Лайтону (Тош Ье1БЬгоп), Альберту Мейеру (А1Ьеп Меуег), Дэвиду Шмойсу (ПачЫ БЬшоуз) и Эве Тардош (Еча Тапка). Благодарим Вильяма Энга (М111аш Апя), Салли Бемус (Ба!!у Вешпз), Рея Хиршфелда (Кау Н1гзсМе!6) и Марка Рейнгольда (Маг1с КешЬо16) за поддержку в рабочем состоянии наших машин (13ЕС М1сгочахез, Арр!е Мас(п!озЬез и Бип Брагсз!айопз), а также за перекомпилирование текста в формате ТЕХ каждый раз, когда мы превышали наш лимит времени, выделенного на компиляцию.
Компания МасЫпез Согрогайоп предоставила частичную поддержку Чарльзу Лейзерсону (СЬаг!ез Ье1зегзоп), позволившую ему работать над этой книгой во время отпуска в Массачуссетском технологическом институте. Многие наши коллеги опробовали черновые варианты этого учебника, читая по ним курсы лекций на других факультетах. Они предложили многочисленные Зб Введение исправления и изменения.
Особую благодарность хотелось бы выразить Ричарду Биглю (ВХсЬап! Ве!яе1), Эндрю Гольдбергу (Аш(ген ОоЫЬегя), Джоан Лукас (Хоап Хлсаз), Марку Овермарсу (Маг1с Очеппагз), Алану Шерману (А!ап БЬеппап) и Дайан Сувейн (О!апе Зоича!пе). Многие ассистенты преподавателей, читающих курсы лекций по учебнику, внесли значительный вклад в разработку материала. Особенно авторы благодарны Алану Баратцу (А1ап Вага(г), Бонни Бергер (Вопше Вегяег), Эдити Дагат (Ас !и' ХХЬаяас), Берту Калиски (Вшт Ка!!зЫ), Артуру Ленту (Аг!Ьиг Х.еп!)„Эндрю Моултону (Апс$гев Моийоп), Мариосу Папаефсимиу (Майоз РараейЬуппои), Синди Филлипс (С(пду РХВ!!1рз), Марку Рейнгольду (Маг!с Ве1пЬо!д), Филу Рогевей (РЫ! Кояаюау), Флавио Роузу (Р!ачю Козе), Эйри Рудичу (Айе Киб1сЬ), Алану Шерману (А!ап ЯЬеппап), Клиффу Штайну (С!!ХТ Яге1п), Сасмнте Сюр (Зияп!!а Зпг), Грегори Трокселу (Огейогу Тгохе!) и Маргарет Таттл (Магяаге! Тш!!е).
Ценную техническую помощь оказали многие частные лица. Дениз Серджент (Оешзе Бегяепг) провела много часов в лабораториях Массачуссетского технологического института, исследуя библиографические ссылки. Мария Синсейл (Мапа Зепза1е), библиотекарь из нашего читального зала, была всегда приветливой и готовой оказать помощь. Много времени, отведенного для работы над литературой при подготовке заключительных замечаний к главам, удалось сэкономить благодаря предоставлению доступа к личной библиотеке Альберта Мейера (А)Ьеп Меуег). Шломо Кипнис (БЫошо К!рп!з), Билл Нихаус (В(й ЬХ!еЬапз) и Дэвид Вилсон (Х)ачЫ %!!зол) откорректировали старые упражнения, разработали новые и написали примечания к их решениям.
Мариос Папаефсимиу (Майоз РараейЬугп1ои) и Грегори Троксель (Огеяогу Тгохе!) внесли вклад в составление предметного указателя. Неоценимую поддержку этого проекта в течение многих лет оказывали наши секретари Инна Радзиховски (1ппа Када!Ьочз1су), Дениз Серджент (Х)ел1зе Яегйеп!), Гейли Шерман (Оау!е ЗЬеппап) и особенно Би Блекбурн (Ве В!ас1сЬшп), за что авторы им благодарны. Многие ошибки в ранних черновых вариантах книги были обнаружены студентами. Особую благодарность за внимательное прочтение мы хотели бы выразить Бобби Блюмоуфу (ВоЬЬу В1шпо(е), Бонни Эйзенберг (Вопп!е ЕВепЬегд), Раймонду Джонсону (Каушолс1 ХоЬпзоп), Джону Кину (ХоЬп Кеел), Ричарду Летину (К!сЬагд Ее!(йп), Марку Лиллибриджу (Магас 1!!11ЬгЫяе), Джону Пезарису (ХоЬп Регайз), Стиву Понзио (81ече Ропг1о) и Маргарет Таттл (Магяагег Тш!1е). Авторы благодарны коллегам, прорецензировавшим отдельные главы или предоставившим информацию по отдельным алгоритмам.
Особая благодарность выражается Биллу Айелло (В!11 А!е!!о), Алоку Аггарвалю (А1о1с Аяйагва1), Эрику Баху (ЕПс ВасЬ), Вашеку Чваталу (Чазек СЬчага!), Ричарду Коулу (К!сЬап1 Со1е), Джоан Хастад (ХоЬап Назгад), Алексу Исии (А!ех ХзЬ!!), Дэвиду Джонсону (РачкЫ ХоЬпзоп), Джо Килиану (Хое К(йап), Дайне Кравец (ГЛла Кгакесз), Брюсу Маггсу (Вгпсе Маяка), Джиму Орлину (Хпп Ог1ш), Джеймсу Парку (Хашез Раг1с), Тейну Введение Пламбеку (ТЬапе Р!апзЬес1с), Гершелю Сейферу (Негьйе) Запрег), Джеффу Шаллиту (зей' ЗЬа1!Ь), Клиффу Штайну (СИТ Зсе!и), Гилу Стренгу (бй! Зсгапя), Бобу Таржану (ВоЬ Тат!ап) и Паулю Вонгу (Рац! %аль). Несколько наших коллег также любезно предоставили нам задачи; особенно мы благодарны Эндрю Гольдбергу (Албгечч ОоЫЬегя), Дэнни Слитору (Раппу З!еасог) и Умешу Вазирани (ПтезЬ 'Чах1гап1). При написании учебника авторам было приятно работать с издательствами ТЬе М1Т Ргеаа и Мсбгав-Н!11. Особую благодарность за моральную поддержку, помощь и терпение они выражают сотрудникам издательства ТЬе М1Т Ргеьз Фрэнку Сэтлоу (Ргап1с За!!о~ч), Терри Элингу (Тепу ЕЫшй), Лари Кохену (Еапу СоЬеп) и Лори Лиджииу (1.оп1е 1.е)еипе), а также Дэвиду Шапиро (РачЫ ЗЬар1го) из издательства Мсбгав-Н!1.
Наша особая благодарность — Лари Кохену (1.апу СоЬеп) за выдающуюся работу по корректированию. Благодарности ко второму изданию Когда мы предложили Джули Сассман (Ы1!е Зизяпап, Р.Р.А.) быть техническим редактором второго издания, то даже не представляли себе, насколько удачный договор заключаем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
