COMPUTER ALGORITHMS: Correctness Proofs and Performance Analyses
Книга «COMPUTER ALGORITHMS: Correctness Proofs and Performance Analyses» представляет собой фундаментальное руководство по проектированию и анализу компьютерных алгоритмов. Основное внимание уделяется двум ключевым аспектам: строгому доказательству корректности алгоритмов и детальному анализу их производительности (временной и пространственной сложности). Автор, Шашанк К. Мехта, бывший профессор ИИТ Канпур, излагает материал систематично, начиная с базовых концепций и моделей вычислений.
В первой главе рассматриваются основы: упрощённая модель современных компьютеров, понятие псевдокода, а также вводятся примеры классических алгоритмов, таких как алгоритм Евклида для НОД, сортировка пузырьком и задача максимального использования ресурсов. Для каждого примера приводится не только описание, но и формальное доказательство корректности, что формирует у читателя строгий математический подход.
Значительная часть книги посвящена методам анализа эффективности. Подробно разбираются понятия размера экземпляра задачи, худшего случая, гладких и негладких функций сложности. Анализируются базовые арифметические и логические операции. Рассматриваются различные классы алгоритмов сортировки (включая сортировку слиянием, быструю сортировку, поразрядную и блочную сортировку), а также доказывается нижняя оценка для алгоритмов, основанных на сравнениях.
Книга служит мостом между теоретическими основами информатики и практическим программированием. Она предназначена для студентов, аспирантов и практикующих разработчиков, которые хотят глубоко понять, как создавать эффективные и надёжные алгоритмы, и научиться формально обосновывать их свойства.
