Основы современных алгоритмов

Дж. Макконел

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

В дополнении ко 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. Анализ программ
  • 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. Упражнение по программированию
  • 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. Упражнения по программированию
  • 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. Упражнения
  • 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. Упражнения по программированию
  • 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. Упражнения по программированию
  • 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. Упражнения
  • 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. Упражнения
  • 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. Упражнения по программированию
  • 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. Муравьиные алгоритмы

Инструкция как скачать книгу Дж. Макконел: Основы современных алгоритмов в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
Основы современных алгоритмов
Рейтинг книги:
1 голос
172

Поиск книг:




При поиске учитываются только слова, длина которых больше 3-х символов.

Статистика: