Основы современных алгоритмов
Дж. Макконел
В учебном пособии обсуждаются алгоритмы решения наиболее широко распространенных классов задач, покрывающих практически всю область программирования: поиск и сортировка, численные алгоритмы и алгоритмы на графах. Особое внимание уделено алгоритмам параллельной обработки, редко освещаемым в литературе на русском языке.
В дополнении ко 2-му изданию на русском языке даны сведения по теории алгоритмов, оценкам трудоемкости и новейшим алгоритмам, не вошедшие в первоначальный вариант книги.
Изложение неформальное и чрезвычайно подробное, с большим количеством упражнений, позволяющих вести самоконтроль. Книга нужна всем, кому приходится самостоятельно писать программы - от программистов банковских систем до научных работников.
Москва, издательство «Техносфера», 2006 г.
ISBN 5-94836-005-9, 0-7637-1634-0 (англ).
Количество страниц: 368.
Содержание книги «Основы современных алгоритмов»:
- 9 Предисловие
- 12 1. Основы анализа алгоритмов
- 14 1.1. Что такое анализ?
- 19 1.1.1. Классы входных данных
- 20 1.1.2. Сложность по памяти
- 21 1.1.3. Упражнения
- 22 1.2. Что подсчитывать и что учитывать
- 25 1.2.1. Упражнения
- 26 1.3. Необходимые математические сведения
- 26 1.3.1. Логарифмы
- 27 1.3.2. Бинарные деревья
- 28 1.3.3. Вероятности
- 31 1.3.4. Упражнения
- 32 1.4. Скорости роста
- 34 1.4.1. Классификация скоростей роста
- 36 1.4.2. Упражнения
- 37 1.5. Алгоритмы вида «разделяй и властвуй»
- 41 1.5.1. Метод турниров
- 42 1.5.2. Нижние границы
- 44 1.5.3. Упражнения
- 45 1.6. Рекуррентные соотношения
- 50 1.6.1. Упражнения
- 51 1.7. Анализ программ
- 14 1.1. Что такое анализ?
- 53 2. Алгоритмы поиска и выборки
- 55 2.1. Последовательный поиск
- 56 2.1.1. Анализ наихудшего случая
- 56 2.1.2. Анализ среднего случая
- 58 2.1.3. Упражнения
- 59 2.2. Двоичный поиск
- 61 2.2.1. Анализ наихудшего случая
- 62 2.2.2. Анализ среднего случая
- 64 2.2.3. Упражнения
- 66 2.3. Выборка
- 68 2.3.1. Упражнения
- 69 2.4. Упражнение по программированию
- 55 2.1. Последовательный поиск
- 70 3. Алгоритмы сортировки
- 72 3.1. Сортировка вставками
- 73 3.1.1. Анализ наихудшего случая
- 74 3.1.2. Анализ среднего случая
- 76 3.1.3. Упражнения
- 77 3.2. Пузырьковая сортировка
- 78 3.2.1. Анализ наилучшего случая
- 78 3.2.2. Анализ наихудшего случая
- 79 3.2.3. Анализ среднего случая
- 81 3.2.4. Упражнения
- 82 3.3. Сортировка Шелла
- 84 3.3.1. Анализ алгоритма
- 86 3.3.2. Влияние шага на эффективность
- 87 3.3.3. Упражнения
- 87 3.4. Корневая сортировка
- 90 3.4.1. Анализ
- 91 3.4.2. Упражнения
- 92 3.5. Пирамидальная сортировка
- 95 3.5.1. Анализ наихудшего случая
- 97 3.5.2. Анализ среднего случая
- 98 3.5.3. Упражнения
- 98 3.6. Сортировка слиянием
- 101 3.6.1. Анализ алгоритма MergeLists
- 102 3.6.2. Анализ алгоритма MergeSort
- 104 3.6.3. Упражнения
- 105 3.7. Быстрая сортировка
- 107 3.7.1. Анализ наихудшего случая
- 108 3.7.2. Анализ среднего случая
- 111 3.7.3. Упражнения
- 112 3.8. Внешняя многофазная сортировка слиянием
- 116 3.8.1. Число сравнений при построении отрезков
- 116 3.8.2. Число сравнений при слиянии отрезков
- 117 3.8.3. Число операций чтения блоков
- 118 3.8.4. Упражнения
- 118 3.9. Дополнительные упражнения
- 120 3.10. Упражнения по программированию
- 72 3.1. Сортировка вставками
- 123 4. Численные алгоритмы
- 125 4.1. Вычисление значений многочленов
- 126 4.1.1. Схема Горнера
- 127 4.1.2. Предварительная обработка коэффициентов
- 129 4.1.3. Упражнения
- 130 4.2. Умножение матриц
- 131 4.2.1. Умножение матриц по Винограду
- 133 4.2.2. Умножение матриц по Штрассену
- 135 4.2.3. Упражнения
- 135 4.3. Решение линейных уравнений
- 136 4.3.1. Метод Гаусса-Жордана
- 138 4.3.2. Упражнения
- 125 4.1. Вычисление значений многочленов
- 139 5. Алгоритмы сравнения с образцом
- 140 5.1. Сравнение строк
- 143 5.1.1. Конечные автоматы
- 143 5.1.2. Алгоритм Кнута Морриса-Пратта
- 147 5.1.3. Алгоритм Бойера-Мура
- 154 5.1.4. Упражнения
- 155 5.2. Приблизительное сравнение строк
- 157 5.2.1. Анализ
- 157 5.2.2. Упражнения
- 158 5.3. Упражнения по программированию
- 140 5.1. Сравнение строк
- 159 6. Алгоритмы на графах
- 162 6.1. Основные понятия теории графов
- 163 6.1.1. Терминология
- 164 6.1.2. Упражнения
- 165 6.2. Структуры данных для представления графов
- 166 6.2.1. Матрица примыканий
- 167 6.2.2. Список примыканий
- 168 6.2.3. Упражнения
- 169 6.3. Алгоритмы обхода в глубину и по уровням
- 170 6.3.1. Обход в глубину
- 171 6.3.2. Обход по уровням
- 172 6.3.3. Анализ алгоритмов обхода
- 173 6.3.4. Упражнения
- 175 6.4. Алгоритм поиска минимального остовного дерева
- 175 6.4.1. Алгоритм Дейкстры-Прима
- 179 6.4.2. Алгоритм Крускала
- 182 6.4.3. Упражнения
- 183 6.5. Алгоритм поиска кратчайшего пути
- 184 6.5.1. Алгоритм Дейкстры
- 187 6.5.2. Упражнения
- 189 6.6. Алгоритм определения компонент двусвязности
- 191 6.6.1. Упражнения
- 192 6.7. Разбиения множеств
- 195 6.8. Упражнения по программированию
- 162 6.1. Основные понятия теории графов
- 197 7. Параллельные алгоритмы
- 199 7.1. Введение в параллелизм
- 199 7.1.1. Категории компьютерных систем
- 201 7.1.2. Параллельные архитектуры
- 203 7.1.3. Принципы анализа параллельных алгоритмов
- 203 7.1.4. Упражнения
- 204 7.2. Модель PRAM
- 206 7.2.1. Упражнения
- 206 7.3. Простые параллельные операции
- 206 7.3.1. Распределение данных в модели CREW PRAM
- 207 7.3.2. Распределение данных в модели EREW PRAM
- 208 7.3.3. Поиск максимального элемента списка
- 210 7.3.4. Упражнения
- 210 7.4. Параллельный поиск
- 212 7.4.1. Упражнения
- 212 7.5. Параллельная сортировка
- 213 7.5.1. Сортировка на линейных сетях
- 214 7.5.2. Четно-нечетная сортировка перестановками
- 217 7.5.3. Другие параллельные сортировки
- 218 7.5.4. Упражнения
- 219 7.6. Параллельные численные алгоритмы
- 219 7.6.1. Умножение матриц в параллельных сетях
- 224 7.6.2. Умножение матриц в модели CRCW PRAM
- 225 7.6.3. Решение систем линейных уравнений алгоритмом SIMD
- 226 7.6.4. Упражнения
- 227 7.7. Параллельные алгоритмы на графах
- 227 7.7.1. Параллельный алгоритм поиска кратчайшего пути
- 229 7.7.2. Параллельный алгоритм поиска минимального остовного дерева
- 231 7.7.3. Упражнения
- 199 7.1. Введение в параллелизм
- 233 8. Недетерминированные алгоритмы
- 235 8.1. Что такое NP?
- 237 8.1.1. Сведение задачи к другой задаче
- 238 8.1.2. NP-полные задачи
- 239 8.2. Типичные NP задачи
- 240 8.2.1. Раскраска графа
- 241 8.2.2. Раскладка по ящикам
- 241 8.2.3. Упаковка рюкзака
- 242 8.2.4. Задача о суммах элементов подмножеств
- 242 8.2.5. Задача об истинности КНФ-выражения
- 242 8.2.6. Задача планирования работ
- 243 8.2.7. Упражнения
- 243 8.3. Какие задачи относятся к классу NP?
- 245 8.3.1. Выполнено ли равенство P=NP?
- 245 8.3.2. Упражнения
- 246 8.4. Проверка возможных решений
- 247 8.4.1. Задача о планировании работ
- 248 8.4.2. Раскраска графа
- 249 8.4.3. Упражнения
- 235 8.1. Что такое NP?
- 250 9. Другие алгоритмические инструменты
- 251 9.1. Жадные приближенные алгоритмы
- 252 9.1.1. Приближения в задаче о коммивояжере
- 254 9.1.2. Приближения в задаче о раскладке по ящикам
- 255 9.1.3. Приближения в задаче об упаковке рюкзака
- 256 9.1.4. Приближения в задаче о сумме элементов подмножества
- 258 9.1.5. Приближения в задаче о раскраске графа
- 259 9.1.6. Упражнения
- 260 9.2. Вероятностные алгоритмы
- 260 9.2.1. Численные вероятностные алгоритмы
- 264 9.2.2. Алгоритмы Монте Карло
- 267 9.2.3. Алгоритмы Лас Вегаса
- 270 9.2.4. Шервудские алгоритмы
- 271 9.2.5. Сравнение вероятностных алгоритмов
- 272 9.2.6. Упражнения
- 273 9.3. Динамическое программирование
- 274 9.3.1. Программирование на основе массивов
- 276 9.3.2. Динамическое умножение матриц
- 278 9.3.3. Упражнения
- 279 9.4. Упражнения по программированию
- 251 9.1. Жадные приближенные алгоритмы
- 281 А. Таблица случайных чисел
- 283 Б. Генерация псевдослучайных чисел
- 284 Б.1. Случайная последовательность в произвольном интервале
- 284 Б.2. Пример применения
- 284 Б.2.1. Первый способ
- 285 Б.2.2. Второй способ
- 286 Б.2.3. Третий способ
- 286 Б.3. Итоги
- 287 В. Ответы к упражнениям
- 298 Литература
- 303 Дополнение
- 304 Д.1. Элементы теории алгоритмов
- 304 Д.1.1. Введение в теорию алгоритмов
- 306 Д.1.2. Форматизация понятия алгоритма
- 308 Д.1.3. Машина Поста
- 310 Д.1.4. Машина Тьюринга
- 311 Д.1.5. Алгоритмически неразрешимые проблемы
- 314 Д.1.6. Сложностные классы задач и проблема P=NP
- 317 Д.1.7. Классы открытых и закрытых задач и теоретическая нижняя граница временной сложности
- 322 Д.2. Оценки трудоемкости
- 322 Д.2.1. Функция трудоемкости и система обозначений
- 323 Д.2.2. Классификация алгоритмов на основе функции трудоемкости
- 327 Д.2.3. Элементарные операции в процедурном языке высокого уровня
- 328 Д.2.4. Методика анализа основных алгоритмических конструкций
- 331 Д.2.5. Примеры анализа трудоемкости алгоритмов
- 338 Д.2.6. Анализ сложности рекурсивных алгоритмов
- 340 Д.2.7. Трудоемкость рекурсивной реализации алгоритмов
- 342 Д.2.8. Методика подсчета вершин рекурсивного дерева
- 346 Д.2.9. Переход к временным оценкам
- 349 Д.2.10. Оценка ресурсной эффективности алгоритмов
- 352 Д.3. Идеи современных алгоритмов
- 352 Д.3.1. Алгоритмы и простые числа
- 356 Д.3.2. Генетические алгоритмы
- 361 Д.3.3. Муравьиные алгоритмы
- 304 Д.1. Элементы теории алгоритмов
Инструкция как скачать книгу Дж. Макконел: Основы современных алгоритмов в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.