Рейтинг: 4.5/5.0 (1823 проголосовавших)Категория: Руководства
Второе издание популярного бестселлера "Алгоритмы. Руководство по разработке " раскрывает тайны проектирования алгоритмов, анализа их действенности и эффективности. Развивая успешную концепцию первого издания, книга является отличным практическим руководством по разработке эффективных алгоритмов, содержит практические упражнения и готовые решения 75 - ти проблем алгоритмизации. Рассмотрены основы организации данных, операции сортировки, поиска, работы с графами и другие темы современного программирования.
Профессор Стивен С. Скиена, заслуженный исследователь алгоритмов и лауреат компьютерных наук IEEE, предоставляет полную онлайн - поддержку для преподавателей на полностью обновлённом и улучшенном сайте с лекциями, слайдами, аудио - и видеоматериалами. Несмотря на сложность рассматриваемого материала, его стиль остаётся лёгким для восприятия с разумной долей юмора. Часто он встраивает в текст истории, приключившиеся с ним как разработчиком программного обеспечения, которые прекрасно иллюстрируют описанные методы на практике.
Книга "Алгоритмы. Руководство по разработке " станет полезным справочником для программистов и отличным учебным пособием для студентов, изучающих программную инженерию и компьютерные науки.
Название: Алгоритмы. Руководство по разработке
Год выпуска: 2011
Издательство: БХВ-Петербург
Автор: Стивен Скиена
Язык: Русский
Страниц: 720
Качество: Хорошее
Формат: PDF
Размер: 215,99 MB
Скачать Алгоритмы. Руководство по разработке:
Похожие новости Комментарии (0)
Стивен Скиена | Алгоритмы. Руководство по разработке [2011] [DJVU]
Описание:
Второе издание популярного бестселлера "Алгоритмы. Руководство по разработке" раскрывает тайны проектирования алгоритмов, анализа их действенности и эффективности. Развивая успешную концепцию первого издания, книга является отличным практическим руководством по разработке эффективных алгоритмов, содержит практические упражнения и готовые решения 75-ти проблем алгоритмизации. Рассмотрены основы организации данных, операции сортировки, поиска, работы с графами и другие темы современного программирования.
Профессор Стивен С. Скиена, заслуженный исследователь алгоритмов и лауреат компьютерных наук IEEE, предоставляет полную онлайн-поддержку для преподавателей на полностью обновлённом и улучшенном сайте с лекциями, слайдами, аудио- и видеоматериалами. Несмотря на сложность рассматриваемого материала, его стиль остаётся лёгким для восприятия с разумной долей юмора. Часто он встраивает в текст истории, приключившиеся с ним как разработчиком программного обеспечения, которые прекрасно иллюстрируют описанные методы на практике.
Книга "Алгоритмы. Руководство по разработке" станет полезным справочником для программистов и отличным учебным пособием для студентов, изучающих программную инженерию и компьютерные науки.
Скриншоты:
Для скачивания .torrent файлов необходима регистрация
Сайт не распространяет и не хранит электронные версии произведений, а лишь предоставляет доступ к создаваемому пользователями каталогу ссылок на торрент-файлы. которые содержат только списки хеш-сумм
(голосов: 1 ) | 18 июля 2012 | Просмотров: 14718
Название: Алгоритмы. Руководство по разработке, 2-е издание
Автор: Стивен Скиена
Издательство: БХВ-Петербург
Год: 2011
ISBN: 978-5-9775-0560-4, 978-1-84800-069-8
DJVU: 16 Мб
Известно, что основой любой программы является правильно разработанный алгоритм. Пособие "Алгоритмы. Руководство по разработке" – одно из немногих, посвященных вопросу анализа алгоритмов задач и методам разработки наиболее эффективных.
Книга состоит из двух частей. Первая представляет собой изложение основных теоретических понятий, подкрепленных соответствующими практическими примерами. В ней даются базовые понятия, обзор алгоритмов, структуры данных, основы дискретной математики: комбинаторики, теории графов, сортировок. Приводятся методы поиска, обхода графов, динамического программирования и эвристической методологии. Во второй части собрана большая библиография, каталог из 75 алгоритмических задач, имеющих наиболее частое применение на практике. Множество приведенных конкретных задач позволяют разобраться в нюансах алгоритмизации.
Книгу можно использовать и как учебное пособие для вузов, и как справочник для программистов и инженеров, нуждающихся в эффективной алгоритмизации задач.
UniBytes (DJVU)
GigaBase (DJVU)
Share4web (DJVU)
Алгоритмы. Руководство по разработке
Год: 2011
Автор: Скиена С.
Переводчик: Таранушенко С.
Жанр: Пособие
Издательство: БХВ-Петербург
ISBN: 798-5-9775-0560-4
Язык: Русский
Формат: DjVu
Качество: Отсканированные страницы
Количество страниц: 720
Описание: Второе издание популярного бестселлера "Алгоритмы. Руководство по разработке" раскрывает тайны проектирования алгоритмов, анализа их действенности и эффективности. Развивая успешную концепцию первого издания, книга является отличным практическим руководством по разработке эффективных алгоритмов, содержит практические упражнения и готовые решения 75-ти проблем алгоритмизации. Рассмотрены основы организации данных, операции сортировки, поиска, работы с графами и другие темы современного программирования.
Профессор Стивен С. Скиена, заслуженный исследователь алгоритмов и лауреат компьютерных наук IEEE, предоставляет полную онлайн-поддержку для преподавателей на полностью обновлённом и улучшенном сайте с лекциями, слайдами, аудио- и видеоматериалами. Несмотря на сложность рассматриваемого материала, его стиль остаётся лёгким для восприятия с разумной долей юмора. Часто он встраивает в текст истории, приключившиеся с ним как разработчиком программного обеспечения, которые прекрасно иллюстрируют описанные методы на практике.
Книга "Алгоритмы. Руководство по разработке" станет полезным справочником для программистов и отличным учебным пособием для студентов, изучающих программную инженерию и компьютерные науки.
К сожалению пока никто не оставил комментарий ;(
© 2009–2016, Торрентино
По всем вопросам обращаться на admin@torrentino.me
Правообладателям просьба писать вежливо и своевременно: abuse@torrentino.me и мы отнесемся к вашей просьбе с пониманием.
Название: Алгоритмы. Руководство по разработке
Автор: Стивен Скиена
Формат: DJVU
Размер: 11 Мб
Качество: Нормальное
Язык: Русский
Год издания: 2011
Второе издание популярного бестселлера "Алгоритмы. Руководство по разработке" раскрывает тайны проектирования алгоритмов, анализа их действенности и эффективности. Развивая успешную концепцию первого издания, книга является отличным практическим руководством по разработке эффективных алгоритмов, содержит практические упражнения и готовые решения 75-ти проблем алгоритмизации. Рассмотрены основы организации данных, операции сортировки, поиска, работы с графами и другие темы современного программирования.
Профессор Стивен С. Скиена, заслуженный исследователь алгоритмов и лауреат компьютерных наук IEEE, предоставляет полную онлайн-поддержку для преподавателей на полностью обновлённом и улучшенном сайте с лекциями, слайдами, аудио- и видеоматериалами. Несмотря на сложность рассматриваемого материала, его стиль остаётся лёгким для восприятия с разумной долей юмора. Часто он встраивает в текст истории, приключившиеся с ним как разработчиком программного обеспечения, которые прекрасно иллюстрируют описанные методы на практике.
Книга "Алгоритмы. Руководство по разработке" станет полезным справочником для программистов и отличным учебным пособием для студентов, изучающих программную инженерию и компьютерные науки.
С этой книгой бесплатно скачивают:
pdf 131,45 мб - Гагарина Л.Г. Колдаев В.Д.
pdf 16,09 mb - Никлаус Вирт
djvu 20.3 мб - Макконнели С.
pdf 27.6 мб - Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман
djvu 27.6 мб - Род Стивенс
Электронная библиотека Kodges.ru — интересный ресурс для тех, кто не любит тратить много времени на поиск необходимого издания. В каталогах представлено огромное количество книг различной тематики, которые можно скачать совершенно бесплатно в нужном формате. В разделе «Компьютерная литература» можно скачать как книги для профессионалов, так и книги с ответами на популярные вопросы, например, «Алгоритмы. Руководство по разработке». Благодаря удобной навигации библиотеки, каждый читатель моментально найдет необходимое издание.
Поделитесь ссылкой на книгу со своими друзьями:
Ссылка для форумов:
Просмотров: 1 771 | Комментарии (0)
Навигация по сайту
© 2006 - 2016 KodGes.RU
2-е изд. Пер. с англ. — СПб. БХВ-Петербург. 2011. — 720 с. ил.
Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации. Приведены многочисленные примеры задач.
Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей.
Оглавление:
Предисловие
Читателю
Преподавателю
Благодарности
Ограничение ответственности
Практическая разработка алгоритмов
Введение в разработку алгоритмов
Оптимизация маршрута робота
Задача календарного планирования
Обоснование правильности алгоритмов
Моделирование задачи
Истории из жизни
История из жизни. Моделирование проблемы ясновидения
Упражнения
Анализ алгоритмов
Модель вычислений RAM
Асимптотические обозначения
Скорость роста и отношения доминирования
Работа с асимптотическими обозначениями
Сложение функций
Умножение функций
Оценка эффективности
Логарифмы и их применение
Свойства логарифмов
История из жизни. Загадка пирамид
Анализ высшего уровня
Упражнения
Структуры данных
Смежные и связные структуры данных
Стеки и очереди
Словари
Двоичные деревья поиска
Очереди с приоритетами
История из жизни. Триангуляция
Хеширование и строки
Специализированные структуры данных
История из жизни. Геном человека
Упражнения
Сортировка и поиск
Применение сортировки
Практические аспекты сортировки
Пирамидальная сортировка
История из жизни. Билет на самолет
Сортировка слиянием. Метод "разделяй и властвуй"
Быстрая сортировка. Рандомизированная версия
Сортировка распределением. Метод блочной сортировки
История из жизни. Адвокат Скиена
Двоичный поиск и связанные с ним алгоритмы
Метод "разделяй и властвуй"
Упражнения
Обход графов
Разновидности графов
Структуры данных для графов
История из жизни. Жертва закона Мура
История из жизни. Создание графа
Обход графа
Обход в ширину
Применение обхода в ширину
Обход в глубину
Применение обхода в глубину
Обход в глубину ориентированных графов
Упражнения
Алгоритмы для работы со взвешенными графами
Минимальные остовные деревья
История из жизни. И все на свете только сети
Поиск кратчайшего пути
История из жизни. Печатаем с помощью номеронабирателя
Потоки в сетях и паросочетание в двудольных графах
Разрабатывайте не алгоритмы, а графы
Упражнения
Комбинаторный поиск и эвристические методы
Перебор с возвратом
Отсечение вариантов поиска
Судоку
История из жизни. Покрытие шахматной доски
Эвристические методы перебора
История из жизни. Только это не радио
История из жизни. Отжиг массивов
Другие эвристические методы поиска
Параллельные алгоритмы
История из жизни. "Торопиться в никуда"
Упражнения
Динамическое программирование
Кэширование и вычисления
Поиск приблизительно совпадающих строк
Самая длинная возрастающая последовательность
История из жизни. Эволюция омара
Задача разбиения
Синтаксический разбор
Ограничения динамического программирования. Задача коммивояжера
История из жизни. Динамическое программирование и язык Prolog
История из жизни. Сжатие текста для штрих-кодов
Упражнения
Трудно решаемые задачи и аппроксимирующие алгоритмы
Сведение задач
Сведение для создания новых алгоритмов
Простые примеры сведения сложных задач
Задача выполнимости булевых формул
Нестандартные сведения
Искусство доказательства сложности
История из жизни. Наперегонки со временем
История из жизни. Полный провал
Сравнение классов сложности Р и NP
Решение NP-полных задач
Упражнения
Как разрабатывать алгоритмы
Каталог алгоритмических задач
Описание каталога
Структуры данных
Словарь
Очереди с приоритетами
Суффиксные деревья и массивы
Графы
Множества
Kd-деревья
Численные задачи
Решение системы линейных уравнений
Уменьшение ширины ленты матрицы
Умножение матриц
Определители и перманенты
Условная и безусловная оптимизация
Линейное программирование
Генерирование случайных чисел
Разложение на множители и проверка чисел на простоту
Арифметика произвольной точности
Задача о рюкзаке
Дискретное преобразование Фурье
Комбинаторные задачи
Сортировка
Поиск
Поиск медианы и выбор элементов
Генерирование перестановок
Генерирование подмножеств
Генерирование разбиений
Генерирование графов
Календарные вычисления
Календарное планирование
Выполнимость
Задачи на графах с полиномиальным временем исполнения
Компоненты связности
Топологическая сортировка
Минимальные остовные деревья
Поиск кратчайшего пути
Транзитивное замыкание и транзитивная редукция
Паросочетание
Задача поиска эйлерова цикла и задача китайского почтальона
Реберная и вершинная связность
Потоки в сети
Рисование графов
Рисование деревьев
Планарность
Сложные задачи на графах
Задача о клике
Независимое множество
Вершинное покрытие
Задача коммивояжера
Гамильтонов цикл
Разбиение графов
Вершинная раскраска
Реберная раскраска
Изоморфизм графов
Дерево Штейнера
Разрывающее множество ребер или вершин
Вычислительная геометрия
Элементарные задачи вычислительной геометрии
Выпуклая оболочка
Триангуляция
Диаграммы Вороного
Поиск ближайшей точки
Поиск в области
Местоположение точки
Выявление пересечений
Разложение по контейнерам
Преобразование к срединной оси
Разбиение многоугольника на части
Упрощение многоугольников
Выявление сходства фигур
Планирование перемещений
Конфигурации прямых
Сумма Минковского
Множества и строки
Поиск покрытия множества
Задача укладки множества
Сравнение строк
Нечеткое сравнение строк
Сжатие текста
Криптография
Минимизация конечного автомата
Максимальная общая подстрока
Поиск минимальной общей подстроки
Ресурсы
Программные системы
Источники данных
Библиографические ресурсы
Профессиональные консалтинговые услуги
Список литературы
Предметный указатель
Перевод с английского. Учебное пособие — Издательский дом "Вильямс", 2000. — 384 с. ISBN 5-8459-0122-7 (рус.) ISBN 0-201-00023-7 (англ.) В этой книге подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Показаны разнообразные реализации абстрактных типов данных, начиная от стандартных списков, стеков.
Пер. с англ. Б. И. Копылова. – М. Лаборатория базовых знаний, 2002. – 832 с. В книге излагаются методы анализа и синтеза современных систем автоматического управления (САУ). Показано, как с использованием принципа обратной связи могут быть созданы высокоэффективные системы управления различного назначения (аэрокосмическая техника, промышленные работы, автомобилестроение.
Пер. с англ. — М. Издательский дом "Вильямс", 2006. — 576 с. ил. — ISBN: 5-8459-0987-2 Эта книга, автором которой является преподаватель информатики, представляет собой один из лучших учебников, посвященных алгоритмам. Делая основной упор на понимание идей, а не на механическое рассмотрение работы того или иного алгоритма, автор излагает принципы разработки алгоритмов так.
2-е изд. — М. Вильямс, 2007. — 1410 с. — ISBN 5-8459-0887-2, 0-13-790395-2, 978-5-8459-0887-2. В книге представлены все современные достижения и изложены идеи, которые были сформулированы в исследованиях, проводившихся в течение последних пятидесяти лет, а также собраны на протяжении двух тысячелетий в областях знаний, ставших стимулом к развитию искусственного интеллекта как.
СПб. БХВ-Петербург,2011. – 720 с. Второе издание популярного бестселлера "Алгоритмы. Руководство по разработке" раскрывает тайны проектирования алгоритмов, анализа их действенности и эффективности. Развивая успешную концепцию первого издания, книга является отличным практическим руководством по разработке эффективных алгоритмов, содержит практические упражнения и готовые решения.
2-е изд. испр. Пер. с англ. – М. ООО «И. Д. Вильямс», 2006. – 1104 с. В книге рассматриваются основные парадигмы искусственных нейронных сетей. Представленный материал содержит строгое математическое обоснование всех нейросетевых парадигм, иллюстрируется примерами, описанием компьютерных экспериментов, содержит множество практических задач, а также обширную библиографию. В.
Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации. Приведены многочисленные примеры задач. Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей.
Введение в разработку алгоритмовЧто такое алгоритм? Это процедура выполнения определенной задачи. Алгоритм является основополагающей идеей любой компьютерной программы.
Чтобы представлять интерес, алгоритм должен решать общую, корректно поставленную задачу. Определение задачи, решаемой с помощью алгорйтма, дается описанием всего множества экземпляров, которые должен обработать алгоритм, и выхода, т. е. результата, получаемого после обработки одного из этих экземпляров. Описание одного из экземпляров задачи может заметно отличаться от формулировки общей задачи. Например, постановка задача сортировки делается таким образом:
Алгоритм — это процедура, которая принимает любой из возможных входных экземпляров и преобразует его в соответствии с требованиями, указанными в условии задачи. Для решения задачи сортировки существует много разных алгоритмов. В качестве примера одного из таких алгоритмов можно привести метод сортировки вставками. Сортировка этим методом заключается во вставке в требуемом порядке элементов из неотсортированной части списка в отсортированную часть, первоначально содержащую один элемент. Реализация этого алгоритма на языке С представлена в листинге 1.1.
Обратите внимание на универсальность этого алгоритма. Его можно применять как для сортировки слов, так и для сортировки чисел, используя соответствующую операцию сравнения для определения, какое из двух значений поставить первым. Можно с легкостью убедиться, что этот алгоритм правильно сортирует любой возможный набор входных величин в соответствии с нашим определением задачи сортировки.
Хороший алгоритм должен обладать тремя свойствами: быть корректным, эффективным и легкореализуемым. Получение комбинации всех трех свойств сразу может оказаться недостижимой задачей. В производственной обстановке любая программа, которая предоставляет достаточно хорошие результаты и не замедляет работу системы, в большинстве случаев является приемлемой, незавиримо от того, возможны ли улучшения этих показателей. В этой области вопрос получения самых лучших возможных результатов или достижения максимальной эффективности обычно возникает только в случае серьезных проблем с производительностью или с законом.
В этой главе основное внимание уделяется вопросу корректности алгоритмов, а их эффективность рассматривается в главе 2. Способность определенного алгоритма правильно решить поставленную задачу, т. е. его корректность, редко поддается очевидной оценке. Алгоритмы обычно сопровождаются доказательством их правильности в виде объяснения, почему для каждого экземпляра задачи будет выдан требуемый результат. Но прежде чем продолжить обсуждение темы, мы продемонстрируем, что аргумент “это очевидно” никогда не является достаточным доказательством правильности алгоритма.
Оптимизация маршрута роботаРассмотрим задачу, которая часто возникает на производстве и транспорте. Допустим, что нам нужно запрограммировать роботизированный манипулятор, который применяется для припаивания контактов интегральной схемы к контактным площадкам на печатной плате. Чтобы запрограммировать манипулятор для выполнения этой задачи, сначала нужно установить порядок, в котором манипулятор припаивает первый контакт, потом второй, третий и т. д. пока не будут припаяны все. После обработки последнего контакта манипулятор возвращается к исходной позиции первого контакта для обработки следующей платы. Таким образом, маршрут манипулятора является замкнутым маршрутом, или циклом.
Так как роботы являются дорогостоящими устройствами, мы хотим минимизировать время, затрачиваемое манипулятором на обработку платы. Будет логичным предположить, что манипулятор перемещается с постоянной скоростью; соответственно, время перемещения от одной точки к другой прямо пропорционально расстоянию между точками. То есть, нам нужно найти алгоритмическое решение такой задачи:
Обоснование правильности алгоритмовБудем надеяться, что предшествующие примеры продемонстрировали вам всю сложность темы правильности алгоритмов. Правильные алгоритмы выделяются из общего числа с помощью специальных инструментов, главный из которых называется доказательством.
Адекватное математическое доказательство состоит из нескольких частей. Прежде всего, требуется ясная и четкая формулировка того, что вы пытаетесь доказать. Потом необходим набор предположений, которые всегда считаются верными и поэтому используются как часть доказательства. Далее, цепь умозаключений приводит нас от начальных предположений к конечному утверждению, которое мы пытаемся доказать. Наконец, небольшой черный квадрат ¦ в тексте указывает на конец доказательства.
В этой книге формальным доказательствам не уделяется большого внимания, т. к. правильное формальное доказательство привести очень трудно, а неправильное может вас сильно дезориентировать. На самом деле, доказательство является демонстрацией. Доказательства полезны только тогда, когда они простые и незамысловатые — ясные и лаконичные аргументы, объясняющие, почему алгоритм удовлетворяет требованию нетривиальной правильности.
Правильные алгоритмы требуют тщательного изложения и определенных усилий для доказательства как их правильности, так и того факта, что они не являются неправильными. В последующих разделах мы разработаем инструменты для достижения этих целей.
Представление алгоритмовЦепь логических умозаключений об алгоритме невозможно построить без тщательного описания последовательности шагов, которые необходимо выполнить. Для этой цели наиболее часто употребляются, по отдельности или в совокупности, три формы представления алгоритма: обычный язык, псевдокод и язык программирования. Самым загадочным из этих средств представления алгоритма является псевдокод; это средство лучше всего можно определить как язык программирования, который никогда не выдает сообщений о синтаксических ошибках. Все три способа являются полезными, т. к. существует естественное стремление к компромиссу между легкостью восприятия и точностью представления алгоритма. Наиболее простым для понимания “языком программирования” является обычный язык, но в то же время он наименее точен. С другой стороны, такие языки, как Java или C/C++, позволяют точно выразить алгоритм, но создавать и понимать алгоритмы на этих языках задача не из легких. В отношении сложности применения и понимания псевдокод представляет золотую середину между этими двумя крайностями.
Выбор самого лучшего способа представления алгоритма зависит от ваших предпочтений. Я, например, сначала описываю свои алгоритмические идеи на обычном языке, а затем перехожу на более формальный псевдокод наподобие языка программирования или даже на настоящий язык программирования для уточнения сложных деталей.
Не допускайте ошибку, которую часто делают мои студенты, — используют псевдокод, чтобы приукрасить плохо определенную идею и придать ей более формальный и солидный вид. При описании алгоритма следует стремиться к ясности. Например, алгоритм ExhaustiveScheduling (см. листинг 1.7) можно было бы выразить на обычном языке так, как показано в листинге 1.9.
Анализ алгоритмовАлгоритмы являются принципиально важным компонентом информатики, т. к. их изучение не требует использования языка программирования или компьютера. Это означает необходимость в методах, позволяющих сравнивать эффективность алгоритмов, не прибегая к их реализации. Самыми значимыми из этих инструментов являются модель вычислений RAM и асимптотический анализ сложности наихудших случаев.
Для оценки производительности алгоритмов применяется асимптотическая нотация. Хотя практик может прийти в ужас от самой идеи теоретического анализа алгоритмов, этот материал представлен здесь в силу его исключительной ценности при работе с алгоритмами.
Этот способ оценки производительности является наиболее трудным материалом в данной книге. Но когда вы поймете основу этих идей на интуитивном уровне, вам будет намного легче разобраться в формальной составляющей.
Модель вычислений RAMРазработка машинно-независимых алгоритмов основывается на гипотетическом компьютере, называющемся машиной с произвольным доступом к памяти (Random Access Machine) или RAM-машиной. Согласно этой модели наш компьютер работает таким образом:
Время исполнения алгоритма в RAM-модели вычисляется по общему количеству ‘шагов, требуемых алгоритму для решения данного экземпляра задачи. Допуская, что наша RAM-машина исполняет определенное количество шагов/операций за секунду, количество шагов легко перевести в единицы времени.
Может показаться, что RAM-модель является слишком упрощенным представлением работы компьютеров. В конце концов, на большинстве процессоров умножение двух чисел занимает больше времени, чем сложение, что не вписывается в первое предположение модели. Второе предположение может быть нарушено удачной оптимизацией цикла компилятором или гиперпотоковыми возможностями процессора. Наконец, время обращения к данным может значительно разниться в зависимости от расположения данных: в кэше, в оперативной памяти или на диске. Таким образом, по сравнению с настоящим компьютером, все три основные допущения для RAM-машины неверны.
Тем не менее, несмотря на эти несоответствия настоящему компьютеру, RAM-модель является превосходной моделью для понимания того, как алгоритм будет работать на настоящем компьютере. Она обеспечивает хороший компромисс, отражая поведение компьютеров и одновременно являясь простой в использовании. Эти характеристики делают RAM-модель полезной для практического применения.
Любая модель полезна лишь в определенных рамках. Возьмем, например, модель плоской Земли. Можно спорить, что это неправильная модель, т. к. еще древние греки знали, что в действительности Земля круглая. Но модель плоской Земли достаточно точна для закладки фундамента дома. Более того, в данном случае с моделью плоской Земли настолько удобнее работать, что использование модели сферической Земли для этой цели даже не приходит в голову.
Та же самая ситуация наблюдается и в случае с RAM-моделью вычислений — мы создаем, вообще говоря, очень полезную абстракцию. Довольно трудно создать алгоритм, для которого RAM-модель выдаст существенно неверные результаты. Устойчивость RAM-модели позволяет анализировать алгоритмы машинно-независимым способом.
Алгоритмы можно изучать и анализировать, не прибегая к использованию конкретного языка программирования или компьютерной платформы.
Структуры данныхЗамену структуры данных в медленно работающей программе сравнить с пересадкой органа. Такие важные классы абстрактных типов данных, как контейнеры, словари и очереди с приоритетами, могут реализовываться посредством разных, но функционально эквивалентных структур данных. Замена структуры данных одного типа структурой данных другого типа не влияет на правильность программы, т. к. предполагается, что одна правильная реализация заменяется другой правильной реализацией. Но в реализации другого типа данных могут применяться операции с иными временными отношениями, в результате чего общая производительность программы может значительно повыситься. Подобно ситуации с больным, нуждающимся в пересадке одного органа, для повышения производительности программы может оказаться достаточным заменить лишь один ее компонент.
Конечно, лучше с рождения иметь здоровое сердце, чем жить в ожидании донорского. То же самое справедливо и в случае со структурами данных. Наибольшую пользу от применения хороших структур данных можно получить, лишь заложив их использование в программу с самого начала. При написании этой книги предполагалось, что ее читатели уже имеют знания об элементарных структурах данных и манипуляциях указателями.
Но так как в сегодняшних курсах по структурам данных внимание фокусируется больше на абстракции данных и на объектно-ориентированном программировании, чем на деталях представления структур в памяти, то мы повторим этот материал здесь, чтобы убедиться в том, что вы его полностью понимаете.
Как и при изучении большинства предметов, при изучении структур данных важнее хорошо освоить основной материал, чем бегло ознакомиться с более сложными понятиями. Здесь мы обсудим три фундаментальных абстрактных типа данных, контейнеры, словари и очереди с приоритетами, и рассмотрим, как они реализуются посредством массивов и списков. Более сложные реализации структур данных рассматриваются в релевантной задаче в каталоге задач.
Сортировка и поискСтуденты, получающие специальность, связанную с вычислительными системами, изучают основные алгоритмы сортировки по крайней мере три раза: сначала во введении в программирование, затем в курсе по структурам данных и, наконец, в курсе разработки и анализа алгоритмов. Почему сортировке уделяется так много внимания? На то есть ряд причин.
В этой главе мы обсудим сортировку, уделяя особое внимание тому, как ее можно применить для решения других задач. Мы рассмотрим подробное описание нескольких фундаментальных алгоритмов, — пирамидальной сортировки (heapsort), сортировки слиянием (mergesort), быстрой сортировки (quicksort) и сортировки распределением (distribution sort),— представляющих собой примеры важных парадигм разработки алгоритмов. Задача сортировки также представлена в разделе 14.1.
Обход графовГрафы являются одной из важнейших областей теории вычислительных систем. Это абстрактное понятие, посредством которого можно описывать разнообразные реальные явления— организацию транспортных систем, человеческих взаимоотношений, сети передачи данных и т. п. Возможность формального моделирования такого множества разных реальных структур позволяет программисту решать широкий круг прикладных задач.
Более конкретно, граф G = (V9E) состоит из набора вершин Vw набора ребер Е, соединяющих пары вершин. С помощью графов можно представить практически любые взаимоотношения. Например, посредством графов можно создать модель сети дорог, представляя населенные пункты верщинами, а дороги между ними — соединяющими соответствующие вершины ребрами. С помощью графов можно также моделировать электронные схемы, представляя компоненты вершинами, а соединения компонентов — ребрами. Такие графы изображены на рис. 5.1.
…
Представление задачи в виде графа является ключевым подходом к решению многих алгоритмических задач. Теория графов предоставляет язык для описания свойств взаимоотношений, и просто поразительно, как часто запутанные прикладные задачи поддаются простому описанию и решению посредством применения свойств классических графов.
Разработка по-настоящему оригинальных алгоритмов графов является очень трудной задачей. Ключевым аспектом эффективного использования алгоритмов на графах является правильное моделирование задачи, чтобы можно было воспользоваться уже существующими алгоритмами. Знакомство с разными типами алгоритмических задач важнее знания деталей отдельных алгоритмов, особенно если учесть, что во второй части этой книги можно найти решение задачи по ее названию.
В этой главе рассматриваются основные структуры данных и операции обхода графов, которые можно будет использовать при поиске решений базовых задач на графах. В главе 6 рассматриваются более сложные алгоритмы для работы с графами: построение минимальных остовных деревьев (minimum spanning tree), кратчайшего пути и потоков в сети. При этом правильное моделирование задачи остается наиболее важным аспектом ее решения. Затратив время на ознакомление с задачами и их решениями во второй части этой книги, вы сэкономите много времени при решении реальных задач в будущем.
Динамическое программированиеНаиболее трудными алгоритмическими задачами являются задачи оптимизации, в которых требуется найти решение, максимизирующее или минимизирующее определенную функцию. Классическим примером задачи оптимизации является задача коммивояжера, в которой требуется найти маршрут с минимальной стоимостью для посещения всех вершин графа. Как мы видели в главе 7, для решения задачи коммивояжера можно легко предложить несколько алгоритмов, которые выдают кажущиеся удовлетворительными решения, но не всегда выдают маршрут с минимальной стоимостью.
Для алгоритмов задач оптимизации требуется доказательство, что они всегда возвращают наилучшее возможное решение. “Жадные” алгоритмы, которые принимают наилучшее локальное решение на каждом шаге, обычно эффективны, но не гарантируют глобальное оптимальное решение. Алгоритмы поиска методом исчерпывающего перебора всегда выдают оптимальный результат, но обычно временная сложность таких алгоритмов чрезмерно высока.
Динамическое программирование сочетает лучшие возможности обоих подходов. Этот метод предоставляет возможность разрабатывать алгоритмы специального назначения, которые систематически исследуют все возможности (таким образом гарантируя правильность решения) и в то же самое время сохраняют ранее полученные промежуточные результаты (таким образом обеспечивая эффективность работы). Сохранение последствий всех возможных решений и систематическое использование этой информации минимизируют общий объем работы.
Если вы понимаете суть динамического программирования, эта технология разработки алгоритмов, возможно, является для вас самой удобной для практического применения. Я считаю, что алгоритмы динамического программирования часто легче разработать заново, чем искать их готовую реализацию в какой-либо книге. Однако, пока вы не понимаете динамическое программирование, оно кажется вам каким-то шаманством.
Динамическое программирование— это технология для эффективной реализации рекурсивных алгоритмов посредством сохранения промежуточных результатов. Секрет ее применения заключается в определении, выдает ли простой рекурсивный алгоритм одинаковые результаты для одинаковых подзадач. Если выдает, то вместо повторения вычислений ответ каждой подзадачи можно сохранять в таблице для использования в дальнейшем, что дает возможность получить Эффективный алгоритм. Начинаем разработку с определения и отладки рекурсивного алгоритма. Только добившись правильной работы нашего рекурсивного алгоритма, мы переходим к поиску мер по ускорению его работы, сохраняя результаты в матрице.
Динамическое программирование обычно является подходящим методом решения задач оптимизации в случае комбинаторных объектов, которые имеют естественный порядок организации компонентов слева направо. К таким объектам относятся строки символов, корневые деревья, многоугольники, а также последовательности целых чисел. Изучение динамического программирования лучше всего начинать с исследования готовых примеров. Для демонстрации практической пользы от динамического программирования в этой главе приводится несколько историй из жизни, в которых оно сыграло решающую роль в решении поставленной задачи.
Post navigation
