Разработка и анализ компьютерных алгоритмов - альфред в. ахо
Опис
В этой монографии, ставшей классикой, излагаются результаты теоретических и
прикладных исследований по разработке и анализу эффективных вычислительных
алгоритмов. Рассмотрены задачи поиска, сортировки массивов, умножения целых
чисел, умножения матриц, алгоритмы на графах, а также основы теории сложности.
Книга предназначены для специалистов по компьютерным наукам и программистов, а
также будет полезна студентам и аспирантам, специализирующимся в области
информатики.
В книге описаны фундаментальные принципы построения алгоритмов, лежащих в
основе всех компьютерных наук. В ней рассматриваются базовые структуры данных
и методики программирования, применяемые при создании эффективных алгоритмов.
В начале книги вы познакомитесь со списками, очередями, стеками, деревьями и
графами. В последующих главах исследуются методы сортировки и поиска, а также
алгоритмы на графах нахождения кратчайшего пути и алгоритмы Штрассена
умножения матриц. В конце каждой главы приведено большое количество интересных
упражнений разного уровня сложности.
Об авторах
Альфред В. Ахо — сотрудник компании Bell Telephone Laboratories в Мюррей Хилл,
шт. Нью-Джерси, председатель программного комитета по компьютерным наукам в
технологическом институте Стивенса и вице-президент специальной группы ACM по
теории автоматов и вычислительным алгоритмам. Он является автором книг The
Theory of Parsing, Translation, and Computing, Volumes 1 and 2, и Theory of
Computing.
Доктор Ахо получил степень бакалавра в университете Торонто, а магистерскую и
докторскую степени — в Принстонском университете.
Профессор факультета компьютерных наук Корнеллского университета Джон Э.
Хопкрофт является членом Национального научного фонда в области компьютерных
наук и ответственным редактором SIAM Journal of Computing. Он работал научным
консультантом в компаниях Bell Telephone Laboratories и System Development
Corporation. Доктор Хопрофт является соавтором книги Formal Languages and
Their Relations to Automata (Addison-Wesley, 1969). Он получил магистерскую и
докторскую степени в Стэнфордском университете.
Джеффри Д. Ульман — профессор электротехники в Принстонском университете.
Ранее он работал в компании Bell Telephone Laboratories. Он является соавтором
книг The Theory of Parsing, Translation, and Computing, Volumes 1 and 2 вместе
с Альфредом Ахо. Доктор Ульман получил степень бакалавра в Колумбийском
университете, а докторскую степень — в Принстонском университете.
Оглавление
Предисловие 11
Глава 1. Модели вычислений 15
Глава 2. Разработка эффективных алгоритмов 61
Глава 3. Сортировка и порядковые статистики 97
Глава 4. Структуры данных для работы с множествами 131
Глава 5. Алгоритмы на графах 199
Глава 6. Умножение матриц и связанные с ним операции 259
Глава 7. Быстрое преобразование Фурье и его применения 291
Глава 8. Арифметические операции над целыми числами и полиномами 319
Глава 9. Алгоритмы сопоставления с образцом 365
Глава 10. NP-полные задачи 419
Глава 11. Некоторые доказуемо трудноразрешимые задачи 469
Глава 12. Нижние оценки числа арифметических операций 495
Список литературы 523
Предметный указатель 537
Також шукають:
