Автор: Стивен С. Скиена Год: 2011 ISBN: 978-5-9775-0560-4 Страниц: 722 Язык: Русский Формат: PDF +code Размер: 27 Мб Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования.

• Алгоритмы. Руководство По Разработке Стивен Скиена Скачать
• Скиена Алгоритмы. Руководство По Разработке Pdf
• Алгоритмы. Руководство По Разработке Стивен Скиена

1. Представляем вниманию программистов и студентов, изучающих программную инженерию и компьютерные науки второе издание популярного бестселлера профессора.
2. Инструкция как скачать книгу Стивен Скиена: Алгоритмы. Руководство по разработке.

Книга: Алгоритмы.Руководство по разработке. Автор: Скиена Стивен. Аннотация, отзывы. Купить книгу «Алгоритмы. Руководство по разработке» автора Стивен Скиена и другие.

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

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

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

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

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

Его корректность, редко поддается очевидной оценке. Алгоритмы обычно сопровождаются доказательством их правильности в виде объяснения, почему для каждого экземпляра задачи будет выдан требуемый результат. Но прежде чем продолжить обсуждение темы, мы продемонстрируем, что аргумент “это очевидно” никогда не является достаточным доказательством правильности алгоритма.

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

Таким образом, маршрут манипулятора является замкнутым маршрутом, или циклом. Так как роботы являются дорогостоящими устройствами, мы хотим минимизировать время, затрачиваемое манипулятором на обработку платы. Будет логичным предположить, что манипулятор перемещается с постоянной скоростью; соответственно, время перемещения от одной точки к другой прямо пропорционально расстоянию между точками. То есть, нам нужно найти алгоритмическое решение такой задачи: Обоснование правильности алгоритмов Будем надеяться, что предшествующие примеры продемонстрировали вам всю сложность темы правильности алгоритмов. Правильные алгоритмы выделяются из общего числа с помощью специальных инструментов, главный из которых называется доказательством. Адекватное математическое доказательство состоит из нескольких частей.

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

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

Все три способа являются полезными, т. Существует естественное стремление к компромиссу между легкостью восприятия и точностью представления алгоритма. Наиболее простым для понимания “языком программирования” является обычный язык, но в то же время он наименее точен. С другой стороны, такие языки, как Java или C/C, позволяют точно выразить алгоритм, но создавать и понимать алгоритмы на этих языках задача не из легких. В отношении сложности применения и понимания псевдокод представляет золотую середину между этими двумя крайностями.

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

Не допускайте ошибку, которую часто делают мои студенты, — используют псевдокод, чтобы приукрасить плохо определенную идею и придать ей более формальный и солидный вид. При описании алгоритма следует стремиться к ясности. Например, алгоритм ExhaustiveScheduling (см.

Листинг 1.7) можно было бы выразить на обычном языке так, как показано в листинге 1.9. Анализ алгоритмов Алгоритмы являются принципиально важным компонентом информатики, т.

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

Этот способ оценки производительности является наиболее трудным материалом в данной книге. Но когда вы поймете основу этих идей на интуитивном уровне, вам будет намного легче разобраться в формальной составляющей. Модель вычислений RAM Разработка машинно-независимых алгоритмов основывается на гипотетическом компьютере, называющемся машиной с произвольным доступом к памяти (Random Access Machine) или RAM-машиной. Согласно этой модели наш компьютер работает таким образом:. для исполнения любой простой операции (+,., -, =, if, call) требуется ровно один временной шаг;.

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

Кроме этого, наш компьютер обладает неограниченным объемом оперативной памяти. Кэш и диск в модели RAM не применяются. Время исполнения алгоритма в RAM-модели вычисляется по общему количеству ‘шагов, требуемых алгоритму для решения данного экземпляра задачи. Допуская, что наша RAM-машина исполняет определенное количество шагов/операций за секунду, количество шагов легко перевести в единицы времени. Может показаться, что RAM-модель является слишком упрощенным представлением работы компьютеров., В конце концов, на большинстве процессоров умножение двух чисел занимает больше времени, чем сложение, что не вписывается в первое предположение модели.

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

Тем не менее, несмотря на эти несоответствия настоящему компьютеру, RAM-модель является превосходной моделью для понимания того, как алгоритм будет работать на настоящем компьютере. Она обеспечивает хороший компромисс, отражая поведение компьютеров и одновременно являясь простой в использовании.

Эти характеристики делают RAM-модель полезной для практического применения. Любая модель полезна лишь в определенных рамках. Возьмем, например, модель плоской Земли.

Можно спорить, что это неправильная модель, т. Еще древние греки знали, что в действительности Земля круглая. Но модель плоской Земли достаточно точна для закладки фундамента дома. Более того, в данном случае с моделью плоской Земли настолько удобнее работать, что использование модели сферической Земли для этой цели даже не приходит в голову.

Та же самая ситуация наблюдается и в случае с RAM-моделью вычислений — мы создаем, вообще говоря, очень полезную абстракцию. Довольно трудно создать алгоритм, для которого RAM-модель выдаст существенно неверные результаты. Устойчивость RAM-модели позволяет анализировать алгоритмы машинно-независимым способом.

Алгоритмы можно изучать и анализировать, не прибегая к использованию конкретного языка программирования или компьютерной платформы. Структуры данных Замену структуры данных в медленно работающей программе сравнить с пересадкой органа. Такие важные классы абстрактных типов данных, как контейнеры, словари и очереди с приоритетами, могут реализовываться посредством разных, но функционально эквивалентных структур данных.

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

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

Здесь мы обсудим три фундаментальных абстрактных типа данных, контейнеры, словари и очереди с приоритетами, и рассмотрим, как они реализуются посредством массивов и списков. Более сложные реализации структур данных рассматриваются в релевантной задаче в каталоге задач. Сортировка и поиск Студенты, получающие специальность, связанную с вычислительными системами, изучают основные алгоритмы сортировки по крайней мере три раза: сначала во введении в программирование, затем в курсе по структурам данных и, наконец, в курсе разработки и анализа алгоритмов. Почему сортировке уделяется так много внимания? На то есть ряд причин. Сортировка является базовым строительным блоком, на котором основаны многие алгоритмы.

Понимание сортировки расширяет наши возможности при решении других задач. Большинствр интересных идей, которые используются в разработке алгоритмов (в частности, метод “разделяй и властвуй”, структуры данных и рандомизированные алгоритмы), возникло в контексте сортировки. Исторически сложилось так, что на сортировку уходит больше компьютерного времени, чем на остальные задачи.

Четверть циклов всех мэйнфреймов была использованы для сортировки данных Knu98. Сортировка по-прежнему остается самой распространенной практической алгоритмической задачей. Сортировка— самая изученная задача в теории вычислительных систем. Известны буквально десятки алгоритмов сортировки, большинство из которых имеют определенное преимущество над другими алгоритмами в определенных ситуациях. В этой главе мы обсудим сортировку, уделяя особое внимание тому, как ее можно применить для решения других задач. Мы рассмотрим подробное описание нескольких фундаментальных алгоритмов, — пирамидальной сортировки (heapsort), сортировки слиянием (mergesort), быстрой сортировки (quicksort) и сортировки распределением (distribution sort),— представляющих собой примеры важных парадигм разработки алгоритмов. Задача сортировки также представлена в разделе 14.1.

Обход графов Графы являются одной из важнейших областей теории вычислительных систем. Это абстрактное понятие, посредством которого можно описывать разнообразные реальные явления— организацию транспортных систем, человеческих взаимоотношений, сети передачи данных и т. Возможность формального моделирования такого множества разных реальных структур позволяет программисту решать широкий круг прикладных задач. Более конкретно, граф G = (V9E) состоит из набора вершин Vw набора ребер Е, соединяющих пары вершин. С помощью графов можно представить практически любые взаимоотношения. Например, посредством графов можно создать модель сети дорог, представляя населенные пункты верщинами, а дороги между ними — соединяющими соответствующие вершины ребрами. С помощью графов можно также моделировать электронные схемы, представляя компоненты вершинами, а соединения компонентов — ребрами.

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

Ключевым аспектом эффективного использования алгоритмов на графах является правильное моделирование задачи, чтобы можно было воспользоваться уже существующими алгоритмами. Знакомство с разными типами алгоритмических задач важнее знания деталей отдельных алгоритмов, особенно если учесть, что во второй части этой книги можно найти решение задачи по ее названию. В этой главе рассматриваются основные структуры данных и операции обхода графов, которые можно будет использовать при поиске решений базовых задач на графах. В главе 6 рассматриваются более сложные алгоритмы для работы с графами: построение минимальных остовных деревьев (minimum spanning tree), кратчайшего пути и потоков в сети.

Алгоритмы. Руководство По Разработке Стивен Скиена Скачать

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

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

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

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

Динамическое программирование— это технология для эффективной реализации рекурсивных алгоритмов посредством сохранения промежуточных результатов. Секрет ее применения заключается в определении, выдает ли простой рекурсивный алгоритм одинаковые результаты для одинаковых подзадач. Если выдает, то вместо повторения вычислений ответ каждой подзадачи можно сохранять в таблице для использования в дальнейшем, что дает возможность получить Эффективный алгоритм. Начинаем разработку с определения и отладки рекурсивного алгоритма.

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

Скиена Алгоритмы. Руководство По Разработке Pdf

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

Алгоритмы. Руководство По Разработке Стивен Скиена

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