Построение и анализ вычислительных алгоритмов
Автор(ы): | Ахо А., Хопкрофт Дж., Ульман Дж.
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) |