Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 4

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

Мы внимательно ознакомимся с вашим мнением и обязательно учтем его при отборе и подготовке к изданию последующих книг. Наши координаты: Е-ша11: зпбойиз11хашвриЫ1в1тзпд.сов %%%: 1зсср: /lиим. и111зааврпЫзвЫпд. сот Адреса для писем из: России; 127055, г. Москва, ул. Лесная, д. 43, стр. 1 Украины: 03150, Киев, а/я 152 Введение Эта часть книги заставит вас задуматься о вопросах, связанных с разработкой и анализом алгоритмов.

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

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

Для изучения выбраны алгоритм сортировки вставкой, в котором используется инкрементный подход, и алгоритм сортировки слиянием, который характеризуется применением рекурсивного метода, известного также как метод "разделяй и властвуй" (метод разбиения). В обоих алгоритмах время выполнения возрастает с увеличением количества сортируемых элементов, однако скорость этого роста зависит от выбранного алгоритма.

В этой главе будет определено время работы изучаемых алгоритмов; кроме того, вы познакомитесь со специальными обозначениями для описания времени работы алгоритмов. В главе 3 дается точное определение обозначений, введенных в главе 2 (которые называются асимптотическими обозначениями). В начале главы 3 опре- Часть 1.

Основы 25 делается несколько асимптотических обозначений для оценки времени работы алгоритма сверху и/или снизу. Остальные разделы главы в основном посвящены математическим обозначениям. Их предназначение состоит не столько в том, чтобы ознакомить читателя с новыми математическими концепциями, сколько в том, чтобы он смог убедиться, что используемые им обозначения совпадают с принятыми в данной книге. В главе 4 представлено дальнейшее развитие метода "разделяй и властвуй*; введенного в главе 2. В главе 4 приведены дополнительные примеры алгоритмов "разделяй и властвуй", включая удивительный метод Штрассена для умножения двух квадратных матриц.

В ней также представлены методы решения рекуррентных соотношений, с помощью которых описывается время работы рекурсивных алгоритмов. Одним из мощных методов является "основной метод" (шаыег шебюд), который используется для решения рекуррентных соотношений, возникающих в алгоритмах разбиения. Хотя немалая часть главы посвящена доказательству корректности метода контроля, вы можете его опустить, что не помешает применению метода на практике.

Глава 5 служит введением в анализ вероятностей и рандомизированные алгоритмы (т.е. алгоритмы, которые основаны на использовании случайных чисел). Анализ вероятностей обычно применяется для определения времени работы алгоритма в тех случаях, когда оно может изменяться для различных наборов входных параметров, несмотря на то что эти наборы содержат одно и то же количество параметров. В некоторых случаях можно предположить, что распределение входных величин описывается некоторым известным законом распределения вероятностей, а значит, время работы алгоритма можно усреднить по всем возможным наборам входных параметров.

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

В приложениях А — Г содержится дополнительный математический материал, который будет полезным в процессе чтения книги. Скорее всего, вы уже знакомы с основной частью материала, содержащегося в приложениях (хотя некоторые из встречавшихся вам ранее обозначений иногда могут отличаться от принятых в данной книге).

Поэтому к приложениям следует относиться как к справочному материалу. С другой стороны, не исключено, что вы еще не знакомы с большинством вопросов, рассматриваемых в части!. Глава 1. Роль алгоритмов в вычислениях Что такое алгоритмы? Стоит ли тратить время на их изучение? Какова роль алгоритмов и как они соотносятся с другими компьютерными технологиями? В этой главе мы ответим на поставленные здесь вопросы. 1.1.

Что такое алгоритмы Говоря неформально, алгоритм — это любая корректно определенная вычислительная процедура, на вход (!прп!) которой подается некоторая величина или набор величин и результатом выполнения которой является выходная (ошрш) величина или набор значений.

Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующих входные величины в выходные. Алгоритм также можно рассматривать как инструмент, предназначенный для решения корректно поставленной вычислительной задачи (сошрщайопа! ргоЬ- !еш). В постановке задачи в общих чертах задаются отношения между входом и выходом. В алгоритме описывается конкретная вычислительная процедура, с помощью которой удается добиться выполнения указанных отношений.

Например, может понадобиться выполнить сортировку последовательности чисел в неубывающем порядке. Эта задача часто возникает на практике и служит благодатной почвой для ознакомления на ее примере со многими стандартными методами разработки и анализа алгоритмов. Задача сортировки (аогйпй ргоЬ!егп) формально определяется следующим образом. Вход. Последовательность из и чисел (аы аз,..., а„). Выход. Перестановка (переупорядочение) (а1, аз, ..., а'„) входной последовательности, такая, что аг, < а!г « а Например, если на вход подается последовательность (31, 41, 59, 26, 41, 58), то вывод алгоритма сортировки должен быть таким; (26, 31, 41, 41, 58, 59).

Подобная входная последовательность называется экземиляраи ()па!апсе) задачи сортировки. Вообще говоря, зкзаииляр задачи состоит из входных данных (удовлетворяю- Гчава Г Раль алюритиов в вмииелеиивл щих всем ограничениям, наложенным при постановке задачи), необходимых для решения задачи. Поскольку многие программы используют ее в качестве промежуточного шага, сортировка является основополагающей операцией в информатике, в результате чего появилось большое количество хороших алгоритмов сортировки. Выбор наиболее подходящего алгоритма зависит от многих факторов, в том числе от количества сортируемых элементов, от их порядка во входной последовательности, от возможных ограничений, накладываемых на члены последовательности„ от архитектуры компьютера, а также от того, какое устройство используется для хранения последовательности: основная память, магнитные диски или даже накопители на магнитных лентах.

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

Такой пример алгоритма с контролируемой частотой ошибок рассматривается в главе 31, в которой изучаются алгоритмы определения большйх простых чисел. Тем не менее обычно мы заинтересованы только в корректных алгоритмах. Алгоритм может быть задан на естественном языке, в виде компьютерной программы или даже воплощен в аппаратном обеспечении. Единственное требование — его спецификация должна предоставлять точное описание вычислительной процедуры, которую требуется выполнить. Какие задачи решаются с помощью алгоритмов Вычислительные задачи, для которых разработаны алгоритмы, отнюдь не ограничиваются сортировкой.

(Возможно, об их разнообразии можно судить по объему данной книги.) Практическое применение алгоритмов чрезвычайно широко, о чем свидетельствуют приведенные ниже примеры. Проект по расшифровке генома человека далеко продвинулся по направлению к своей цели — к идентификации всех ста тысяч генов, входящих в состав ДНК человека, определению последовательностей, образуемых тремя миллиардами базовых пар, из которых состоит ДНК, к сортировке этой информации в базах данных и разработке инструментов для ее анализа.

Для реализации всех перечисленных этапов нужны сложные алгоритмы. Хотя решение разнообразных задач, являющихся составными частями данного проекта, выходит за рамки настоящей книги, идеи, описанные во многих ее главах, используются для решения упомянутых биологических проблем. Это позволяет ученым достигать поставленных целей, эффективно используя вычислительные ресурсы. При этом экономятся время (как машинное, так и затрачиваемое сотрудниками) и деньги, а также повышается эффективность использования лабораторного оборудования.