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

lgli/Алгоритмы.Руководство по разработке.3-е изд.Скиена.2022.pdf

lgrsnf/Алгоритмы.Руководство по разработке.3-е изд.Скиена.2022.pdf

zlib/no-category/Стивен Скиена/Алгоритмы. Руководство по разработке_25442142.pdf

The Algorithm Design Manual (Texts in Computer Science)

Skiena, Steven S.

Steven S. Skiena

Springer International Publishing AG

Springer Nature Switzerland AG

BXV-Peterburg

Texts in computer science, Third edition, Cham, Switzerland, 2020

Springer Nature (Textbooks & Major Reference Works), Cham, 2020

Russia, Russian Federation

Switzerland, Switzerland

Oct 06, 2020

{"edition":"3","isbns":["3030542556","5977567995","9783030542559","9785977567992"],"last_page":848,"publisher":"БХВ-Петербург"}

Source title: The Algorithm Design Manual (Texts in Computer Science)

Оглавление
Предисловие
ЧАСТЬ I. Практическая разработка алгоритмов
Глава 1. Введение в разработку алгоритмов
1.1. Оптимизация маршрута робота
1.2. Задача календарного планирования
1.3. Обоснование правильности алгоритмов
1.4. Моделирование задачи
1.5. Доказательство от противного
1.6. Истории из жизни
1.7. История из жизни. Моделирование проблемы ясновидения
1.8. Прикидка
Замечания к главе
1.9. Упражнения
Глава 2. Анализ алгоритмов
2.1. Модель вычислений RAM
2.2. Асимптотические («Big Oh») обозначения
2.3. Скорость роста и отношения доминирования
2.4. Работа с асимптотическими обозначениями
2.5. Оценка эффективности
2.6. Суммирование
2.7. Логарифмы и их применение
2.8. Свойства логарифмов
2.9. История из жизни. Загадка пирамид
2.10. Анализ высшего уровня (*)
Замечания к главе
2.11. Упражнения
Глава 3. Структуры данных
3.1. Смежные и связные структуры данных
3.2. Стеки и очереди
3.3. Словари
3.4. Двоичные деревья поиска
3.5. Очереди с приоритетами
3.6. История из жизни. Триангуляция
3.7. Хеширование
3.8. Специализированные структуры данных
3.9. История из жизни. Геном человека
Замечания к главе
3.10. Упражнения
Глава 4. Сортировка и поиск
4.1. Применение сортировки
4.2. Практические аспекты сортировки
4.3. Пирамидальная сортировка
4.4. История из жизни. Билет на самолет
4.5. Сортировка слиянием. Метод «разделяй и властвуй»
4.6. Быстрая сортировка. Рандомизированная версия
4.7. Сортировка распределением. Метод блочной сортировки
4.8. История из жизни. Скиена в суде
Замечания к главе
4.9. Упражнения
Глава 5. Метод «разделяй и властвуй»
5.1 . Двоичный поиск и связанные с ним алгоритмы
5.2. История из жизни. Поиск «бага в баге»
5.3. Рекуррентные соотношения
5.4. Решение рекуррентных соотношений типа «разделяй и властвуй» (*)
5.5. Быстрое умножение
5.6. Поиск наибольшего поддиапазона и ближайшей пары
5.7. Параллельные алгоритмы
5.8. История из жизни. «Торопиться в никуда»
5.9. Свертка (*)
Замечания к главе
5.10. Упражнения
Глава 6. Хеширование и рандомизированные алгоритмы
6.1. Обзор теории вероятностей
6.2. Задача мячиков и контейнеров
6.3. Почему хеширование является рандомизированным алгоритмом?
6.4. Фильтры Блума
6.5. Парадокс дня рождения и идеальное хеширование
6.6. Метод минимальных хеш-кодов
6.7. Эффективный поиск подстроки в строке
6.8. Тестирование чисел на простоту
6.9. История из жизни. Как я дал Кнуту свой средний инициал
6.10. Откуда берутся случайные числа?
Замечания к главе
6.11. Упражнения
Глава 7. Обход графов
7.1. Разновидности графов
7.2. Структуры данных для графов
7.3. История из жизни. Жертва закона Мура
7.4. История из жизни. Создание графа
7.5. Обход графа
7.6. Обход в ширину
7.7. Применение обхода в ширину
7.8. Обход в глубину
7.9. Применение обхода в глубину
7.10. Обход в глубину ориентированных графов
Замечания к главе
7.11. Упражнения
Глава 8. Алгоритмы для работы со взвешенными графами
8.1. Минимальные остовные деревья
8.2. История из жизни. И всё на свете — только сети
8.3. Поиск кратчайшего пути
8.4. История из жизни. Печатаем с помощью номеронабирателя
8.5. Потоки в сетях и паросочетание в двудольных графах
8.6. Произвольный минимальный разрез
Замечания к главе
8.8. Упражнения
Глава 9. Комбинаторный поиск
9.1. Перебор с возвратом
9.2. Примеры перебора с возвратом
9.3. Отсечение вариантов поиска
9.4. Судоку
9.5. История из жизни. Покрытие шахматной доски
9.6. Поиск методом «лучший-первый»
9.7. Эвристический алгоритм А*
Замечания к главе
9.8. Упражнения
Глава 10. Динамическое программирование
10.1. Кэширование и вычисления
10.2. Поиск приблизительно совпадающих строк
10.3. Самая длинная возрастающая подпоследовательность
10.4. История из жизни. Сжатие текста для штрихкодов
10.5. Неупорядоченное разбиение или сумма подмножества
10.6. История из жизни: Баланс мощностей
10.7. Задача упорядоченного разбиения
10.8. Синтаксический разбор
10.9. Ограничения динамического программирования: задача коммивояжера
10.10. История из жизни. Динамическое программирование и язык Prolog
Замечания к главе
10.11. Упражнения
Глава 11. NP-полнота
11.1. Сведение задач
11.2. Сведение для создания новых алгоритмов
11.3. Простые примеры сведения сложных задач
11.4. Задача выполнимости булевых формул
11.5. Нестандартные сведения задачи SAT
11.6. Искусство доказательства сложности
11.7. История из жизни. Наперегонки со временем
11.8. История из жизни. Полный провал
11.9. Сравнение классов сложности Р и NP
Замечания к главе
11.10. Упражнения
Глава 12. Решение сложных задач
12.1. Аппроксимирующие алгоритмы
12.2. Аппроксимация вершинного покрытия
12.3. Задача коммивояжера в евклидовом пространстве
12.5. Задача о покрытии множества
12.6. Эвристические методы поиска
12.7. История из жизни. Только это не радио
12.8. История из жизни. Отжиг массивов
12.9. Генетические алгоритмы и другие эвристические методы поиска
12.10. Квантовые вычисления
Замечания к главе
12.11. Упражнения
Глава 13. Как разрабатывать алгоритмы?
13.1. Список вопросов для разработчика алгоритмов
13.2. Подготовка к собеседованию в технологических компаниях
ЧАСТЬ II. КАТАЛОГ АЛГОРИТМИЧЕСКИХ ЗАДАЧ
Глава 14. Описание каталога
14.1. Предостережения
Глава 15. Структуры данных
15.1. Словари
15.2. Очереди с приоритетами
15.3. Суффиксные деревья и массивы
15.4. Графы
15.5. Множества
15.6. Кd-деревья
Глава 16. Численные задачи
16.1. Решение системы линейных уравнений
16.2. Уменьшение ширины ленты матрицы
16.3. Умножение матриц
16.4. Определители и перманенты
16.5. Условная и безусловная оптимизация
16.6. Линейное программирование
16.7. Генерирование случайных чисел
16.8. Разложение на множители и проверка чисел на простоту
16.9. Арифметика произвольной точности
16.10. Задача о рюкзаке
16.11. Дискретное преобразование Фурье
Глава 17. Комбинаторные задачи
17.1. Сортировка
17.2. Поиск
17.3. Поиск медианы и выбор элементов
17.4. Генерирование перестановок
17.5. Генерирование подмножеств
17.6. Генерирование разбиений
17.7. Генерирование графов
17.8. Календарные вычисления
17.9. Календарное планирование
17.10. Выполнимость
Глава 18. Задачи на графах c полиномиальным временем исполнения
18.1. Компоненты связности
18.2. Топологическая сортировка
18.3. Минимальные остовные деревья
18.4. Поиск кратчайшего пути
18.5. Транзитивное замыкание и транзитивная редукция
18.6. Паросочетание
18.7. Задача поиска эйлерова цикла и задача китайского почтальона
18.8. Реберная и вершинная связность
18.9. Потоки в сети
18.10. Рисование графов
18.11. Рисование деревьев
18.12. Планарность
Глава 19. NР-сложные задачи на графах
19.1. Задача о клике
19.2. Независимое множество
19.3. Вершинное покрытие
19.4. Задача коммивояжера
19.5. Гамильтонов цикл
19.6. Разбиение графов
19.7. Вершинная раскраска
19.8. Реберная раскраска
19.9. Изоморфизм графов
19.10. Дерево Штейнера
19.11. Разрывающее множество ребер или вершин
Глава 20. Вычислительная геометрия
20.1. Элементарные задачи вычислительной геометрии
20.2. Выпуклая оболочка
20.3. Триангуляция
20.4. Диаграммы Вороного
20.5. Поиск ближайшей точки
20.6. Поиск в области
20.7. Местоположение точки
20.8. Выявление пересечений
20.9. Разложение по контейнерам
20.10. Преобразование к срединной оси
20.11. Разбиение многоугольника на части
20.12. Упрощение многоугольников
20.13. Выявление сходства фигур
20.14. Планирование перемещений
20.15. Конфигурации прямых
20.16. Сумма Минковского
Глава 21. Множества и строки
21.1. Поиск покрытия множества
21.2. Задача укладки множества
21.3. Сравнение строк
21.4. Нечеткое сравнение строк
21.5. Сжатие текста
21.6. Криптография
21.7. Минимизация конечного автомата
21.8. Максимальная общая подстрока
21.9. Поиск минимальной общей надстроки
Глава 22. Ресурсы
22.1. Программные системы
22.2. Источники данных
22.4. Профессиональные консалтинговые услуги
Глава 23. Список литературы
Приложение. Описание электронного архива
Предметный указатель

My Absolute Favorite For This Kind Of Interview Preparation Is Steven Skiena’s The Algorithm Design Manual. More Than Any Other Book It Helped Me Understand Just How Astonishingly Commonplace ... Graph Problems Are -- They Should Be Part Of Every Working Programmer’s Toolkit. The Book Also Covers Basic Data Structures And Sorting Algorithms, Which Is A Nice Bonus. ... Every 1 – Pager Has A Simple Picture, Making It Easy To Remember. This Is A Great Way To Learn How To Identify Hundreds Of Problem Types. (steve Yegge, Get That Job At Google) Steven Skiena’s Algorithm Design Manual Retains Its Title As The Best And Most Comprehensive Practical Algorithm Guide To Help Identify And Solve Problems. ... Every Programmer Should Read This Book, And Anyone Working In The Field Should Keep It Close To Hand. ... This Is The Best Investment ... A Programmer Or Aspiring Programmer Can Make. (harold Thimbleby, Times Higher Education) It Is Wonderful To Open To A Random Spot And Discover An Interesting Algorithm. This Is The Only Textbook I Felt Compelled To Bring With Me Out Of My Student Days.... The Color Really Adds A Lot Of Energy To The New Edition Of The Book! (cory Bart, University Of Delaware) The Is The Most Approachable Book On Algorithms I Have. (megan Squire, Elon University) --- This Newly Expanded And Updated Third Edition Of The Best-selling Classic Continues To Take The Mystery Out Of Designing Algorithms, And Analyzing Their Efficiency. It Serves As The Primary Textbook Of Choice For Algorithm Design Courses And Interview Self-study, While Maintaining Its Status As The Premier Practical Reference Guide To Algorithms For Programmers, Researchers, And Students. The Reader-friendly Algorithm Design Manual Provides Straightforward Access To Combinatorial Algorithms Technology, Stressing Design Over Analysis. The First Part, Practical Algorithm Design, Provides Accessible Instruction On Methods For Designing And Analyzing Computer Algorithms. The Second Part, The Hitchhiker's Guide To Algorithms, Is Intended For Browsing And Reference, And Comprises The Catalog Of Algorithmic Resources, Implementations, And An Extensive Bibliography. New To The Third Edition: -- New And Expanded Coverage Of Randomized Algorithms, Hashing, Divide And Conquer, Approximation Algorithms, And Quantum Computing -- Provides Full Online Support For Lecturers, Including An Improved Website Component With Lecture Slides And Videos -- Full Color Illustrations And Code Instantly Clarify Difficult Concepts -- Includes Several New War Stories Relating Experiences From Real-world Applications -- Over 100 New Problems, Including Programming-challenge Problems From Leetcode And Hackerrank. -- Provides Up-to-date Links Leading To The Best Implementations Available In C, C++, And Java Additional Learning Tools: -- Contains A Unique Catalog Identifying The 75 Algorithmic Problems That Arise Most Often In Practice, Leading The Reader Down The Right Path To Solve Them -- Exercises Include Job Interview Problems From Major Software Companies -- Highlighted Take Home Lessons Emphasize Essential Concepts -- The No Theorem-proof Style Provides A Uniquely Accessible And Intuitive Approach To A Challenging Subject -- Many Algorithms Are Presented With Actual Code (written In C) -- Provides Comprehensive References To Both Survey Articles And The Primary Literature Written By A Well-known Algorithms Researcher Who Received The Ieee Computer Science And Engineering Teaching Award, This Substantially Enhanced Third Edition Of The Algorithm Design Manual Is An Essential Learning Tool For Students And Professionals Needed A Solid Grounding In Algorithms. Professor Skiena Is Also The Author Of The Popular Springer Texts, The Data Science Design Manual And Programming Challenges: The Programming Contest Training Manual.

Texts in Computer Science
Erscheinungsdatum: 06.10.2020

2023-07-21