Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[0]

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

Алгоритмы записаны с виде «псевдокода» и прокомментированы в тексте; мы старались сделать описание алгоритма понятным людям с минимальным программистским опытом. Книга содержит более 260 рисунков, поясняющих работу различных алгоритмов. Мы обращаем особое внимание на эффективность рассматриваемых алгоритмов и приводим оценки времени их работы.

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

Преподавателям:

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

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

Каждый раздел снабжён упражнениями (всего их более 900): каждая глава заканчивается задачами (всего более 120). Как правило, упражнения проверяют понимание изложенного материала (часть из них - устные вопросы, часть подходят для письменного домаш-


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

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

Студентам:

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

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

Что нужно знать, приступая к чтению? Мы рассчитываем, что вы

•имеете некоторый программистский опыт, и рекурсивные процедуры, массивы и списки вас не пугают;

•простые математические рассуждения (скажем, доказательства по индукции) вам также знакомы (кое-где понадобятся отдельные факты из курса математического анализа; в первой части больше ничего из математики не потребуется).

Программистам:

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

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

Наш псевдокод легко перевести на любой язык программирования, если это понадобится. Надо только иметь в виду, что мы не включаем в алгоритмы системно-зависимые фрагменты (обработку ошибок и т.п.), чтобы не затемнять сути дела.


Ошибки

Книга такого объёма не может не содержать ошибок. Если вы обнаружили ошибку в английском оригинале книги, или у вас есть предложения по её исправлению, мы будем рады узнать об этом. Мы будем особенно рады новым упражнениям и задачам (но, пожалуйста, присылайте их с решениями). Почтовый адрес:

Introduction to Algorithms MIT Labratory for Computer Science 545 Technology Square Cambridge, Massachusetts 02139

Можно также получить список известных опечаток и сообщить о найденных ошибках с помощью электронной почты; чтобы получить инструкции, пошлите по адресу algorithms@theory.lcs.mit.edu письмо, содержащее Subject: help в заголовке. Извините, что мы не можем лично ответить на все письма.

[При переводе были учтены все исправления, имевшиеся на момент издания перевода (декабрь 1997), кроме того, исправлено несколько обнаруженных при переводе опечаток, но, возможно, возникли новые (в чём виноват научный редактор книги, А. Шень). Поэтому, обнаружив ошибку в русском тексте, не посылайте её сразу авторам: может быть, она возникла при переводе! Сообщите о ней сначала переводчикам, по адресу algorOmccme. ru или по почте (Москва, 121002, Большой Власьевский пер., 11, Московский центр непрерывного математического образования, издательство).]

Благодарности

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

Лаборатория информатики Массачусетского технологического института (Massachusetts Institute of Technology, Laboratory for Computer Science) была идеальным местом для работы над книгой. Наши коллеги по теоретической группе этой лаборатории были особенно терпимы и любезно соглашались просматривать главы книги. Мы хотели бы особенно поблагодарить следующих из них: Baruch Awerbuch, Shah Goldwasser, Leo Guibas, Tom Leighton, Albert Meyer, David Shmoys, Eva Tardos. Компьютеры, на которых готовилась книга (трёх типов: Microvax, Apple Macintosh, Sun Sparc-station) поддерживали William Ang, Sally Bemus, Ray Hirschfeld и Mark Reinhold; они же перекомпилировали TX, когда наши файлы перестали помещаться в его стандартную версию. Компания Thinking Machines поддерживала Чарльза Лейзерсона в период его



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]