Алгоритмы - построение и анализ (1021735), страница 5
Текст из файла (страница 5)
Часто предлагаются реальные альтернативы алгоритмам, представляющим преимущественно теоретический интерес. Если вам понадобится реализовать любой из приведенных алгоритмов, будет достаточно легко преобразовать приведенный псевдокод в код на вашем любимом языке программирования. Псевдокод разработан таким образом, чтобы каждый алгоритм был представлен ясно и лаконично.
Вследствие этого не рассматриваются обработка ошибок и другие связанные с разработкой программного обеспечения вопросы, требующие определенных предположений, касающихся конкретной среды программирования. Авторы попытались представить каждый алгоритм просто и непосредственно, не используя индивидуальные особенности того или иного языка программирования, что могло бы усложнить понимание сути алгоритма.
Коллегам В книге приведена обширная библиография и представлены указания на современную литературу. В конце каждой главы даются "заключительные замечания", содержащие исторические подробности и ссылки. Однако эти замечания не могут служить исчерпывающим руководством в области алгоритмов. Возможно, в зто будет сложно поверить, но даже в такую объемную книгу не удалось включить многие интересные алгоритмы из-за недостатка места.
Несмотря на огромное количество писем от студентов с просьбами предоставить решения задач и упражнений, политика авторов — не приводить ссылки на Введение источники, из которых этн задачи и упражнения были позаимствованы. Это сделано для того, чтобы студенты не искали готовые решения в литературе, а решали задачи самостоятельно. Изменения во втором издании Какие изменения произошли во втором издании книги? В зависимости от точки зрения, можно сказать, что их достаточно мало или довольно много. Ббльшая часть глав первого издания содержится и во втором издании.
Авторы убрали две главы и некоторые разделы, но добавили три новые главы и (кроме них) четыре новых раздела. Если судить об изменениях по оглавлению, то, скорее всего, можно прийти к выводу, что их объем достаточно скромный. Однако зти изменения далеко выходят за рамки оглавления. Ниже без определенного порядка приводится обзор наиболее значительных изменений во втором издании. ° К коллективу соавторов присоединился Клифф Штайн (С111Т Бге1л). ° Были исправлены ошибки. Сколько их было допущено? Ну, скажем, несколько.
° Появились три новые главы: ° в главе 1 обсуждается роль алгоритмов в вычислениях; ° в главе 5 излагается вероятностный анализ и рандомизированные алгоритмы; в первом издании зта тема упоминается в разных местах книги; ° глава 29 посвящена линейному программированию. ° Что касается глав, которые присутствовали в первом издании, в них добавлены новые разделы по таким вопросам: ° идеальное хеширование (раздел 11.5); ° два приложения динамического программирования (разделы 15.1 и !5.5); ° алгоритмы аппроксимации, в которых применяется рандомизация и линейное программирование (раздел 35.4). ° Чтобы поместить в начальную часть книги больше алгоритмов, три главы по основным разделам математики перенесены из части 1 в приложение (часть ЧП1). ° Добавлено более 40 новых задач и 185 новых упражнений.
° В явном виде были использованы инварианты цикла для доказательства корректности алгоритмов. Первый инвариант цикла используется в главе 2, и в дальнейшем в книге они применяются еще несколько десятков раз. 34 Введение ° Переделаны многие места, где проводится вероятностный анализ.
В частности, более десяти раз используется метод "индикаторных случайных величин", упрощающих вероятностный анализ, особенно при наличии зависимости между случайными величинами. ° Дополнены и обновлены заключительные замечания к главам и библиография. Библиография увеличилась более чем на 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п), Сасмнте Сюр (Зияп!!а Зпг), Грегори Трокселу (Огейогу Тгохе!) и Маргарет Таттл (Магяаге! Тш!!е). Ценную техническую помощь оказали многие частные лица.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
