Разработка и анализ компьютерных алгоритмов - Альфред В. Ахо

В этой монографии, ставшей классикой, излагаются результаты теоретических и прикладных исследований по разработке и анализу эффективных вычислительных алгоритмов. Рассмотрены задачи поиска, сортировки массивов, умножения целых чисел, умножения матриц, алгоритмы на графах, а также основы теории сложности. Книга предназначены для специалистов по компьютерным наукам и программистов, а также будет полезна студентам и аспирантам, специализирующимся в области информатики.В книге описаны фундаментальные принципы построения алгоритмов, лежащих в основе всех компьютерных наук. В ней рассматриваются базовые структуры данных и методики программирования, применяемые при создании эффективных алгоритмов. В начале книги вы познакомитесь со списками, очередями, стеками, деревьями и графами. В последующих главах исследуются методы сортировки и поиска, а также алгоритмы на графах нахождения кратчайшего пути и алгоритмы Штрассена умножения матриц. В конце каждой главы приведено большое количество интересных упражнений разного уровня сложности.Об авторахАльфред В. Ахо — сотрудник компании 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