Algorithms Illuminated. Part 2: Graph Algorithms and Data Structures / Совершенный алгоритм. Графовые алгоритмы и структуры данных
Год издания: 2019
Автор: Tim Roughgarden / Тим Рафгарден
Переводчик: Логунов А.
Издательство: Питер
ISBN: 978-5-4461-1272-2
Серия: Библиотека программиста
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Интерактивное оглавление: Да
Количество страниц: 256
Описание:
Перед вами вторая книга серии из четырех частей, изданная на основе проводимых мною с 2012 года онлайн-курсов по алгоритмам. Эти курсы, в свою очередь, появились благодаря лекциям для студентов, которые я читал в Стэнфордском университете в течение долгих лет. Первая книга - «Совершенный алгоритм. Основы» - не является обязательным условием для второй части, она самостоятельна и будет доступна любому читателю, кто имеет подготовку.
Вторая часть книги «Совершенный алгоритм» - это вводный курс в основы грамотности по следующим трем темам.
Графовый поиск и приложения. Графы моделируют ряд разных типов сетей, включая дорожные, коммуникационные, социальные сети и сети зависимостей между задачами. Графы могут быть сложными, однако существует несколько невероятно быстрых примитивов для рассуждения о структуре графа. Мы начнем с линейно-временных алгоритмов графового поиска, с приложений в диапазоне от сетевого анализа до построения последовательности выполнения операций.
Кратчайшие пути. В задаче о кратчайшем пути цель состоит в том, чтобы вычислить наилучший маршрут в сети из точки А в точку В. Данная задача имеет очевидные применения, такие как вычисление маршрутов движения, а также встречается в замаскированном виде во многих других универсальных задачах. Мы обобщим один из наших алгоритмов графового поиска и придем к знаменитому алгоритму поиска кратчайшего пути Дейкстры.
Структуры данных. Эта книга сделает вас высокообразованным пользователем нескольких разных структур данных, предназначенных для поддержания эволюционирующего множества объектов с ассоциированными с ними ключами. Основная цель состоит в развитии интуиции о том, какая структура данных является правильной для вашего приложения. Дополнительные разделы содержат рекомендации по реализации этих структур данных с нуля.
Сначала мы обсудим кучи, которые могут быстро идентифицировать хранимый объект с наименьшим ключом, а также полезны для сортировки, реализации очереди с приоритетом и реализации почти линейно-временного алгоритма Дейкстры. Деревья поиска сохраняют полную упорядоченность ключей хранимых объектов и поддерживают еще более широкий спектр операций. Хеш-таблицы оптимизированы для сверхбыстрых операций поиска и широко распространены в современных программах. Мы также рассмотрим фильтр Блума, близкого родственника хеш-таблицы, который использует
меньше пространства за счет случайных ошибок.
Темы, затронутые в трех других томах. Первая часть книги «Совершенный алгоритм. Основы» охватывает асимптотические обозначения (форму записи О-большое и ее близких родственников), алгоритмы «разделяй и властвуй» и основную теорему о рекуррентных соотношениях - основной метод, рандомизированную быструю сортировку и ее анализ, а также линейно-временные алгоритмы отбора. В третьей части речь идет о жадных алгоритмах (планирование, минимальные остовные деревья, кластеризация, коды Хаффмана) и динамическом программировании (задача о рюкзаке, выравнивание после
довательности, кратчайшие пути, оптимальные деревья поиска). Четвертая часть посвящена NР-полноте, тому, что она означает для проектировщика алгоритмов, и стратегиям решения вычислительно неразрешимых задач, включая эвристический анализ и локальный поиск.
dumpz.ws
Год издания: 2019
Автор: Tim Roughgarden / Тим Рафгарден
Переводчик: Логунов А.
Издательство: Питер
ISBN: 978-5-4461-1272-2
Серия: Библиотека программиста
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Интерактивное оглавление: Да
Количество страниц: 256
Описание:
Перед вами вторая книга серии из четырех частей, изданная на основе проводимых мною с 2012 года онлайн-курсов по алгоритмам. Эти курсы, в свою очередь, появились благодаря лекциям для студентов, которые я читал в Стэнфордском университете в течение долгих лет. Первая книга - «Совершенный алгоритм. Основы» - не является обязательным условием для второй части, она самостоятельна и будет доступна любому читателю, кто имеет подготовку.
Вторая часть книги «Совершенный алгоритм» - это вводный курс в основы грамотности по следующим трем темам.
Графовый поиск и приложения. Графы моделируют ряд разных типов сетей, включая дорожные, коммуникационные, социальные сети и сети зависимостей между задачами. Графы могут быть сложными, однако существует несколько невероятно быстрых примитивов для рассуждения о структуре графа. Мы начнем с линейно-временных алгоритмов графового поиска, с приложений в диапазоне от сетевого анализа до построения последовательности выполнения операций.
Кратчайшие пути. В задаче о кратчайшем пути цель состоит в том, чтобы вычислить наилучший маршрут в сети из точки А в точку В. Данная задача имеет очевидные применения, такие как вычисление маршрутов движения, а также встречается в замаскированном виде во многих других универсальных задачах. Мы обобщим один из наших алгоритмов графового поиска и придем к знаменитому алгоритму поиска кратчайшего пути Дейкстры.
Структуры данных. Эта книга сделает вас высокообразованным пользователем нескольких разных структур данных, предназначенных для поддержания эволюционирующего множества объектов с ассоциированными с ними ключами. Основная цель состоит в развитии интуиции о том, какая структура данных является правильной для вашего приложения. Дополнительные разделы содержат рекомендации по реализации этих структур данных с нуля.
Сначала мы обсудим кучи, которые могут быстро идентифицировать хранимый объект с наименьшим ключом, а также полезны для сортировки, реализации очереди с приоритетом и реализации почти линейно-временного алгоритма Дейкстры. Деревья поиска сохраняют полную упорядоченность ключей хранимых объектов и поддерживают еще более широкий спектр операций. Хеш-таблицы оптимизированы для сверхбыстрых операций поиска и широко распространены в современных программах. Мы также рассмотрим фильтр Блума, близкого родственника хеш-таблицы, который использует
меньше пространства за счет случайных ошибок.
Темы, затронутые в трех других томах. Первая часть книги «Совершенный алгоритм. Основы» охватывает асимптотические обозначения (форму записи О-большое и ее близких родственников), алгоритмы «разделяй и властвуй» и основную теорему о рекуррентных соотношениях - основной метод, рандомизированную быструю сортировку и ее анализ, а также линейно-временные алгоритмы отбора. В третьей части речь идет о жадных алгоритмах (планирование, минимальные остовные деревья, кластеризация, коды Хаффмана) и динамическом программировании (задача о рюкзаке, выравнивание после
довательности, кратчайшие пути, оптимальные деревья поиска). Четвертая часть посвящена NР-полноте, тому, что она означает для проектировщика алгоритмов, и стратегиям решения вычислительно неразрешимых задач, включая эвристический анализ и локальный поиск.
Скрытое содержимое могут видеть только пользователи групп(ы): Premium, Местный, Свои
