- Артикул:00-01119128
- Автор: А. Ахо, Дж. Хопкрофт, Дж. Ульман
- Обложка: Твердая обложка
- Издательство: МИР (все книги издательства)
- Город: Москва
- Страниц: 536
- Формат: 60х90 1/16
- Год: 1979
- Вес: 802 г
Развернуть ▼
В монографии с единых позиций излагаются результаты теоретических и прикладных исследований по построению быстрых алгоритмов и доказательству их отсутствия. Рассмотрены задачи перебора, упорядочения массивов данных, умножения чисел, умножения матриц; обсуждаются алгоритмы на графах. Многие результаты ранее были рассеяны в труднодоступных источниках и в монографическом виде публикуются впервые.
Книга рассчитана на специалистов по современному программированию, разработчиков вычислительных систем и алгоритмов; она может быть использована как учебное пособие студентами и аспирантами, специализирующимися в области вычислительной математики.
Содержание
Предисловие к русскому переводу предисловие
1. Модели вычислений
1.1. Алгоритмы и их сложности
1.2. Машины с произвольным доступом к памяти
1.3. Вычислительная сложность Р АМ-программ
1.4. Модель с хранимой программой
1.5. Модификация РАМ
1.6. Простейшая модель вычислений: машина Тьюринга
1.7. Связь машин Тьюринга и РАМ
1.8. Язык высокого уровня - Упрощенный Алгол Упражнения
Замечания по литературе
2. Разработка эффективных алгоритмов
2.1. Структуры данных: списки, очереди и стеки
2.2. Представления множеств
2.3. Графы
2.4. Деревья
2.5. Рекурсия
2.6. Разделяй и властвуй
2.7. Балансировка
2.8. Динамическое программирование
2.9. Эпилог Упражнения
Замечания по литературе
З. Сортировка и порядковые статистики
3.1. Задача сортировки
3.2. Цифровая сортировка
3.3. Сортировка с помощью сравнений
3.4. Сортдеревом - упорядочение с помощью О(n 1оg n) сравнений
3.5. Быстрсорт - упорядочение за среднее время О(n 1оg n)
3.6. Порядковые статистики
3.7. Среднее время для порядковых статистик
Упражнения
Замечания по литературе
4. Структуры данных для задач, касающихся работы с множествами
4.1. Основные операции над множествами
4.2. Метод расстановки
4.3. Двоичный поиск
4.4. Деревья двоичного поиска
4.5. Оптимальные деревья двоичного поиска
4.6. Простой алгоритм для нахождения объединения непересекающихся множеств
4.7. Древовидные структуры для задачи объединить-найти
4.8. Приложения и обобщения алгоритма объединить-найти
4.9. Схемы сбалансированных деревьев
4.10. Словари и очереди с приоритетами
4.11. Сливаемые деревья
4.12. Сцепляемые очереди
4.13. Разбиение
4.14. Резюме
Упражнения
Замечания по литературе
5. Алгоритмы на графах
5.1. Остовное дерево наименьшей стоимости
5.2. Метод поиска в глубину
5.3. Двусвязность
5.4. Поиск в глубину в ориентированном графе
5.5. Сильная связность
5.6. Задачи нахождения путей
5.7. Алгоритм транзитивного замыкания
5.8. Алгоритм нахождения кратчайшего пути
5.9. Задачи о путях и умножение матриц
5.10. Задачи с одним источником
5.11. Доминаторы в ориентированных ациклических графах: комбинирование понятий
Упражнения
Замечания по литературе
6. Умножение матриц и связанные с ним операции
6.1. Основные понятия
6.2. Алгоритм Штрассена для умножения матриц
6.3. Обращение матриц
6.4. НВП-разложение матрицы
6.5. Приложения НВП-разложения
6.6. Умножение булевых матриц Упражнения
Замечания по литературе
7. Быстрое преобразование Фурье и его приложения
7.1. Дискретное преобразование Фурье и обратное к нему
7.2. Алгоритм быстрого преобразования Фурье
7.3. БПФ при использовании битовых операций
7.4. Произведение полиномов
7.5. Алгоритм Шёнхаге - Штрассена для умножения целых чисел
7.6. Упражнении
Замечания по литературе
8. Арифметические операции над целыми числами и полиномами
8.1. Аналогии между целыми числами и полиномами
8.2. Умножение и деление целых чисел
8.3. Умножение и деление полиномов
8.4. Модульная арифметика
8.5. Модульная арифметика полиномов и вычисление их значений
8.6. Применение китайской теоремы об остатках
8.7. Китайская теорема об остатках и интерполяция полиномов
8.8. Наибольшие общие делители и алгоритм Евклида
8.9. Асимптотически быстрый алгоритм нахождения НОД полиномов
8.10. НОД целых чисел
8.11. Еще раз о применении китайской теоремы об остатках
8.12. Разреженные полиномы Упражнения
Замечания по литературе
9. Алгоритмы идентификации
9.1. Конечные автоматы и регулярные выражения
9.2. Распознавание образов, задаваемых регулярными выражениями
9.3. Распознавание подцепочек
9.4. Двусторонний детерминированный магазинный автомат
9.5. Позиционные деревья и идентификаторы позиций
Упражнения
Замечания по литературе
10. NP- полные задачи
10.1. Недетерминированные машины Тьюринга
10.2. Классы Р и
10.3. Языки и задачи
10.4. NP-полнота задачи выполнимости
10.5. Еще несколько МР-полных задач
10.6. Задачи с полиномиально ограниченной памятью
Упражнения
Замечания по литературе
11. Некоторые доказуемо трудно разрешимые задачи
11.1. Иерархии по сложности
11.2. Иерархия по емкостной сложности для детерминированных машин Тьюринга
11.3. Задача, требующая экспоненциальных времени и памяти
11.4. Неэлементарная задача
Упражнения
Замечания по литературе
12. Нижние оценки числа арифметических операций
12.1. Поля
12.2. Еще раз о неветвящихся программах
12.3. Матричная формулировка задач
12.4. Нижняя граница для числа умножений, связанная с рангом по строкам
12.5. Нижняя граница для числа умножений, связанная с рангом по столбцам
12.6. Граница для числа умножений, связанная с рассмотрением строк и столбцов
12.7. Предварительная обработка
Упражнения
Замечания по литературе
Список литературы
Глоссарий
Именной указатель
Предметный указатель