Программирование

Дж. Макконнелл. Основы современных алгоритмов

Дж. Макконнелл. Основы современных алгоритмов

2-е издание

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

Содержание:
  • Предисловие

1. Основы анализа алгоритмов
  • Что такое анализ?
  • Что подсчитывать и что учитывать
  • Необходимые математические сведения
  • Скорости роста
  • Алгоритмы вида «разделяй и властвуй»
  • Рекуррентные соотношения
  • Анализ программ

2. Алгоритмы поиска и выборки
  • Последовательный поиск
  • Двоичный поиск
  • Выборка
  • Упражнение по программированию

3. Алгоритмы сортировки
  • Сортировка вставками
  • Пузырьковая сортировка
  • Сортировка Шелла
  • Корневая сортировка
  • Пирамидальная сортировка
  • Сортировка слиянием
  • Быстрая сортировка
  • Внешняя многофазная сортировка слиянием
  • Дополнительные упражнения
  • Упражнения по программированию

4. Численные алгоритмы
  • Вычисление значений многочленов
  • Умножение матриц
  • Решение линейных уравнений

5. Алгоритмы сравнения с образцом
  • Сравнение строк
  • Приблизительное сравнение строк
  • Упражнения по программированию

6. Алгоритмы на графах
  • Основные понятия теории графов
  • Структуры данных для представления графов
  • Алгоритмы обхода в глубину и по уровням
  • Алгоритм поиска минимального остовного дерева
  • Алгоритм поиска кратчайшего пути
  • Алгоритм определения компонент двусвязности
  • Разбиения множеств
  • Упражнения по программированию

7. Параллельные алгоритмы
  • Введение в параллелизм
  • Модель PRAM
  • Простые параллельные операции
  • Параллельный поиск
  • Параллельная сортировка
  • Параллельные численные алгоритмы
  • Параллельные алгоритмы на графах

8. Недетерминированные алгоритмы
  • Что такое NP?
  • Типичные NP задачи
  • Какие задачи относятся к классу NP?
  • Проверка возможных решений

9. Другие алгоритмические инструменты
  • Жадные приближенные алгоритмы
  • Вероятностные алгоритмы
  • Динамическое программирование
  • Упражнения по программированию

А. Таблица случайных чисел

Б. Генерация псевдослучайных чисел

  • Случайная последовательность в произвольном интервале
  • Пример применения
  • Итоги

В. Ответы к упражнениям
  • Литература

Дополнение
  • Элементы теории алгоритмов
  • Оценки трудоемкости
  • Идеи современных алгоритмов

Издательство: Техносфера
Серия: Мир программирования
Год издания: 2004
Страниц: 368
ISBN: 5-94836-005-9
Формат: PDF
Качество: отличное

 

Скачать книгу «Основы современных алгоритмов» (10 МБ):

deposit_rumit 30/03/19 Просмотров: 2402
+5