Построение и анализ вычислительных алгоритмов

  

Ахо А. Построение и анализ вычислительных алгоритмов. Изд-во "Мир", М., 1979 г.

В монографии с единых позиций излагаются результаты теоретических и прикладных исследований по построению быстрых алгоритмов и доказательству их отсутствия. Рассмотрены задачи перебора, упорядочения массивов данных, умножения чисел, умножения матриц; обсуждаются алгоритмы на графах. Многие результаты ранее были рассеяны в труднодоступных источниках и в монографическом виде публикуются впервые.

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



Оглавление

ПРЕДИСЛОВИЕ
МОДЕЛИ ВЫЧИСЛЕНИЙ
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. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ
3.1. ЗАДАЧА СОРТИРОВКИ
3.2. ЦИФРОВАЯ СОРТИРОВКА
3.3. СОРТИРОВКА С ПОМОЩЬЮ СРАВНЕНИЙ
3.4. СОРТДЕРЕВОМ — УПОРЯДОЧЕНИЕ С ПОМОЩЬЮ O(n log n) СРАВНЕНИЙ
3.5. БЫСТРСОРТ — УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ O(n log n)
3.6. ПОРЯДКОВЫЕ СТАТИСТИКИ
3.7. СРЕДНЕЕ ВРЕМЯ ДЛЯ ПОРЯДКОВЫХ СТАТИСТИК
4. СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ, КАСАЮЩИХСЯ РАБОТЫ С МНОЖЕСТВАМИ
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.2. АЛГОРИТМ ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ МАТРИЦ
6.3. ОБРАЩЕНИЕ МАТРИЦ
6.4. НВП-РАЗЛОЖЕНИЕ МАТРИЦЫ
6.5. ПРИЛОЖЕНИЯ НВП-РАЗЛОЖЕНИЯ
6.6. УМНОЖЕНИЕ БУЛЕВЫХ МАТРИЦ
7. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ
7.2. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
7.3. БПФ ПРИ ИСПОЛЬЗОВАНИИ БИТОВЫХ ОПЕРАЦИЙ
7.4. ПРОИЗВЕДЕНИЕ ПОЛИНОМОВ
7.5. АЛГОРИТМ ШЕНХАГЕ — ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ
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. ЕЩЕ НЕСКОЛЬКО NP-ПОЛНЫХ ЗАДАЧ
10.6. ЗАДАЧИ С ПОЛИНОМИАЛЬНО ОГРАНИЧЕННОЙ ПАМЯТЬЮ
11. НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ
11.2. ИЕРАРХИЯ ПО ЕМКОСТНОЙ СЛОЖНОСТИ ДЛЯ ДЕТЕРМИНИРОВАННЫХ МАШИН ТЬЮРИНГА
11.3. ЗАДАЧА, ТРЕБУЮЩАЯ ЭКСПОНЕНЦИАЛЬНЫХ ВРЕМЕНИ И ПАМЯТИ
11.4. НЕЭЛЕМЕНТАРНАЯ ЗАДАЧА
12. НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ
12.2. ЕЩЕ РАЗ О НЕВЕТВЯЩИХСЯ ПРОГРАММАХ
12.3. МАТРИЧНАЯ ФОРМУЛИРОВКА ЗАДАЧ
12.4. НИЖНЯЯ ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАНГОМ ПО СТРОКАМ
12.5. НИЖНЯЯ ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАНГОМ ПО СТОЛБЦАМ
12.6. ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАССМОТРЕНИЕМ СТРОК И СТОЛБЦОВ
12.7. ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА
email@scask.ru