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

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