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

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

Содержание:

• Предисловие

1. Основы анализа алгоритмов

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

2. Алгоритмы поиска и выборки

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

3. Алгоритмы сортировки

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

4. Численные алгоритмы

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

5. Алгоритмы сравнения с образцом

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

6. Алгоритмы на графах

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

7. Параллельные алгоритмы

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

8. Недетерминированные алгоритмы

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

9. Другие алгоритмические инструменты

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

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

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

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

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

• Литература

Дополнение

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

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

 

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