Презентация на тему: Место и значение алгоритмов в вычислительных задачах

Хотя некоторые детали представленных примеров и выходят за рамки настоя­щей книги, в ней приводятся основные методы, применяющиеся для их решения. В книге также показано, как решить многие конкретные задачи, в том числе пе­речисленные ниже. Пусть имеется карта дорог, на которой обозначены расстояния между каж­дой парой соседних перекрестков. Наша цель — определить кратчайший путь от одного перекрестка к другому. Количество возможных маршрутов может быть огромным, даже если исключить те из них, которые содержат самопе­ресечения. Как найти наиболее короткий из всех возможных маршрутов? При решении этой задачи карта дорог (которая сама по себе является моделью настоящих дорог) моделируется в виде графа (мы подробнее познакомимся с графами в части VI и приложении Б). Задача будет заключаться в опре­делении кратчайшего пути от одной вершины графа к другой. Эффективное решение этой задачи представлено в главе 24. У нас имеются две упорядоченные последовательности символов, X = (х1, Х2, … , хт) и Y = (y1,у2,..., уп), и нам надо найти длиннейшую общую под­последовательность X и Y. Подпоследовательностью X является сама после­довательность X с некоторыми (возможно, всеми или никакими) удаленными элементами. Например, одной из подпоследовательностей (А, В, С, D, Е, F, G) является (В, С, Е, G). Наидлиннейшая общая подпоследовательность X и У дает меру схожести двух последовательностей. Например, если этими двумя последовательностями являются базовые пары в цепочках ДНК, то мы можем считать их сходными, если они имеют длинную общую подпоследователь­ность. Если X имеет т символов, a Y — п символов, то X и Y имеют 2т и 2П возможных подпоследовательностей соответственно. Выбирая все возможные подпоследовательности X и У и сопоставляя их, можно решить поставлен­ную задачу только за очень длительное время (конечно, если только т и п не оказываются очень малыми величинами). В главе 15 мы познакомимся с об­щим методом гораздо более эффективного решения этой задачи, известным как динамическое программирование.

• Хотя некоторые детали представленных примеров и выходят за рамки настоя­щей книги, в ней приводятся основные методы, применяющиеся для их решения. В книге также показано, как решить многие конкретные задачи, в том числе пе­речисленные ниже. Пусть имеется карта дорог, на которой обозначены расстояния между каж­дой парой соседних перекрестков. Наша цель — определить кратчайший путь от одного перекрестка к другому. Количество возможных маршрутов может быть огромным, даже если исключить те из них, которые содержат самопе­ресечения. Как найти наиболее короткий из всех возможных маршрутов? При решении этой задачи карта дорог (которая сама по себе является моделью настоящих дорог) моделируется в виде графа (мы подробнее познакомимся с графами в части VI и приложении Б). Задача будет заключаться в опре­делении кратчайшего пути от одной вершины графа к другой. Эффективное решение этой задачи представлено в главе 24. У нас имеются две упорядоченные последовательности символов, X = (х1, Х2, … , хт) и Y = (y1,у2,..., уп), и нам надо найти длиннейшую общую под­последовательность X и Y. Подпоследовательностью X является сама после­довательность X с некоторыми (возможно, всеми или никакими) удаленными элементами. Например, одной из подпоследовательностей (А, В, С, D, Е, F, G) является (В, С, Е, G). Наидлиннейшая общая подпоследовательность X и У дает меру схожести двух последовательностей. Например, если этими двумя последовательностями являются базовые пары в цепочках ДНК, то мы можем считать их сходными, если они имеют длинную общую подпоследователь­ность. Если X имеет т символов, a Y — п символов, то X и Y имеют 2т и 2П возможных подпоследовательностей соответственно. Выбирая все возможные подпоследовательности X и У и сопоставляя их, можно решить поставлен­ную задачу только за очень длительное время (конечно, если только т и п не оказываются очень малыми величинами). В главе 15 мы познакомимся с об­щим методом гораздо более эффективного решения этой задачи, известным как динамическое программирование.
• У нас имеется проект, который представлен в виде библиотеки составных ча­стей, причем каждая часть может включать экземпляры из других частей. Нам требуется перечислить все части в таком порядке, чтобы каждая часть появля­лась в списке до любой другой части, ее использующей. Если проект состоит из п частей, имеется п! возможных упорядочений, где n! — обозначение факто­риала. Поскольку факториал растет быстрее даже показательной функции, мы не можем просто сгенерировать все возможные упорядочения и для каждого из них проверить, соответствует ли расположение частей нашему требованию (если, конечно, частей достаточно много). Эта задача представляет собой эк­земпляр топологической сортировки, и в главе 22 мы узнаем о способе ее эффективного решения. Пусть имеется п принадлежащих плоскости точек, и нужно найти выпуклую оболочку этих точек. Выпуклой оболочкой точек называется минимальный выпуклый многоугольник, содержащий эти точки. Для решения этой задачи удобно воспользоваться такой наглядной картиной: если представить точки в виде вбитых в доску и торчащих из нее гвоздей, то выпуклую оболочку мож­но получить, намотав на них резинку таким образом, чтобы все гвозди вошли внутрь замкнутой линии, образуемой резинкой. Каждый гвоздь, вокруг кото­рого обвивается резинка, становится вершиной выпуклой оболочки (рис. 33.6 на с. 1076). В качестве набора вершин может выступать любое из 2п под­множеств множества точек. Однако недостаточно знать, какие точки являются вершинами выпуклой оболочки, нужно еще указать порядок их обхода. Таким образом, чтобы найти выпуклую оболочку, придется перебрать множество ва­риантов. В главе 33 описаны два хороших метода поиска выпуклой оболочки. Приведенные выше случаи применения алгоритмов отнюдь не являются ис­черпывающими, однако на их примере выявляются две общие характеристики, присущие многим интересным алгоритмам. Они имеют множество вариантов-кандидатов, подавляющее большинство ко­торых решениями не являются. Поиск среди них работающего (или “наилуч­шего”) кандидата является довольно сложным делом. Они имеют практическое применение. Простейший пример среди перечислен­ных задач — определение кратчайшего пути, соединяющего два перекрестка. Любая компания, занимающаяся автомобильными или железнодорожными пе­ревозками, финансово заинтересована в том, чтобы определить кратчайший маршрут. Это способствовало бы снижению затрат труда и расходов горюче­го. Маршрутизатору в Интернете также нужно иметь возможность находить кратчайшие пути в сети, чтобы как можно быстрее доставлять сообщения. Водитель, едущий из одного города в другой, может захотеть найти маршрут на веб-сайте или использовать в поездке GPS.

Структуры данных

• Структуры данных
• В книге также представлен ряд структур данных. Структура данных (data structure) — это способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию. Ни одна структура данных не является уни­версальной и не может подходить для всех целей, поэтому важно знать преиму­щества и ограничения, присущие некоторым из них.
• Методические указания
• Данную книгу можно рассматривать как “сборник рецептов” для алгоритмов. Правда, однажды вам встретится задача, для которой вы не сможете найти опуб­ликованный алгоритм (например, таковы многие из приведенных в книге упраж­нений и задач). Данная книга научит вас методам разработки алгоритмов и их анализа. Это позволит вам разрабатывать корректные алгоритмы и оценивать их эффективность самостоятельно. В разных главах рассматриваются различные ас­пекты решения алгоритмических задач. Одни главы посвящены конкретным за­дачам, таким как поиск медиан и порядковых статистик в главе 9, вычисление минимальных остовных деревьев в главе 23 и определение максимального пото­ка в сети в главе 26. Другие главы ориентированы на методы, такие как “разделяй и властвуй” в главе 4, динамическое программирование в главе 15 и амортизаци­онный анализ в главе 17.
• Сложные задачи
• Большая часть этой книги посвящена эффективным алгоритмам. Обычной ме­рой эффективности алгоритма является скорость — время, в течение которого алгоритм выдает результат. Однако существуют задачи, для которых неизвестны эффективные методы решения. В главе 34 рассматривается интересный вопрос, имеющий отношение к подобным задачам, известным как NP-полные.
• Почему NP-полные задачи представляют такой интерес? Во-первых, несмотря на то что до сих пор не найден эффективный алгоритм их решения, также не доказано, что такого алгоритма не существует. Другими словами, никто не знает, существует ли эффективный алгоритм для NP-полных задач. Во-вторых, набор NP-полных задач обладает замечательным свойством. Оно заключается в том, что если эффективный алгоритм существует хотя бы для одной из этих задач, то его можно сформулировать и для всех остальных. Эта взаимосвязь между NP- полными задачами и отсутствие методов их эффективного решения вызывают еще больший интерес к ним. В-третьих, некоторые NP-полные задачи похожи (но не идентичны) на задачи, для которых известны эффективные алгоритмы. Ученых волнует вопрос о том, как небольшое изменение формулировки задачи может значительно ухудшить эффективность самого лучшего из всех известных алгоритмов.
• Вы должны знать об NP-полных задачах, поскольку в реальных приложениях некоторые из них возникают неожиданно часто. Если перед вами встанет задача найти эффективный алгоритм для NP-полной задачи, скорее всего, вы потратите много времени на безрезультатные поиски. Если же вы покажете, что данная задача принадлежит к разряду NP-полных, то можно будет вместо самого лучшего из всех возможных решений попробовать найти достаточно эффективное.
• В качестве конкретного примера рассмотрим компанию грузового автотранс­порта, имеющую один центральный склад. Каждый день грузовики загружают­ся на этом складе и отправляются по определенному маршруту, доставляя груз в несколько мест. В конце рабочего дня грузовик должен вернуться на склад, что­бы на следующее утро его снова можно было загрузить. Чтобы сократить расхо­ды, компании нужно выбрать оптимальный порядок доставки груза в различные точки. При этом расстояние, пройденное грузовиком, должно быть минимальным. Эта задача хорошо известна как “задача о коммивояжере”, и она является NP-пол- ной. Эффективный алгоритм решения для нее неизвестен, однако при некоторых предположениях можно указать такие алгоритмы, в результате выполнения кото­рых полученное расстояние будет ненамного превышать минимально возможное. Подобные “приближенные алгоритмы” рассматриваются в главе 35.

Параллельные вычисления

• Параллельные вычисления
• Многие годы можно было считать скорость работы процессоров устойчиво возрастающей. Однако физика накладывает свои фундаментальные ограничения на скорость работы: поскольку с ростом тактовой частоты выделение тепловой мощности растет более чем линейно, микросхемы могут просто начать плавить­ся. Для повышения количества вычислений, выполняемых за единицу времени, проектировщиками все активнее используется другой путь — разработка процес­соров, содержащих несколько “ядер” Мы можем уподобить эти многоядерные компьютеры нескольким компьютерам на одном обычном процессоре; другими словами, это разновидность “параллельных компьютеров” Чтобы добиться более высокой производительности от многоядерных компьютеров, мы должны разра­батывать алгоритмы с учетом возможности параллельных вычислений. В главе 27 представлена модель для “многопоточных” (multithreaded) алгоритмов, которая использует преимущества многоядерности. Эта модель обладает рядом преиму­ществ с теоретической точки зрения и образует основу для ряда успешных про­грамм, включая программу для игры в шахматы.
• Алгоритмы как технология
• Предположим, быстродействие компьютера и объем его памяти можно уве­личивать до бесконечности. Была бы в таком случае необходимость в изучении алгоритмов? Была бы, но только для того, чтобы продемонстрировать, что метод решения имеет конечное время работы и что он дает правильный ответ. Если бы компьютеры были неограниченно быстрыми, подошел бы любой кор­ректный метод решения задачи. Возможно, вы бы предпочли, чтобы реализация решения была выдержана в хороших традициях программирования (например, ваша реализация должна быть качественно разработана и аккуратно задокумен­тирована), но чаще всего выбирался бы метод, который легче всего реализовать. Конечно же, сегодня есть весьма производительные компьютеры, но их быст­родействие не может быть бесконечно большим. Память также дешевеет, но не может стать бесплатной. Таким образом, время вычисления — такой же ограни­ченный ресурс, как и объем необходимой памяти. Вы должны разумно распоря­жаться этими ресурсами, чему и способствует применение алгоритмов, эффек­тивных в плане расходов времени и памяти.
• Эффективность
• Различные алгоритмы, разработанные для решения одной и той же задачи, часто очень сильно различаются по эффективности. Эти различия могут быть намного значительнее тех, которые вызваны применением неодинакового аппа­ратного и программного обеспечения. В качестве примера можно привести два алгоритма сортировки, которые рас­сматриваются в главе 2. Для выполнения первого из них, известного как сорти­ровка вставкой, требуется время, которое оценивается как с1п2, где п — коли­чество сортируемых элементов, а с1 — константа, не зависящая от п. Таким об­разом, время работы этого алгоритма приблизительно пропорционально п2. Для выполнения второго алгоритма, сортировки слиянием, требуется время, прибли­зительно равное С2n lg n, где lg п — краткая запись log2 n, а С2 — некоторая другая константа, не зависящая от п. Типичная константа метода вставок меньше кон­станты метода слияния, т.е. с1 < С2. Давайте убедимся, что постоянные множи­тели намного меньше влияют на время работы алгоритма, чем множители, зави­сящие от п. Запишем время работы алгоритма сортировки вставкой как с1п* п, а сортировки слиянием — как С2n • lg п. Тогда мы увидим, что там, где сорти­ровка вставкой имеет сомножитель п, сортировка слиянием содержит lgn, что существенно меньше. (Например, когда п = 1000, lgn приближенно равен 10, а когда п равно миллиону, lgn всего лишь около 20.) Хотя сортировка встав­кой обычно работает быстрее сортировки слиянием для небольшого количества сортируемых элементов, когда размер входных данных п становится достаточ­но большим, все заметнее проявляется преимущество сортировки слиянием, воз­никающее благодаря тому, что для больших n незначительная величина lgn по сравнению с п полностью компенсирует разницу величин постоянных множите­лей. Не имеет значения, во сколько раз константа с1 меньше, чем С2. С ростом количества сортируемых элементов обязательно будет достигнут переломный мо­мент, когда сортировка слиянием окажется более производительной.

В качестве примера можно привести два алгоритма сортировки, которые рас­сматриваются в главе 2. Для выполнения первого из них, известного как сорти­ровка вставкой, требуется время, которое оценивается как с1п2, где п — коли­чество сортируемых элементов, а с1 — константа, не зависящая от п. Таким об­разом, время работы этого алгоритма приблизительно пропорционально п2. Для выполнения второго алгоритма, сортировки слиянием, требуется время, прибли­зительно равное С2n lg n, где lg п — краткая запись log2 n, а С2 — некоторая другая константа, не зависящая от п. Типичная константа метода вставок меньше кон­станты метода слияния, т.е. с1 < С2. Давайте убедимся, что постоянные множи­тели намного меньше влияют на время работы алгоритма, чем множители, зави­сящие от п. Запишем время работы алгоритма сортировки вставкой как с1п* п, а сортировки слиянием — как С2n • lg п. Тогда мы увидим, что там, где сорти­ровка вставкой имеет сомножитель п, сортировка слиянием содержит lgn, что существенно меньше. (Например, когда п = 1000, lgn приближенно равен 10, а когда п равно миллиону, lgn всего лишь около 20.) Хотя сортировка встав­кой обычно работает быстрее сортировки слиянием для небольшого количества сортируемых элементов, когда размер входных данных п становится достаточ­но большим, все заметнее проявляется преимущество сортировки слиянием, воз­никающее благодаря тому, что для больших n незначительная величина lgn по сравнению с п полностью компенсирует разницу величин постоянных множите­лей. Не имеет значения, во сколько раз константа с1 меньше, чем С2. С ростом количества сортируемых элементов обязательно будет достигнут переломный мо­мент, когда сортировка слиянием окажется более производительной.

• В качестве примера можно привести два алгоритма сортировки, которые рас­сматриваются в главе 2. Для выполнения первого из них, известного как сорти­ровка вставкой, требуется время, которое оценивается как с1п2, где п — коли­чество сортируемых элементов, а с1 — константа, не зависящая от п. Таким об­разом, время работы этого алгоритма приблизительно пропорционально п2. Для выполнения второго алгоритма, сортировки слиянием, требуется время, прибли­зительно равное С2n lg n, где lg п — краткая запись log2 n, а С2 — некоторая другая константа, не зависящая от п. Типичная константа метода вставок меньше кон­станты метода слияния, т.е. с1 < С2. Давайте убедимся, что постоянные множи­тели намного меньше влияют на время работы алгоритма, чем множители, зави­сящие от п. Запишем время работы алгоритма сортировки вставкой как с1п* п, а сортировки слиянием — как С2n • lg п. Тогда мы увидим, что там, где сорти­ровка вставкой имеет сомножитель п, сортировка слиянием содержит lgn, что существенно меньше. (Например, когда п = 1000, lgn приближенно равен 10, а когда п равно миллиону, lgn всего лишь около 20.) Хотя сортировка встав­кой обычно работает быстрее сортировки слиянием для небольшого количества сортируемых элементов, когда размер входных данных п становится достаточ­но большим, все заметнее проявляется преимущество сортировки слиянием, воз­никающее благодаря тому, что для больших n незначительная величина lgn по сравнению с п полностью компенсирует разницу величин постоянных множите­лей. Не имеет значения, во сколько раз константа с1 меньше, чем С2. С ростом количества сортируемых элементов обязательно будет достигнут переломный мо­мент, когда сортировка слиянием окажется более производительной.
• В качестве примера рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нем работает алгоритм сортировки вставкой, а компьютер Б бо­лее медленный, и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоящего из десяти миллионов чисел. (Хотя десять миллионов чисел и могут показаться огромным количеством, если эти числа представляют собой восьмибайтовые целые числа, то входные данные занимают около 80 Мбайт памяти, что весьма немного да­же для старых недорогих лэптопов.) Предположим, что компьютер А выполняет десять миллиардов команд в секунду (что быстрее любого одного последователь­ного омпьютера на момент написания книги), а компьютер Б — только десять миллионов команд в секунду, так что компьютер А в тысячу раз быстрее компью­тера Б. Чтобы различие стало еще большим, предположим, что код для метода вставок (т.е. для компьютера А) написан самым лучшим в мире программистом на машинном языке и для сортировки п чисел надо выполнить 2п2 команд. Сор­тировка же методом слияния (на компьютере Б) реализована программистом-се- реднячком с помощью языка высокого уровня. При этом компилятор оказался не слишком эффективным, и в результате получился код, требующий выполнения 50n lg п команд. Для сортировки десяти миллионов чисел компьютеру А понадо­бится

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

• Как видите, использование кода, время работы которого возрастает медленнее, даже при плохом компиляторе на более медленном компьютере требует более чем в 17 раз меньше процессорного времени! Если же нужно выполнить сор­тировку ста миллионов чисел, то преимущество метода слияния становится еще более очевидным: там, где для сортировки вставкой потребуется более 23 дней, сортировка слиянием справится за четыре часа. Общее правило таково: чем боль­ше количество сортируемых элементов, тем заметнее преимущество сортировки слиянием.
• Алгоритмы и другие технологии
• Приведенный выше пример демонстрирует, что алгоритмы, как и аппаратное обеспечение компьютера, следует рассматривать как технологию. Общая произ­водительность системы настолько же зависит от эффективности алгоритма, на­сколько и от мощности применяющегося аппаратного обеспечения. В области разработки алгоритмов происходит такое же быстрое развитие, как и в других компьютерных технологиях. Возникает вопрос, действительно ли так важны алгоритмы, работающие на современных компьютерах, если и так достигнуты выдающиеся успехи в других областях высоких технологий, таких как усовершенствованные архитектуры компьютеров и технологий их изготов­ления; легкодоступные, интуитивно понятные графические интерфейсы (GUI); объектно-ориентированные системы; интегрированные веб-технологии; быстрые сети, как проводные, так и беспроводные.
• Ответ — да, безусловно. Несмотря на то что некоторые приложения не требуют алгоритмического наполнения явно (такие, как некоторые простые веб-приложе­ния), для большинства приложений оно необходимо. Например, рассмотрим веб­службу, определяющую, как добраться из одного места в другое. В основе ее ре­ализации лежит высокопроизводительное аппаратное обеспечение, графический интерфейс пользователя, глобальная сеть и, возможно, объектно-ориентирован­ный подход. Кроме того, использование алгоритмов необходимо для определен­ных операций, выполняемых данной веб-службой, например таких, как поиск маршрутов (вероятно, использующий алгоритм поиска кратчайшего пути), визуа­лизация карт и интерполяция адресов. Более того, даже приложение, не требующее алгоритмического наполнения на высоком уровне, сильно зависит от алгоритмов. Ведь известно, что работа при­ложения зависит от производительности аппаратного обеспечения, а при его раз­работке применяются разнообразные алгоритмы. Все мы также знаем, что прило­жение тесно связано с графическим интерфейсом пользователя, а для разработки любого графического интерфейса пользователя требуются алгоритмы. Вспомним приложения, работающие в сети. Чтобы они могли функционировать, необхо­димо осуществлять маршрутизацию, которая, как уже говорилось, основана на ряде алгоритмов. Чаще всего приложения составляются на языке, отличном от машинного. Их код обрабатывается компилятором или интерпретатором, который интенсивно использует различные алгоритмы. И таким примерам несть числа. Кроме того, ввиду постоянного роста вычислительных возможностей компью­теров, они применяются для решения все более и более сложных задач. Как мы уже убедились на примере сравнительного анализа двух методов сортиров­ки, с ростом сложности решаемой задачи различия в эффективности алгоритмов проявляются все значительнее.
• Знание основных алгоритмов и методов их разработки — одна из характери­стик, отличающих действительно умелого, опытного программиста от новичка. Располагая современными компьютерными технологиями, некоторые задачи мож­но решить и без основательного знания алгоритмов, однако знания в этой области позволяют достичь намного большего.

Функции сложности алгоритмов и их рост

Анализ алгоритма и его сложности

• Существует ряд важных практических причин, побуждающих нас заниматься анализом алгоритмов. Одной из них является потребность получения оценок или границ для объема памяти и времени работы, необходимых алгоритму для успешной обработки входных данных. Следует избегать разработки программы, которая за отведенное студенту машинное время не успеет обработать входные данные достаточно большого размера (например, следует признать неудовлетворительной программу обработки графов, если из-за нехватки времени она не дает ответа для графа, состоящего из десяти вершин). Лучше заранее (еще при разработке алгоритма) с помощью карандаша и бумаги оценить объем памяти и время, необходимые разрабатываемому алгоритму, а затем улучшать его (или разработать новый, более эффективный). Хороший анализ может выявить узкие места в ваших программах (например, те части программы, на выполнение которых расходуется большая часть времени), а также выбрать более подходящий алгоритм из широкого класса алгоритмов, решающих одно и то же задание.
• Для алгоритма мы определили функцию временной сложности ВРЕМЯ  (n), дающую верхнюю границу для максимального времени его работы, т.е. максимального числа основных операций (сложения, сравнения и т.д.), которые должен выполнить алгоритм при решении задачи на входных данных размером . Аналогично можно определить функцию емкостной сложности ПАМЯТЬ  (n), дающую границу для максимального числа одновременно существующих скалярных значений при выполнении на входных данных размером .