Последовательные и параллельные алгоритмы. Общий подход

Предисловие
Обзор глав
Рекомендуем использовать
Переписка
Благодарность
ГЛАВА 1. Асимптотический анализ
Асимптотический анализ
Асимптотические отношения
Асимптотический анализ и пределы
Примечания к главе
Упражнения
ГЛАВА 2. Индукция и рекурсия
Индукция и рекурсия
Математическая индукция
Примеры индукции
Рекурсия
Бинарный поиск
Слияние и сортировка слияниями
Примечания к главе
Упражнения
ГЛАВА 3. Основной метод
Основной метод
Доказательство основной теоремы
(факультативное)
Примеры
Примечания к главе
Упражнения
ГЛАВА 4. Комбинационные схемы
Комбинационные схемы и сортирующие сети
Примечания к главе
Упражнения
ГЛАВА 5. Вычислительные модели
Вычислительные модели
Примеры: простые алгоритмы
Фундаментальные понятия
Сети процессоров
Структура сетей процессоров
Дополнительная терминология
Примечания к главе
Упражнения
ГЛАВА 6. Матричные операции
Матричные операции
Умножение матриц
Метод исключения Гаусса
Примечания к главе
Упражнения
ГЛАВА 7. Параллельный префикс
Параллельный префикс
Приложение
Задача о нулях и единицах
Интервальная (сегментная) передача (broadcasting)
данных
Задача о доминирующих точках
Задачи о пересекающихся отрезках
Примечания к главе
Упражнения
ГЛАВА 8. Переход по указателю
Переход по указателю
Ранжирование списка
Параллельный префикс в связном списке
Примечания к главе
Упражнения
ГЛАВА 9. Разделяй и властвуй
Разделяй и властвуй
Сортировка слияниями (пересмотренная)
Выбор
Быстрая сортировка (сортировка с разбиением)
Гипербыстрая сортировка (HyperQuickSort)
Алгоритм битонической сортировки
(переработанный)
Параллельное чтение/запись
Примечания к главе
Упражнения
ГЛАВА 10. Вычислительная геометрия
Вычислительная геометрия
Выпуклая оболочка
Просмотр Грэхема
Решение методом "разделяй и властвуй"
Наименьшая окружающая оболочка
Задача о нахождении всех ближайших точек
Независимая от архитектуры разработка
алгоритмов
Задачи о пересечении прямых
Перекрывающиеся отрезки
Примечания к главе
Упражнения
ГЛАВА 11. Обработка изображений
Обработка изображений
Начальные сведения
Маркировка компонентов
Выпуклая оболочка
Задачи о расстоянии
Показатель Хаусдорфа для цифровых изображений
Примечания к главе
Упражнения
ГЛАВА 12. Алгоритмы на графах
Алгоритмы на графах
Основные понятия
Способы описания графа
Фундаментальные алгоритмы
Маркировка связных компонентов
Остовное дерево минимального веса
Задачи о кратчайших путях
Примечания к главе
Упражнения
ГЛАВА 13. Численные задачи
Численные задачи
Проверка чисел на простоту
Наибольший общий делитель
Целые степени
Вычисление значения многочлена
Приближенные вычисления с помощью ряда
Тэйлора
Вычисление интеграла по формуле трапеций
Примечания к главе
Упражнения
Предметный указатель