Алгоритмы. Введение в разработку и анализ

Ананий Левитин

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

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

Издательство: Вильямс, 2006 г.

ISBN 5-8459-0987-2 (рус), 0-201-74395-7

Количество страниц: 576.

Содержание книги «Алгоритмы. Введение в разработку и анализ»:

14 Предисловие
23 Глава 1. Введение
- 25 1.1 Понятие алгоритма
  - 31 Упражнения 1.1
- 33 1.2 Основы решения алгоритмической задачи
  - 34 Понимание задачи
  - 34 Определение возможностей вычислительного устройства
  - 35 Выбор между точным или приближенным методом решения задачи
  - 36 Выбор подходящих структур данных
  - 36 Методы проектирования алгоритмов
  - 37 Методы представления алгоритмов
  - 38 Оценка корректности алгоритма
  - 39 Анализ алгоритма
  - 40 Кодирование алгоритма
  - 43 Упражнения 1.2
- 45 1.3 Важные типы задач
  - 45 Сортировка
  - 47 Поиск
  - 48 Обработка строк
  - 48 Задачи из теории графов
  - 50 Комбинаторные задачи
  - 50 Геометрические задачи
  - 51 Численные задачи
  - 51 Упражнения 1.3
- 54 1.4 Базовые структуры данных
  - 55 Линейные структуры данных
  - 58 Графы
  - 63 Деревья
  - 67 Множества и словари
  - 70 Упражнения 1.4
- 71 Резюме
73 Глава 2. Основы анализа эффективности алгоритмов
- 75 2.1 Основы анализа
  - 75 Оценка размера входных данных
  - 76 Единицы измерения времени выполнения алгоритма
  - 78 Порядок роста
  - 80 Эффективность алгоритма в разных случаях
  - 84 Повторение пройденного
  - 85 Упражнения 2.1
- 87 2.2 Асимптотические обозначения и основные классы эффективности
  - 88 Нестрогое введение
  - 88 O-обозначение
  - 89 Ω-обозначение
  - 90 Θ-обозначение
  - 91 Полезные свойства сделанных асимптотических обозначений
  - 92 Использование пределов для сравнения порядка роста двух функций
  - 94 Основные классы эффективности
  - 96 Упражнения 2.2
- 98 2.3 Математический анализ нерекурсивных алгоритмов
  - 105 Упражнения 2.3
- 107 2.4 Математический анализ рекурсивных алгоритмов
  - 116 Упражнения 2.4
- 119 2.5 Пример: числа Фибоначчи
  - 120 Явная формула для определения n-го элемента последовательности чисел Фибоначчи
  - 122 Алгоритмы вычисления чисел Фибоначчи
  - 125 Упражнения 2.5
- 127 2.6 Эмпирический анализ алгоритмов
  - 133 Упражнения 2.6
  - 135 Визуализация алгоритмов
- 139 Резюме
141 Глава 3. Метод грубой силы
- 142 3.1 Сортировка выбором и пузырьковая сортировка
  - 143 Сортировка выбором
  - 144 Пузырьковая сортировка
  - 146 Упражнения 3.1
- 147 3.2 Последовательный поиск и поиск подстрок методом грубой силы
  - 147 Последовательный поиск
  - 148 Поиск подстроки
  - 150 Упражнения 3.2
- 152 3.3 Задачи поиска пары ближайших точек и вычисления выпуклой оболочки с использованием грубой силы
  - 152 Поиск пары ближайших точек
  - 154 Поиск выпуклой оболочки
  - 157 Упражнения 3.3
- 159 3.4 Исчерпывающий перебор
  - 159 Задача коммивояжера
  - 160 Задача о рюкзаке
  - 163 Задача о назначениях
  - 164 Упражнения 3.4
- 166 Резюме
167 Глава 4. Метод декомпозиции
- 169 4.1 Сортировка слиянием
  - 172 Упражнения 4.1
- 174 4.2 Быстрая сортировка
  - 179 Упражнения 4.2
- 180 4.3 Бинарный поиск
  - 183 Упражнения 4.3
- 184 4.4 Обход бинарного дерева
  - 188 Упражнения 4.4
- 189 4.5 Умножение больших целых чисел и алгоритм умножения матриц Штрассена
  - 189 Умножение больших целых чисел
  - 192 Алгоритм Штрассена для умножения матриц
  - 194 Упражнения 4.5
- 195 4.6 Решение задач о паре ближайших точек и о выпуклой оболочке методом декомпозиции
  - 196 Задача о паре ближайших точек
  - 198 Задача о выпуклой оболочке
  - 200 Упражнения 4.6
- 201 Резюме
203 Глава 5. Метод уменьшения размера задачи
- 206 5.1 Сортировка вставкой
  - 209 Упражнения 5.1
- 211 5.2 Поиск в глубину и поиск в ширину
  - 212 Поиск в глубину
  - 215 Поиск в ширину
  - 218 Упражнения 5.2
- 220 5.3 Топологическая сортировка
  - 224 Упражнения 5.3
- 226 5.4 Алгоритмы генерации комбинаторных объектов
  - 227 Генерация перестановок
  - 229 Генерация подмножеств
  - 231 Упражнения 5.4
- 232 5.5 Алгоритмы с использованием уменьшения на постоянный множитель
  - 233 Задача поиска фальшивой монеты
  - 234 Умножение по-русски
  - 235 Задача Иосифа
  - 237 Упражнения 5.5
- 238 5.6 Алгоритмы с переменным уменьшением размера
  - 238 Вычисление медианы и задача выбора
  - 240 Интерполяционный поиск
  - 242 Поиск и вставка в бинарное дерево поиска
  - 243 Упражнения 5.6
- 244 Резюме
247 Глава 6. Метод преобразования
- 248 6.1 Предварительная сортировка
  - 252 Упражнения 6.1
- 254 6.2 Метод исключения Гаусса
  - 259 LU-разложение и другие приложения
  - 261 Вычисление обратной матрицы
  - 262 Вычисление определителя
  - 264 Упражнения 6.2
- 265 6.3 Сбалансированные деревья поиска
  - 267 AVL-деревья
  - 271 2-3-деревья
  - 274 Упражнения 6.3
- 275 6.4 Пирамиды и пирамидальная сортировка
  - 276 Понятие пирамиды
  - 281 Пирамидальная сортировка
  - 282 Упражнения 6.4
- 284 6.5 Схема Горнера и возведение в степень
  - 284 Схема Горнера
  - 286 Бинарное возведение в степень
  - 289 Упражнения 6.5
- 291 6.6 Приведение задачи
  - 292 Вычисление наименьшего общего кратного
  - 293 Подсчет путей в графе
  - 293 Приведение задач оптимизации
  - 295 Линейное программирование
  - 297 Приведение к задачам о графах
  - 299 Упражнения 6.6
- 301 Резюме
305 Глава 7. Пространственно-временной компромисс
- 307 7.1 Сортировка подсчетом
  - 310 Упражнения 7.1
- 312 7.2 Улучшение входных данных в поиске подстрок
  - 313 Алгоритм Хорспула
  - 317 Алгоритм Бойера-Мура
  - 322 Упражнения 7.2
- 323 7.3 Хеширование
  - 325 Открытое хеширование (раздельные цепочки)
  - 326 Закрытое хеширование (открытая адресация)
  - 329 Упражнения 7.3
- 331 7.4 B-деревья
  - 335 Упражнения 7.4
- 336 Резюме
339 Глава 8. Динамическое программирование
- 341 8.1 Вычисление биномиальных коэффициентов
  - 343 Упражнения 8.1
- 345 8.2 Алгоритмы Воршалла и Флойда
  - 345 Алгоритм Воршалла
  - 349 Алгоритм Флойда поиска кратчайших путей между всеми парами вершин
  - 353 Упражнения 8.2
- 354 8.3 Оптимальные бинарные деревья поиска
  - 360 Упражнения 8.3
- 361 8.4 Задача о рюкзаке и функции с запоминанием
  - 364 Функции с запоминанием
  - 366 Упражнения 8.4
- 368 Резюме
369 Глава 9. Жадные методы
- 371 9.1 Алгоритм Прима
  - 376 Упражнения 9.1
- 378 9.2 Алгоритм Крускала
  - Непересекающиеся подмножества и алгоритмы поиска
  - 381 объединений
  - 385 Упражнения 9.2
- 386 9.3 Алгоритм Дейкстры
  - 390 Упражнения 9.3
- 392 9.4 Деревья Хаффмана
  - 397 Упражнения 9.4
- 398 Резюме
401 Глава 10. Ограничения мощи алгоритмов
- 402 10.1 Доказательства нижних границ
  - 403 Тривиальные нижние границы
  - 404 Информационно-теоретические доказательства
  - 405 Доказательство «от противника
  - 406 Приведение задачи
  - 408 Упражнения 10.1
- 409 10.2 Деревья принятия решения
  - 411 Деревья принятия решения для алгоритмов сортировки
  - 412 Деревья принятия решения для поиска в отсортированном массиве
  - 415 Упражнения 10.2
- 417 10.3 P, NP и NP-полные задачи
  - 418 P и NP-задачи
  - 423 NP-полные задачи
  - 426 Упражнения 10.3
- 428 10.4 Численные алгоритмы
  - 437 Упражнения 10.4
- 438 Резюме
441 Глава 11. Преодоление ограничений
- 442 11.1 Поиск с возвратом
  - 443 Задача о n ферзях
  - 444 Задача о гамильтоновом цикле
  - 445 Задача о сумме подмножества
  - 447 Общие замечания
  - 449 Упражнения 11.1
- 451 11.2 Метод ветвей и границ
  - 452 Задача о назначениях
  - 455 Задача о рюкзаке
  - 458 Задача коммивояжера
  - 460 Упражнения 11.2
- 461 11.3 Приближенные алгоритмы для NP-сложных задач
  - 463 Приближенный алгоритм для решения задачи коммивояжера
  - 468 Приближенные алгоритмы для задачи о рюкзаке
  - 473 Упражнения 11.3
- 475 11.4 Алгоритмы для решения нелинейных уравнений
  - 476 Метод деления пополам
  - 480 Метод секущих
  - 481 Метод Ньютона
  - 484 Упражнения 11.4
- 485 Резюме
487 Эпилог
491 Приложение А. Формулы, использующиеся при анализе алгоритмов
- 491 Свойства логарифмов
- 491 Комбинаторика
- 492 Важные формулы суммирования
- 492 Правила работы с суммами
- 493 Приближение суммы определенным интегралом
- 493 Формулы для округлений снизу и сверху
- 493 Разное
495 Приложение Б. Краткое руководство по рекуррентным соотношениям
- 495 Последовательности и рекуррентные соотношения
- 497 Методы решения рекуррентных соотношений
- 501 Распространенные типы рекуррентных соотношений в анализе алгоритмов
509 Список литературы
517 Указания к упражнениям
562 Предметный указатель