Введение в анализ алгоритмов

Книга представляет собой краткое введение в анализ алгоритмов с точки зрения доказывания правильности алгоритма. Как математически, без бремени чрезмерного формализма, доказывать, что заданный алгоритм делает то, что он должен делать? И почему это так важно?

Автор: Майкл Солтис Издательство: ДМК Пресс Год издания: 2016 Количество страниц: 278 ISBN: 978-5-97060-696-4 Цена: 899 руб.

Инженеры по ПО знают много примеров того, когда дела принимают ужасный оборот из-за программных ошибок; их конкретными фаворитами являются следующие два из них. ПО – это большая часть проблемы. Мы должны писать ПО, которое имеет гораздо меньше ошибок и является гораздо безопасным.

Безопасность ПО естественным образом относится к правильности ПО как ее составная часть. В то время как цель правильности программы неуловима, мы можем разработать методы и приемы для сокращения ошибок.

Задача этой книги представить введение в анализ алгоритмов – «идеи», лежащие в основе программ, и показать, как доказывать их правильность. Алгоритм может быть правильным, но сама реализация может быть ошибочной. Некоторые синтаксические ошибки в реализации программы могут быть обнаружены компилятором или транслятором, которые, в свою очередь, также сами могут быть дефектными, но могут быть и другие скрытые ошибки. Само оборудование может быть неисправным; библиотеки, на которые опирается программа во время выполнения, могут быть ненадежными и т. д. Основная задача программиста – писать исходный код, который работает в условиях такой непрочной, подверженной ошибкам среды. Наконец, алгоритмическое содержимое компонента ПО может быть очень малым; большинство строк исходного кода может быть посвящено «черновой» задаче программирования интерфейса, рандомизированные алгоритмы вместе с разделом по криптографии.

Книга содержит большое количество теоретических задач и практических примеров на языке Python. Издание предназначено для студентов вузов, специалистов в области информатики и математики, а также широкого круга программистов и разработчиков.