Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 3
Текст из файла (страница 3)
Одна из ключевых идей главы, посвященной сортирующим сетям, а именно 0-1 принцип, в этом издании находится в задаче 8.7 в виде леммы 0-1 сортировки для алгоритмов, работающих путем сравнения и обмена. Рассмотрение пирамид Фибоначчи больше не Предисловие основывается на биномиальных пирамидах как на предшественницах пирамид Фибоначчи.
Мы пересмотрели подход к динамическому программированию и жадным алгоритмам. Динамическое программирование теперь иллюстрируется более интересной задачей разрезания стержня, чем задача сборочного конвейера во втором издании. Кроме того, мы сделали больший, чем во втором издании, акцент на технологии запоминания и ввели понятие графа подзадачи как способа улучшения определения времени работы алгоритма динамического программирования. В нашем вводном примере для жадных алгоритмов — в задаче о выборе процессов — мы переходим к жадным алгоритмам более прямым путем, чем во втором издании. Способ удаления узла из бинарных деревьев поиска (включающих красно-черные деревья) теперь гарантирует, что будет удален именно тот узел, который нужно удалить.
В двух первых изданиях в некоторых случаях удалялся некоторый другой узел с перемещением его содержимого в узел, переданный процедуре удаления. При таком, новом, способе удаления узлов в случае, когда другие компоненты программы поддерживают указатели на узлы дерева, они не окажутся в ситуации с устаревшими указателями на удаленные из дерева узлы. В материале, посвященном транспортным сетям, потоки теперь полностью базируются на ребрах, что представляет более интуитивно понятный подход, чем в первых двух изданиях.
Поскольку материал об основах работы с матрицами и алгоритм Штрассена перенесены в другие главы, глава, посвященная матричным операциям, стала существенно меньше по сравнению со вторым изданием. Изменено рассмотрение алгоритма сравнения строк Кнута-Морриса-Пратта. Исправлен ряд ошибок. Информация о большинстве из них (но не обо всех) была получена нами через наш сайт, посвященный второму изданию книги. Идя навстречу многочисленным пожеланиям, мы заменили синтаксис нашего псевдокода. Теперь для указания присвоения мы используем "=", а для проверки на равенство — "==", как зто делается в С, С-н-, вача и Рушев.
Точно так же мы удалили ключевые слова Йо и Гпеп и приняли в качестве символов начала комментария до окончания строки "//". Кроме того, для указания атрибутов обьектов используется запись с точкой. Но мы не зашли настолько далеко, чтобы сделать псевдокод объектно-ориентированным; он остался процедурным. Другими словами, вместо выполнения методов объектов мы просто вызываем процедуры, передавая им объекты в качестве параметров. Мы добавили 100 новых упражнений и 28 новых задач.
Мы также обновили и расширили библиографию. Наконец мы прошлись по всей книге и переписали многие разделы, абзацы и отдельные предложения, делая изложение более понятным. !9 !уреднсл окне Веб-сайт Вы можете воспользоваться нашим веб-сайтом по адресу Ьсср: // лтйсргеаа.пгйс.ес1ц/а1догйспуав/ для получения дополнительных материалов и для обратной связи с авторами. На сайте имеются ссылки на список известных ошибок, на решения избранных упражнений и задач и многие другие дополнительные материалы. Веб-сайт также позволяет читателю сообщить о замеченных ошибках или внести свои предложения по поводу книги.
Как создавалась зта книга Третье издание книги, как и второе, выполнено в )дТБХ 2е. Для математических формул мы использовали шрифт Тппеб вместе со шрифтами МагЬТппе Рго 2. Мы выражаем признательность за техническую поддержку Майклу Спиваку (М!сЬае! Бр!уа1с) из РцЬПбЬ ог РепзЬ, 1лс., Лансу Кариесу (1.апсе Сагпеб) из Регбопа1 ТеХ, 1пс., и Тиму Трегубову (Тпп ТгейпЬоу) из ОаггпюцгЬ Сойейе. Как и в двух предыдущих изданиях, предметный указатель компилировался с помощью %!пг)ех, написанной нами программы на языке С, а библиография — с применением В!вТВХ.
РТУР-файлы этой книги созданы на МасВоок под управлением ОБ !0.5. Иллюстрации к третьему изданию созданы с использованием МасПгачо Рго с соответствующими пакетами для кьТБХ2е для вставки в иллюстрации математических формул. К сожалению, МасРгачг Рго — устаревшее программное обеспечение, не выпускающееся уже более десятилетия.
Но к счастью, у нас все еще есть пара "Макинтошей", на которых можно запускать классическую среду под управлением ОБ 10.4, а следовательно, как правило, и Мас1угатн Рго. Но даже с этими сложностями мы пришли к выводу, что Мас0гамг Рго гораздо проще любого другого программного обеспечения для создания иллюстраций, сопровождающих текст на компьютерную тематику, и позволяет получить отличные результаты.' Кто знает, сколько еще протянут наши доинтеловские Маки, так что если кто-то из Арр!е читает эти строки, то услышьте нашу просьбу: пожалуйста, создайте Оо Х-соаиестидгую версию Мас0газр Рго/ Благодарности к третьему изданию К настоящему времени мы сотрудничаем с М!Т Ргеай уже более двух десятилетий, и это были очень плодотворные десятилетия! Мы благодарны Эллен Фаран (Ейеп Рагап), Бобу Приору (ВоЬ Рпог), Аде Брунштейн (Ада Впгпбзе!и) и Мэри Рейли (Магу Кей!у) за помощь и поддержку.
При написании третьего издания мы были сильно разбросаны географически„работая в Пагппоцгй Сойейе Оерапшепг ог" Сошрпгег Яс!енсе, М1Т Сошрпгег Мы изучили несколью различных программ, рабогаююих под управлением Мас Об Х. но все оии обладают значительными недостатками по сравнению с Маспгаи Ргш Мы пробовали создашть иллюстрации лля этой книги с помошью других, хорошо известных программ, но получалось, что в результате мы тратили как минимум в пять рю больше времени, чем для создания тех же иллюстраций в Маспгаэт Рго, причем результат оставлял желать лучшего.
Так что нам пришлось скрепя сердце принять решение вернуться к Маспгам Рго на старых "Макинтошам". Предитовие 20 Ливан, Нью-Гемпшир Кембридж, Массачусеттс Кэмбридж, Массачусеттс Нью-Йорк, Нью-йорк ТОМАС КОРМЕН ЧАРЛЬЗ ЛЕЙЗЕРСОН РОнАльД РиВест КЛИФФОРД ШТАЙН Февраль 2009 Бс)епсе апс( Ап!Пс(а! 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}
