3 Ахо А., Хопкрофт Д., Ульман Д. - Построение и анализ вычислительных алгоритмов (1979) (1162194)
Текст из файла
А.Ахо, Дж.Хопкрофт, Дж.УльманПОСТРОЕНИЕ И АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВМ.: Мир, 1979, 536 стр.В монографии с единых позиций излагаются результаты теоретических иприкладных исследований по построению быстрых алгоритмов и доказательствуих отсутствия. Рассмотрены задачи перебора, упорядочения массивов данных,умножения чисел, умножения матриц, обсуждаются алгоритмы на графах.Многие результаты ранее были рассеяны в труднодоступных источниках и вмонографическом виде публикуются впервые.Книга рассчитана на специалистов по современному программированию,разработчиков вычислительных систем и алгоритмов, она может бытьиспользованакакучебноепособиестудентамииаспирантами,специализирующимися в области вычислительной математики.СодержаниеПРЕДИСЛОВИЕ К РУССКОМУ ПЕРЕВОДУ5ПРЕДИСЛОВИЕ71. МОДЕЛИ ВЫЧИСЛЕНИЙ111.1.
Алгоритмы и их сложности111.2. Машины с произвольным доступом к памяти151.3. Вычислительная сложность РАМ-программ221.4. Модель с хранимой программой261.5. Модификация РАМ321.6. Простейшая модель вычислений: машина Тьюринга391.7. Связь машин Тьюринга и РАМ451.8. Язык высокого уровня—Упрощенный Алгол47Упражнения54Замечания по литературе562. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ572.1. Структуры данных: списки, очереди и стеки582.2. Представления множеств632.3. Графы642.4.
Деревья672.5. Рекурсия702.6. Разделяй и властвуй752.7. Балансировка812.8. Динамическое программирование832.9. Эпилог85Упражнения86Замечания по литературе923. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ933.1. Задача сортировки943.2. Цифровая сортировка953.3. Сортировка с помощью сравнений1043.4.
Сортдеревом—упорядочение с помощью O(n log n) сравнений1063.5. Быстрcopт—упорядочение за среднее время O(n log 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.
НВП-разложение матрицы1111171191221271281281321351361411461501621681711751781811881881951971972022062142162232272292302352382472542552552592622636.5. Приложения НВП-разложения6.6. Умножение булевых матрицУпражненияЗамечания по литературе7.
БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ7.1. Дискретное преобразование Фурье и обратное к нему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. Классы P и NP10.3.
Языки и задачи10.4. NP-полнота задачи выполнимости10.5. Еще несколько NP-полных задач10.6. Задачи с полиномиально ограниченной памятьюУпражнения272274279283284284290298303304308310311312313320323327329333336339345347348350353354354363367373385398403404405414417420428440446Замечания по литературе45011. НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ45111.1.
Иерархии по сложности45111.2. Иерархия по емкостной сложности для детерминированных машин452Тьюринга11.3. Задача, требующая экспоненциальных времени и памяти45611.4. Неэлементарная задача466Упражнения471Замечания по литературе47412. НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ47512.1. Поля47512.2. Еще раз о неветвящихся программах47712.3. Матричная формулировка задач47912.4. Нижняя граница для числа умножений, связанная с рангом по480строкам12.5. Нижняя граница для числа умножений, связанная с рангом по483столбцам12.6. Граница для числа умножений, связанная с рассмотрением строк и488столбцов12.7. Предварительная обработка490Упражнения493Замечания по литературе501СПИСОК ЛИТЕРАТУРЫ502ГЛОССАРИИ514ИМЕННОЙ УКАЗАТЕЛЬ516ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ519ПРЕДМЕТНЫЙ УКАЗАТЕЛЬАдрес (address) 16Автомат (automaton) конечный- возврата (return) 73(finite) 165, 361, 365- значения (value) 73- - детерминированный (deterministic)- символический (symbolic) 33165, 361Адресация (addressing) — косвенная- - недетерминированный(indirect) 16(nondeterministic) 356Активный (active) 484, 490- линейно ограниченный (linearАлгол (ALGOL) — Упрощенныйbounded) 449(Pidgin) 48- магазинный (pushdown) 373Алгоритм (algorithm) — Дейкстры- - двусторонний (two-way) 373, 400(Dijkstra's) 236- - - детерминированный- Евклида (Euclid's) 336(deterministic) 373—375- - расширенный (extended) 336, 337- - детерминированный (deterministic)- Крускала (Kruskal's) 199373, 400, 401- префиксный (on-line) 129- - недетерминированный- свободный (off-line) 129(nondeterministic) 400- - односторонний (one-way) 400- с предварительной обработкойданных (preconditioned) 329- четырех русских (four Russians')275, 277- Шёнхаге — Штрассена (Schonhage— Strassen) 304, 306- Штрассена (Strassen-'s) 259Алфавит (alphabet) 19, 355- входной (input) 165, 356, 375- магазинный (pushdown list) 374, 375Аннулятор (anihilator) 224Антисимметричность (antisymmetry)94Аргумент (argument) см.
Параметр,51База данных (data base) 132, 147, 188Баланс узла (balance of a vertex) 194Балансировка (balancing) 81БЛОК (INBLOCK) 185Блок (block) 51БПФ (FFT) см. ПреобразованиеФурье, быстрое 294Брат (brother) 174Быстрсорт (quicksort) 111, 113БЫСТРСОРТ (QUICKSORT) 113ВЕРШИНА (TOP) 61Вес дерева (weight of a tree) 142ВЗИМОЗАМЕНА (INTERCHANGE)52ВНЕШ-ИМЯ (EXTERNAL_NAME)147ВНУТПОРЯДОК (INORDER) 71ВНУТР_ИМЯ (INTERNAL-NAME)147В-ОЖИДАНИИ (INWAITING) 186ВПИСАТЬ (ENQUEUE) 62, 194ВРЕМ (TEMP) 380ВСТАВИТЬ (INSERT) 59, 128Вход (input) 34- вычисления (of computation) 477ВЫБОР (SELECT) 118, 122Вызов (call) — по значению (byvalue) 52- - наименованию (by name) 52- - ссылке (by reference) 52ВЫПИСАТЬ (DEQUEUE) 62, 194Выполнимость (satisfiability) 419Выражение (expression)- регулярное (regular) 355- - полу расширенное (semiextended)457- - расширенное (extended) 456Высота (height) — дерева (of a tree)68- узла (of a vertex) 68ВЫТОЛКНУТЬ (POP) 61Выход (output) 34Выход (в графе) (output vertex) 497Вычисление (computation) — битовое(bitwise) 35- двойственное (dual) 496- линейное (linear) 497- машины с данным измерителем,правильное (of a machine with agiven yardstick, valid) 462- относительно поля (with respect to afield) 477Вычисление (значения) полинома(evaluation of a polynomial) 34,286, 328, 476, 487, 490—491,499—500Глубина (depth) — средняя (expected)111- узла (of a vertex) 68Головка (head) 40Гомоморфизм (homomorphism) 461- сохраняющий длину (lengthpreserving) 461, 520Грамматика (grammar) —бесконтекстная (context-free) 91,401- - в нормальной форме Хомского (inChomski normal form) 91- контекстная (context-sensitive) 449Граф (graph) 64- ациклический (acyclic) 67- двусвязный (biconnected) 206- дополнительный (complement) 431- корневой (rooted) 239- неориентированный (undirected) 64- ориентированный (directed) 64- переходов см.
Диаграмма(переходов) 357- раскрашиваемый (colorable) 421- связный (connected) 70, 216, 253- сильно связный (strongly connected)216ДАННЫЕ (DATA) 99Дважды связанный (doubly linked) 61Двойственное (вычисление) (dual)496Двусвязность (biconnectivity) 206ДЕЛЕНИЕ (DIVIDE) 179, 180Деление (division) — полиномов (ofpolynomials) 320- целых чисел (of integers) 313Дерево (tree) 67- 2, 3, 169- I 386- S 386- АВЛ (AVL) 193- бинарное см. Дерево двоичное 68- вспомогательное (auxiliary) 390- двоичное (binary) 68- - полное (complete) 68- двоичного поиска (binary search)136- доминаторное (dominator) 239- корневое (rooted) 67- - неориентированное (undirected) 70- неориентированное (undirected) 70- ориентированное (directed) 67- остовное (spanning) 130- - глубинное (depth-first) 203- позиций см.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
