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

Автор(ы):Ахо А., Хопкрофт Дж., Ульман Дж.
07.04.2012
Год изд.:1979
Описание: В монографии с единых позиций излагаются результаты теоретических и прикладных исследований по построению быстрых алгоритмов и доказательству их отсутствия. Рассмотрены задачи перебора, упорядочения массивов данных, умножения чисел, умножения матриц; обсуждаются алгоритмы на графах. Многие результаты ранее были рассеяны в труднодоступных источниках и в монографическом виде публикуются впервые. Книга рассчитана на специалистов по современному программированию, разработчиков вычислительных систем и алгоритмов; она может быть использована как учебное пособие студентами и аспирантами, специализирующимися в области вычислительной математики.
Оглавление:
Построение и анализ вычислительных алгоритмов — обложка книги. Обложка книги.
ПРЕДИСЛОВИЕ К РУССКОМУ ПЕРЕВОДУ [5]
ПРЕДИСЛОВИЕ [7]
1. МОДЕЛИ ВЫЧИСЛЕНИЙ [11]
  1.1. Алгоритмы и их сложности [11]
  1.2. Машины с произвольным доступом к памяти [15]
  1.3. Вычислительная сложность РАМ-программ [22]
  1.4. Модель с хранимой программой [26]
  1.5. Модификация РАМ [32]
  1.6. Простейшая модель вычислений: машина Тьюринга [39]
  1.7. Связь машин Тьюринга и РАМ [45]
  1.8. Язык высокого уровня — Упрощенный Алгол [47]
  Упражнения [54]
  Замечания по литературе [56]
2. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ [57]
  2.1. Структуры данных: списки, очереди и стеки [58]
  2.2. Представления множеств [63]
  2.3. Графы [64]
  2.4. Деревья [67]
  2.5. Рекурсия [70]
  2.6. Разделяй и властвуй [75]
  2.7. Балансировка [81]
  2.8. Динамическое программирование [83]
  2.9. Эпилог [85]
  Упражнения [86]
  Замечания по литературе [92]
3. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ [93]
  3.1. Задача сортировки [94]
  3.2. Цифровая сортировка [95]
  3.3. Сортировка с помощью сравнений [104]
  3.4. Сортдеревом — упорядочение с помощью 0(n log n) сравнений [106]
  3.5. Быстрсорт — упорядочение за среднее время 0(n log n) [111]
  3.6. Порядковые статистики [117]
  3.7. Среднее время для порядковых статистик [119]
  Упражнения [122]
  Замечания по литературе [127]
4. СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ, КАСАЮЩИХСЯ РАБОТЫ С МНОЖЕСТВАМИ [128]
  4.1. Основные операции над множествами [128]
  4.2. Метод расстановки [132]
  4.3. Двоичный поиск [135]
  4.4. Деревья двоичного поиска [136]
  4.5. Оптимальные деревья двоичного поиска [141]
  4.6. Простой алгоритм для нахождения объединения непересекающихся множеств [146]
  4.7. Древовидные структуры для задачи ОБЪЕДИНИТЬ—НАЙТИ [150]
  4.8. Приложения и обобщения алгоритма ОБЪЕДИНИТЬ—НАЙТИ [162]
  4.9. Схемы сбалансированных деревьев [168]
  4.10. Словари и очереди с приоритетами [171]
  4.11. Сливаемые деревья [175]
  4.12. Сцепляемые очереди [178]
  4.13. Разбиение [181]
  4.14. Резюме [188]
  Упражнения [188]
  Замечания по литературе [195]
5. АЛГОРИТМЫ НА ГРАФАХ [197]
  5.1. Остовное дерево наименьшей стоимости [197]
  5.2. Метод поиска в глубину [202]
  5.3. Дву связность [206]
  5.4. Поиск в глубину в ориентированном графе [214]
  5.5. Сильная связность [216]
  5.6. Задачи нахождения путей [223]
  5.7. Алгоритм транзитивного замыкания [227]
  5.8. Алгоритм нахождения кратчайшего пути [229]
  5.9. Задачи о путях и умножение матриц [230]
  5.10. Задачи с одним источником [235]
  5.11. Доминаторы в ориентированных ациклических графах: комбинирование понятий [238]
  Упражнения [247]
  Замечания по литературе [254]
6. УМНОЖЕНИЕ МАТРИЦ И СВЯЗАННЫЕ С НИМ ОПЕРАЦИИ [255]
  6.1. Основные понятия [255]
  6.2. Алгоритм Штрассена для умножения матриц [259]
  6.3. Обращение матриц [262]
  6.4. НВП-разложение матрицы [263]
  6.5. Приложения НВП-разложения [272]
  6.6. Умножение булевых матриц [274]
  Упражнения [279]
  Замечания по литературе [283]
7. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ [284]
  7.1. Дискретное преобразование Фурье и обратное к нему [284]
  7.2. Алгоритм быстрого преобразования Фурье [290]
  7.3. БПФ при использовании битовых операций [298]
  7.4. Произведение полиномов [303]
  7.5. Алгоритм Шёнхаге — Штрассена для умножения целых чисел [304]
  Упражнения [308]
  Замечания по литературе [310]
8. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ [311]
  8.1. Аналогии между целыми числами и полиномами [312]
  8.2. Умножение и деление целых чисел [313]
  8.3. Умножение и деление полиномов [320]
  8.4. Модульная арифметика [323]
  8.5. Модульная арифметика полиномов и вычисление их значений [327]
  8.6. Применение китайской теоремы об остатках [329]
  8.7. Китайская теорема об остатках и интерполяция полиномов [333]
  8.8. Наибольшие общие делители и алгоритм Евклида [336]
  8.9. Асимптотически быстрый алгоритм нахождения НОД полиномов [339]
  8.10. НОД целых чисел [345]
  8.11. Еще раз о применении китайской теоремы об остатках [347]
  8.12. Разреженные полиномы [348]
  Упражнения [350]
  Замечания по литературе [353]
9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ [354]
  9.1. Конечные автоматы и регулярные выражения [354]
  9.2. Распознавание образов, задаваемых регулярными выражениями [363]
  9.3. Распознавание подцепочек [367]
  9.4. Двусторонний детерминированный магазинный автомат [373]
  9.5. Позиционные деревья и идентификаторы позиций [385]
  Упражнения [398]
  Замечания по литературе [403]
10. NP-ПОЛНЫЕ ЗАДАЧИ [404]
  10.1. Недетерминированные машины Тьюринга [405]
  10.2. Классы P и NP [414]
  10.3. Языки и Задачи [417]
  10.4. NP-полнота задачи выполнимости [420]
  10.5. Еще несколько NP-полных задач [428]
  10.6. Задачи с полиномиально ограниченной памятью [440]
  Упражнения [446]
  Замечания по литературе [450]
11. НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ [451]
  11.1. Иерархии по сложности [451]
  11.2. Иерархия по емкостной сложности для детерминированных машин Тьюринга [452]
  11.3. Задача, требующая экспоненциальных времени и памяти [456]
  11.4. Неэлементарная задача [466]
  Упражнения [471]
  Замечания по литературе [474]
12. НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ [475]
  12.1. Поля [475]
  12.2. Еще раз о неветвящихся программах [477]
  12.3. Матричная формулировка задач [479]
  12.4. Нижняя граница для числа умножений, связанная с рангом по строкам [480]
  12.5. Нижняя граница для числа умножений, связанная с рангом по столбцам [483]
  12.6. Граница для числа умножений, связанная с рассмотрением строк и столбцов [488]
  12.7. Предварительная обработка [490]
  Упражнения [493]
  Замечания по литературе [501]
СПИСОК ЛИТЕРАТУРЫ [502]
ГЛОССАРИЙ [514]
ИМЕННОЙ УКАЗАТЕЛЬ [516]
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ [519]
Формат: djvu
Размер:5801002 байт
Язык:РУС
Рейтинг: 222 Рейтинг
Открыть: Ссылка (RU)