Алгоритмы - построение и анализ (1021735), страница 9
Текст из файла (страница 9)
Оно заключается в том, что если эффективный алгоритм существует хотя бы для одной из этих задач, то его можно сформулировать и для всех остальных. Эта взаимосвязь между ХР-полными задачами и отсутствие методов их эффективного решения вызывает еще ббльший интерес к ним. В третьих, некоторые ХР-полные задачи похожи (но не идентичны) на задачи, для которых известны эффективные алгоритмы. Небольшое изменение формулировки задачи может значительно ухудшить эффективность самого лучшего из всех известных алгоритмов.
Полезно располагать знаниями о ХР-полных задачах, посюльку в реальных приложениях некоторые из них возникают неожиданно часто. Если перед вами встанет задача найти эффективный алгоритм для ИР-полной задачи, скорее всего, вы потратите много времени на безрезультатные поиски. Если же вы покажете, что данная задача принадлежит к разряду ХР-полных, то можно будет вместо самого лучшего из всех возможных решений попробовать найти достаточно эффективное. Рассмотрим конкретный пример. Компания грузового автотранспорта имеет один центральный склад.
Каждый день грузовики загружаются на этом складе и отправляются по определенному маршруту, доставляя груз в несколько мест. В конце рабочего дня грузовик должен вернуться на склад, чтобы на следующее утро его снова можно было загрузить. Чтобы сократить расходы, компании нужно выбрать оптимальный порядок доставки груза в различные точки. При этом расстояние, пройденное грузовиком, должно быть минимальным.
Эта задача хорошо известна как "задача о коммивояжере", и она является ИР-полной. Эффективный алгоритм решения для нее неизвестен, однако при неюторых предположениях можно указать такие алгоритмы, в результате выполнения юторых полученное расстояние будет ненамного превышать минимально возможное. Подобные "приближенные алгоритмы" рассматриваются в главе 35. 52 Часть 1. Основы Упражнения 1.1-1. Приведите реальные примеры задач, в которых возникает одна из таких вычислительных задач: сортировка, определение оптимального порядка перемножения матриц, поиск выпуклой оболочки.
1.1-2. Какими еще параметрами, кроме скорости, можно характеризовать алгоритм на практике? 1.1-3. Выберите одну из встречавшихся вам ранее структур данных и опишите ее преимущества и ограничения. 1.1-4. Что общего между задачей об определении кратчайшего пути и задачей о коммивояжере? Чем они различаются? 1.1-5. Сформулируйте задачу, в которой необходимо только наилучшее решение. Сформулируйте также задачу, в которой может быть приемлемым решение, достаточно близкое к наилучшему. 1.2 Алгоритмы как технология Предположим, быстродействие компьютера и обьем его памяти можно увеличивать до бесконечности.
Была бы в таком случае необходимость в изучении алгоритмов? Была бы, но только для того, чтобы продемонстрировать, что метод решения имеет конечное время работы и что он дает правильный ответ. Если бы компьютеры были неограниченно быстрыми, подошел бы любой корректный метод решения задачи. Возможно, вы бы предпочли, чтобы реализация решения была выдержана в хороших традициях программирования (т.е.
качественно разработана и аккуратно занесена в документацию), но чаще всего выбирался бы метод, который легче всего реализовать. Конечно же, сегодня есть весьма производительные компьютеры, но их быстродействие не может быть бесконечно большим. Память тоже дешевеет, но она не может быть бесплатной. Таким образом, время вычисления — это такой же ограниченный ресурс, как и объем необходимой памяти.
Этими ресурсами следует распоряжаться разумно, чему и способствует применение алгоритмов, эффективных в плане расходов времени и памяти. Эффективность Алгоритмы, разработанные для решения одной и то же задачи, часто очень сильно различаются по эффективности. Эти различия могут быть намного значительнее, чем те, что вызваны применением неодинакового аппаратного и программного обеспечения. Глава 1.
Роль алгоритмов в вычислениях 53 В качестве примера можно привести два алгоритма сортировки, которые рассматриваются в главе 2. Для выполнения первого из них, известного как сортировка вставкой, требуется время, которое оценивается как с1пз, где п — количество сортируемых элементов, а с| — константа, не зависящая от п. Таким образом, время работы этого алгоритма приблизительно пропорционально пз. Для выполнения второго алгоритма, сортировки слиянием, требуется время, приблизительно равное сап !к и, где !кп — краткая запись 1окз и, а сз — некоторая другая константа, не зависящая от п. Обычно константа метода вставок меньше константы метода слияния, т.е.
с| ( сз. Мы убедимся, что постоянные множители намного меньше влияют на время работы алгоритма, чем множители, зависящие от и. Для двух приведенных методов последние относятся как )кп к и. Для небольшого количества сортируемых элементов сортировка включением обычно работает быстрее, однако когда и становится достаточно большим, все заметнее проявляется преимущество сортировки слиянием, возникающее благодаря тому, что для больших и незначительная величина 1к и по сравнению с п полностью компенсирует разницу величин постоянных множителей. Не имеет значения, во сколько раз константа с1 меньше, чем сз. С ростом количества сортируемых элементов обязательно будет достигнут переломный момент, когда сортировка слиянием окажется более производительной.
В качестве примера рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нем работает алгоритм сортировки вставкой, а компьютер Б более медленный, и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоящего из миллиона чисел. Предположим, что компьютер А выполняет миллиард инструкций в секунду, а компьютер Б — лишь десять миллионов. Таким образом, компьютер А работает в ! 00 раз быстрее, чем компьютер Б. Чтобы различие стало еще ббльшим, предположим, что код для метода вставок (т.е.
для компьютера А) написан самым лучшим в мире программистом с использованием команд процессора, и для сортировки и чисел надо выполнить 2пз команд (т.е. с1 = 2). Сортировка же методом слияния (на компьютере Б) реализована программистом-середнячком с помощью языка высокого уровня.
При этом компилятор оказался не слишком эффективным, и в результате получился код, требующий выполнения 50п 1кп команд (т.е. сз = = 50). Для сортировки миллиона чисел компьютеру А понадобится 2 (10а/ команд = 2000 с, 10экоманд / с а компьютеру Б— 50 10в 1б 10акоманд = 100 с.
10ткоманд / с Как видите, использование кода, время работы которого возрастает медленнее, даже при плохом компиляторе на более медленном компьютере требует на по- Часть Ь Основы 54 рядок меньше процессорного времени! Если же нужно выполнить сортировку 10 миллионов чисел, то преимущество метода слияния становится еще более очевидным: если для сортировки вставкой потребуется приблизительно 2.3 дня, то для сортировки слиянием — меньше 20 минут. Общее правило таково: чем больше количество сортируемых элементов, тем заметнее преимущество сортировки слиянием.
Алгоритмы и другие технологии Приведенный выше пример демонстрирует, что алгоритмы, как и аппаратное обеспечение компьютера, представляют собой технологию. Общая производительность системы настолько же зависит от эффективности алгоритма, как и от мощности применяющегося аппаратного обеспечения. В области разработки алгоритмов происходит такое же быстрое развитие, как и в других компьютерных технологиях. Возникает вопрос, действительно ли так важны алгоритмы, работающие на современных компьютерах, если и так достигнуты выдающиеся успехи в других областях высоких технологий, таких как: ° аппаратное обеспечение с высокими тактовыми частотами, конвейерной обработкой и суперскалярной архитектурой; ° легкодоступные, интуитивно понятные графические интерфейсы (О1Л); ° обьектно-ориентированные системы; ° локальные и глобальные сети. Ответ — да, безусловно.
Несмотря на то, что иногда встречаются приложения, которые не требуют алгоритмического наполнения (например, некоторые простые %еЬ-приложения), для большинства приложений определенное алгоритмическое наполнение необходимо. Например, рассмотрим %еЬ-службу, определяющую, как добраться из одного места в другое (во время написания книги существовало несколько таких служб). В основе ее реализации лежит высокопроизводительное аппаратное обеспечение, графический интерфейс пользователя, глобальная сеть и, возможно, обьекгно-ориентированный подход. Кроме того, для определенных операций, выполняемых данной %еЬ-службой, необходимо использование алгоритмов — например, таких как вычисление квадратных корней (что может потребоваться для определения кратчайшего пути), визуализации карт и интерполяции адресов.
Более того, даже приложение, не требующее алгоритмического наполнения на высоком уровне, сильно зависит от алгоритмов. Ведь известно, что работа приложения зависит от производительности аппаратного обеспечения, а при его разработке применяются разнообразные алгоритмы. Все мы также знаем, что Глава 1.
Роль алгоритмов в вычислениях приложение тесно связано с графическим интерфейсом пользователя, а для разработки любого графического интерфейса пользователя требуются алгоритмы. Вспомним приложения, работающие в сети. Чтобы они могли функционировать, необходимо осуществлять маршрутизацию, которая, как уже говорилось, основана на ряде алгоритмов. Чаще всего приложения составляются на языке, отличном от машинного. Их код обрабатывается компилятором или интерпретатором, которые интенсивно используют различные алгоритмы.
И таким примерам нет числа. Кроме того, ввиду постоянного роста вычислительных возможностей компьютеров, они применяются для решения все более сложных задач. Как мы уже убедились на примере сравнительного анализа двух методов сортировки, с ростом сложности решаемой задачи различия в эффективности алгоритмов проявляются все значительнее. Знание основных алгоритмов и методов их разработки — одна из характеристик, отличающих умелого программиста от новичка. Располагая современными компьютерными технологиями, некоторые задачи можно решить и без основательного знания алгоритмов, однако знания в этой области позволяют достичь намного большего.
Упражнения 1.2-1. Приведите пример приложения, для которого необходимо алгоритмическое наполнение на уровне приложений, и дайте характеристику функций, входящих в состав этих алгоритмов. 1.2-2. Предположим, на одной и той же машине проводится сравнительный анализ реализаций двух алгоритмов сортировки, работающих по методу вставок и по методу слияния. Для сортировки п элементов методом вставок необходимо 8пз шагов, а для сортировки методом слияния — 64п 1б и шагов. При каком значении и время сортировки методом вставок превысит время сортировки методом слияния? 1.2-3.
При каком минимальном значении п алгоритм, время работы которого определяется формулой 100пэ, работает быстрее, чем алгоритм, время работы которого выражается как 2", если оба алгоритма выполняются на одной и той же машине? Задачи 1-1. Сравнение времени работы алгоритмов Ниже приведена таблица, строки которой соответствуют различным функциям г" (и), а столбцы — значениям времени $. Определите максимальные значения и, для которых задача может быть решена за время 1, если Часть 1. Основы 56 предполагается, что время работы алгоритма, необходимое для решения задачи, равно ! (и) микросекунд. Заключительные замечания Имеется множество учебников, посвященных общим вопросам, которые имеют отношение к алгоритмам.
К ним относятся книги Ахо (АЬо), Хопкрофта (Норсгой) и Ульмана ((71!шап) [5,6], Бейза (Ваазе) и Ван Гельдера (Уап Ое16ег) [26], Брассарда (Вгаввап1) и Бретли (Вга!1еу) [46,47], Гудрича (Оотг(сЬ) и Тамазии (Татазз1а) [128], Горовица (Ногочч!!х), Сани (БаЬп1) и Раджисекарана (Ка]азекагап) [158], Кингстона (К]пйз!оп) [179], Кнута (Кпи1Ь) [182,183,185], Козена (Кожев) [193], Манбера (МапЬег) [210], Мельхорна (МеЬ1Ьош) [217,218,219], Пурдома (Рип1ош) и Брауна (Вготчл) [252], Рейнгольда (Ке!пйо16), Ньевергельта (Ы!ечегйе1!) и Део (Оео) [257], Седжевика (Яебйев1ск) [269], Скьены (Яс!ела) [280] и Вильфа (%!!1) [315]. Некоторые аспекты разработки алгоритмов, имеющие большую практическую направленность, обсуждаются в книгах Бентли (Веп11еу) [39,40] и Гоннета (Ооппе!) [126].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
