Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 7
Текст из файла (страница 7)
Авторы хотели бы учесть все внесенные предложения. Единственная проблема заключается в том, что если бы это было сделано, объем второго издания мог бы превысить 3000 страниц! Второе издание готовилось к публикации в ЬТЕХ2я. Майкл Дауне (М!сЬае1 Росчпея) преобразовал ЬТЕХ-сценарии из "классической" версии ЬТЕХ в ЬТЕХ 2я и изменил текстовые файлы таким образом, чтобы в них использовались эти сценарии. Помощь в составлении текста в формате ЬТЕХ также оказал Дэвид Джонс (!)ачЫ )опея). Рисунки ко второму изданию созданы авторами в программе Мас).згасч Рго.
Как и в первом издании, предметный указатель составлен с помощью %!пс!ех, — программы на С, написанной авторами, а библиография подготовлена с помощью ВсвТЕХ. Айоркор Миллз-Титти (Ауог1сог М!11я-Тепеу) и Роб Лизерн 41 Введение (КоЫ.еа!Ьегп) помогли преобразовать рисунки в Мас()гачг Рго, а Айоркор также проверил библиографию. Как и во время работы над первым изданием, сотрудничество с издательствами М1Т Ргезз и Мсбгачч-Н!!! принесло авторам большое удовольствие. Редакторы Боб Прайор (ВоЬ Ргюг) из М1Т Ргеья и Бетси Джонс (Вегзу Успев) были терпеливы к нашим причудам и помогли преодолеть все препятствия.
Наконец, мы выражаем благодарность нашим женам Николь Кормен (Ы!со!е Соппеп), Гейл Ривест (ба!1 К!чез!) и Ребекке Иври (КеЬесса 1чгу), нашим детям Рикки (К!с!су), Вильяму (%!!!1аш) и Дебби Лейзерсон (РеЬЬу 1.е1зегзоп), Алексу (А!ех) и Кристоферу Ривест (СЬПз!орЬег К!чез!), а также Молли (Мо!1у), Ноа (ХоаЬ) и Беилжамену Штайн (Веп!аш!и Зге!и), нашим родителям Рени (Кепее) и Перри (Репу) Корменам, Джин (1еап) и Марку (Маг!с) Лейзерсон, Ширли (БЬ!г!еу) и Ллойду (1.!суси) Ривестам, а также Ирен (1гепе) и Ире Штайн (1га 8!е1п) за любовь и поддержку во время написания этой книги. Этот проект стал возможным благодаря поддержке и поощрению членов наших семей.
С любовью посвящаем им эту книгу. Томас Когмнн (Тномлз Н. Сокмнч), Ганновер, Нью-Гемпшир ЧАрльз Ляйзв'сон (Снлкг.нз Е. 1.нзнион), Кембридж, Массачуссетс Рон~льд Рнвнст (Конд!.о Ь. К!чвзт), Кембридж, Массачуссегс КЛИФФОРД ШтАЙн (Сыггоко Бтепч), Ганновер, Нью-Гемпшир От издательства Вы, читатель этой книги, и есть главный ее критик и комментатор. Мы ценим ваше мнение и хотим знать, что было сделано нами правильно, что можно было сделать лучше и что еще вы хотели бы увидеть изданным нами.
Нам интересно услышать и любые другие замечания, которые вам хотелось бы высказать в наш адрес. Мы ждем ваших комментариев и надеемся на них. Вы можете прислать нам бумажное нли электронное письмо, либо просто посетить наш %еЬ-сервер и оставить свои замечания там. Одним словом, любым удобным для вас способом дайте нам знать, нравится или нет вам эта книга, а также выскажите свое мнение о том, как сделать наши книги более интересными для вас. Посылая письмо или сообщение, не забудьте указать название книги и ее авторов, а также ваш обратный адрес. Мы внимательно ознакомимся с вашим мнением и обязательно учтем его при отборе и подготовке к изданию последующих книг. Наши координаты: Е-ша11: зпйойиз11хатэрпЬ1зэпзпд.сот %%%: Ьсср: //иии ° нз11зайэрп1э1зэЬ1пя .
сом Информация для писем из России: 115419, Москва, а/я 783 из Украины: 03150, Киев, а/я 152 Введение Эта часть книги заставит вас задуматься о вопросах, связанных с разработкой и анализом алгоритмов. Она была запланирована как вводный курс, в котором рассматриваются способы определения алгоритмов, некоторые стратегии их разработки, использующиеся в этой книге, а также применяемые при анализе алгоритмов различные основополагающие идеи. Кратко рассмотрим содержание глав первой части.
В главе 1 рассматривается понятие алгоритма и его роль в современных вычислительных системах. В ней приводится определение алгоритма и даются некоторые примеры. Здесь также обосновывается положение о том, что алгоритмы — это такой же технологический продукт, как, например, аппаратное обеспечение, графические интерфейсы пользователя, объектно-ориентированные системы или сети. В главе 2 читатель получит возможность ознакомиться с алгоритмами, с помошью которых решается задача о сортировке последовательности из п чисел.
Эти алгоритмы сформулированы в виде псевдокода. Несмотря на то, что используемый псевдокод напрямую не преобразуется ни в один из общепринятых языков программирования, он вполне адекватно передает структуру алгоритма, поэтому достаточно компетентный программист легко сможет реализовать его на любом языке программирования. Для изучения выбраны алгоритм сортировки вставкой, в котором используется инкрементный подход, и алгоритм сортировки слиянием, который характеризуется применением рекурсивного метода, известного также как метод "разделяй и властвуй" (метод разбиения).
В обоих алгоритмах время выполнения возрастает с ростом количества сортируемых элементов, однако скорость этого роста зависит от выбранного алгоритма. В этой главе будет определено время работы изучаемых алгоритмов; кроме того, вы познакомитесь со специальными обозначениями для выражения времени работы алгоритмов. В главе 3 дается точное определение обозначений, введенных в главе 2 (которые называются асимптотическими обозначениями). В начале главы 3 определяется несколько асимптотических обозначений для оценки времени работы алгоритма сверху и/или снизу.
Остальные разделы главы в основном посвящены описанию математических обозначений. Их предназначение не столько в том, чтобы ознакомить читателя с новыми математическими концепциями, сколько в том, чтобы он смог убедиться, что используемые им обозначения совпадают с принятыми в данной книге. В главе 4 представлено дальнейшее развитие метода "разделяй и властвуй", введенного в главе 2.
В частности, в главе 4 представлены методы решения рекуррентных соотношений, с помощью которых описывается время работы рекурсивных алгоритмов. Большая часть главы посвящена обоснованию "метода контроля" (шаглег телюсь), который используется для решения рекуррентных соотношений, Часть!. Основы 45 возникающих в алгоритмах разбиения. Заметим, что изучение доказательств можно опустить без ущерба для понимания материала книги.
Глава 5 служит введением в анализ вероятностей и рандомизированные алгоритмы (т.е. такие, которые основаны на использовании случайных чисел). Анализ вероятностей обычно применяется для определения времени работы алгоритма в тех случаях, когда оно может изменяться для различных наборов входных параметров, несмотря на то, что эти наборы содержат одно и то же количество параметров. В некоторых случаях можно предположить, что распределение входных величин описывается некоторым известным законом распределения вероятностей, а значит, время работы алгоритма можно усреднить по всем возможным наборам входных параметров.
В других случаях распределение возникает не из-за входных значений, а в результате случайного выбора, который делается во время работы алгоритма. Алгоритм, поведение которого определяется не только входными значениями, но и величинами, полученными с помощью генератора случайных чисел, называется рандомнзированным алгоритмом. В приложениях А-В содержится дополнительный математический материал, который окажется полезным в процессе чтения книги.
Скорее всего, вы уже знакомы с основной частью материала, содержащегося в приложениях (хотя некоторые из встречавшихся вам ранее обозначений иногда могут отличаться от тех, что приняты в данной книге). Поэтому к приложениям следует относиться как к справочному материалу. С другой стороны, не исключено, что вы еще незнакомы с большинством вопросов, рассматриваемых в части 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}
