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

Задача данной книги проста: разобрать «идеи», лежащие в основе программ, и пока-зать, как доказывать их правильность.

Как математически доказать, что заданный алгоритм делает то, что он должен делать ? И почему это так важно ?
Доказывается правильность классических алгоритмов: целочисленного деления, алгоритм Евклида, ранжирования, др. Помимо традиционных алгоритмов, таких как жадные алгоритмы, алгоритмы динамического программирования и алгоритмы «разделяй и властвуй», книга исследует также рандомизированные и онлайновые алгоритмы. Первые стали повсеместными из-за появления криптографии, а вторые необходимы во многих областях, начиная с операционных систем и заканчивая фондовым рынком.
Книга усеяна задачами. Большинство задач теоретические, но многие требуют реализации алгоритма; для таких задач используется язык программирования Python 3. Несмотря на свою краткость, издание является математически строгим. Желательно предварительное знакомство с дискретной математикой.
Издание предназначено для студентов вузов, специалистов в области информатики и математики, а также широкого круга программистов и разработчиков.
Файлы к книге, в том числе упражнения на языке Python доступны на сайте книги, а также на сайте издательства.
Основные темы книги:

• предварительные условия;
• жадный алгоритм;
• разделяй и властвуй;
• динамическое программирование;
• онлайновые алгоритмы;
• рандомизированные алгоритмы;
• алгоритмы в линейной алгебре;
• вычислительная основа;
• математическая основа.

Об авторе:
Майкл Солтис (Michael Soltys) является профессором и заведующим кафедрой компьютерных наук Калифорнийского государственного университета на Нормандских островах, США, с 2014 года. Его научные интересы лежат в области алгоритмов, в особенности в области строковых алгоритмов и кибербезопасности. Солтис консультирует бизнес и промышленность в области цифровой криминалистики и информационной безопасности. Регулярно ведет курсы по кибербезопасности и алгоритмам.