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

Во-вторых, набор ХР-полных задач обладает замечательным свойством. Оно заключается в том, что если эффективный алгоритм существует хотя бы для одной из этих задач, то его можно сформулировать и для всех остальных. Эта взаимосвязь между ХР- полными задачами и отсутствие методов их эффективного решения вызывают еще больший интерес к ним. В-третьих, некоторые ХР-полные задачи похожи 1но не идентичны) на задачи, для которых известны эффективные алгоритмы. Ученых волнует вопрос о том, как небольшое изменение формулировки задачи может значительно ухудшить эффективность самого лучшего нз всех известных алгоритмов. Вы должны знать об ХР-полных задачах, поскольку в реальных приложениях некоторые из них возникают неожиданно часто.

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

Чтобы сократить расходы, компании нужно выбрать оптимальный порядок доставки груза в различные точки. При этом расстояние, пройденное грузовиком, должно быть минимальным. Эта задача хорошо известна как "задача о коммивояжере", и она является ХР-полной. Эффективный алгоритм решения для нее неизвестен, однако при некоторых предположениях можно указать такие алгоритмы, в результате выполнения которых полученное расстояние будет ненамного превышать минимально возможное.

Подобные "приближенные алгоритмы" рассматриваются в главе 35. Параллельные вычислении Многие годы можно было считать скорость работы процессоров устойчиво возрастающей. Однако физика накладывает свои фундаментальные ограничения Часмь 1 Основы на сюрость работы: поскольку с ростом тактовой частоты выделение тепловой мощности растет более чем линейно, микросхемы могут просто начать плавиться. Для повышения количества вычислений, выполняемых за единицу времени, проектировщиками все активнее используется другой путь — разработка процессоров, содержащих несколько "ядер". Мы можем уподобить зти многоядерные компьютеры нескольким компьютерам на одном обычном процессоре; другими словами, зто разновидность "параллельных компьютеров".

Чтобы добиться более высокой производительности от многоядерных компьютеров, мы должны разрабатывать алгоритмы с учетом возможности параллельных вычислений. В главе 27 представлена модель для "многопоточных" (шп!йЬтеабеб) алгоритмов, которая использует преимущества многоядерности. Эта модель обладает рядом преимуществ с теоретической точки зрения и образует основу для ряда успешных программ, включая программу для игры в шахматы. Упражнения 1.1.1 Приведите реальные примеры задач, в которых возникает потребность в сортировке или вычислении выпуклой оболочки. 1.1.г Какими еще параметрами, кроме скорости, можно характеризовать алгоритм на практике? 1.1.3 Выберите одну из встречавшихся вам ранее структур данных и опишите ее пре- имущества и ограничения.

1.1.4 Что общего между задачей об определении кратчайшего пути и задачей о коммивояжере? Чем они различаются? 1.1.5 Сформулируйте задачу, в которой необходимо только наилучшее решение. Сформулируйте также задачу, в юторой может быть приемлемым решение, достаточно близкое к наилучшему. 1.2.

Алгоритмы как технология Предположим„быстродействие компьютера и объем его памяти можно увеличивать до бесюнечности. Была бы в таком случае необходимость в изучении алгоритмов? Была бы, но только для того, чтобы продемонстрировать, что метод решения имеет конечное время работы и что он дает правильный ответ. Глава 1. Роль алгоритмов в вычиглеиилл Если бы компьютеры были неограниченно быстрыми, подошел бы любой корректный метод решения задачи. Возможно, вы бы предпочли, чтобы реализация решения была выдержана в хороших традициях программирования (например, ваша реализация должна быть качественно разработана и аккуратно задокументирована), но чаще всего выбирался бы метод, который легче всего реализовать. Конечно же, сегодня есть весьма производительные компьютеры, но их быстродействие не может быть бесконечно большим. Память также дешевеет, но не может стать бесплатной.

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

Таким образом, время работы этого алгоритма приблизительно пропорционально пз. Для выполнения второго алгоритма, сортировки слиянием, требуется время, приблизительно равное сап )яп, где )ни — краткая запись 1ояз и, а сз — некоторая другая константа, ие зависящая от и. Типичная константа метода вставок меньше константы метода слияния, т.е.

с~ < сз. Давайте убедимся, что постоянные множители намного меньше влияют на время работы алгоритма, чем множители, зависящие от и. Запишем время работы алгоритма сортировки вставкой как с1п. и, а сортировки слиянием — как сзп 1яп. Тогда мы увидим, что там, где сортировка вставкой имеет сомножитель и, сортировка слиянием содержит 1кп, что существенно меньше. (Например„когда и = 1000, 1яп приближенно равен 10, а когда и равно миллиону, 1яп всего лишь около 20.) Хотя сортировка вставкой обычно работает быстрее сортировки слиянием для небольшого количества сортируемых элементов, когда размер входных данных и становится достаточно большим, все заметнее проявляется преимущество сортировки слиянием, возникающее благодаря тому, что для больших п незначительная величина!яп по сравнению с и полностью компенсирует разницу величин постоянных множителей.

Не имеет значения, во сколько раз константа сз меньше, чем сз. С ростом количества сортируемых элементов обязательно будет достигнут переломный момент, когда сортировка слиянием окажется более производительной. В качестве примера рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нем работает алгоритм сортировки вставкой, а компьютер Б более медленный, и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоящего из десяти г эьь зглв Часть Л Основы миллионов чисел. (Хотя десять миллионов чисел и могут показаться огромным количеством, если эти числа представляют собой восьмибайтовые целые числа, то входные данные занимают около 80 Мбайт памяти, что весьма немного даже для старых недорогих лэптопов.) Предположим, что компьютер А выполняет десять миллиардов команд в секунду (что быстрее любого одного последовательного компьютера на момент написания книги), а компьютер Б — только десять миллионов команд в секунду, так что компьютер А в тысячу раз быстрее компьютера Б.

Чтобы различие стало еше большим, предположим, что код для метода вставок (т.е. для компьютера А) написан самым лучшим в мире программистом на машинном языке и для сортировки и чисел надо выполнить 2па команд. Сортировка же методом слияния (на компьютере Б) реализована программистом-середнячком с помощью языка высокого уровня. При этом компилятор оказался не слишком эффективным, и в результате получился код, требующий выполнения 50п 18 п команд. Для сортировки десяти миллионов чисел компьютеру А понадобится 2 (10т)з команд = 20000 секунд (более 5.5 часов), 10'о команд в секунду в то время как компьютеру Б потребуется 50 10т 1810" команд 1163 секунд (менее 20 минут) .

10т команд в секунду Как видите, использование кода, время работы которого возрастает медленнее, даже прн плохом компиляторе на более медленном компьютере требует более чем в 17 раз меньше процессорного времени! Если же нужно выполнить сортировку ста миллионов чисел, то преимушество метода слияния становится еще более очевидным: там, где для сортировки вставкой потребуется более 23 дней, сортировка слиянием справится за четыре часа. Общее правило таково: чем больше количество сортируемых элементов, тем заметнее преимушество сортировки слиянием. Алгоритмы и другие технологии Приведенный выше пример демонстрирует, что алгоритмы, как и аппаратное обеспечение компьютера, следует рассматривать как технологию.

Общая производительность системы настолько же зависит от эффективности алгоритма, насколько и от мощности применяющегося аппаратного обеспечения. В области разработки алгоритмов происходит такое же быстрое развитие„как и в других компьютерных технологиях. Возникает вопрос, действительно ли так важны алгоритмы, работающие на современных компьютерах, если и так достигнуты выдающиеся успехи в других областях высоких технологий, таких как усовершенствованные архитектуры компьютеров и технологий их изготов- ления; легкодоступные, интуитивно понятные графические интерфейсы (О1Л); 35 Глава д Ролл алгоритмов в вычиелениал объектно-ориентированные системы; интегрированные веб-технологии; быстрые сети, как проводные, так и беспроводные. Ответ — да, безусловно. Несмотря на то что некоторые приложения не требуют алгоритмического наполнения явно (такие, как некоторые простые веб-приложения), для большинства приложений оно необходимо.

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

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