Как доказать, что заданный алгоритм делает то, что он должен делать? Ключевые идеи индукции и инвариантности. Стандартные методы проектирования: жадные алгоритмы, динамическое программирование и парадигма «разделяй и властвуй». Математическая основа алгоритмов. Расширенные алгоритмы. Задания с предельными сроками. Онлайновые алгоритмы. Шифрование с публичным ключом. Решение оптимизационных задач. Задача данной книги проста: разобрать «идеи», лежащие в основе программ, и показать, как доказывать их правильность. Как математически доказать, что заданный алгоритм делает то, что он должен делать? И почему это так важно? Доказывается правильность классических алгоритмов: целочисленного деления, алгоритм Евклида, ранжирования, др. Помимо традиционных алгоритмов, таких как жадные алгоритмы, алгоритмы динамического программирования и алгоритмы «разделяй и властвуй», книга исследует также рандомизированные и онлайновые алгоритмы. Первые стали повсеместными из-за появления криптографии, а вторые необходимы во многих областях, начиная с операционных систем и заканчивая фондовым рынком. Книга усеяна задачами. Большинство задач теоретические, но многие требуют реализации алгоритма; для таких задач используется язык программирования Python 3. Несмотря на свою краткость, издание является математически строгим. Желательно предварительное знакомство с дискретной математикой. Издание предназначено для студентов вузов, специалистов в области информатики и математики, а также широкого круга программистов и разработчиков.
Федеральное государственное бюджетное учреждение культуры «Российская государственная библиотека для молодёжи»
Главное здание
107061 Москва, ул. Б. Черкизовская, дом 4, корпус 1 Метро «Преображенская площадь» (выход №5) Телефон для справок: +7 499 670-80-01 E-mail: info@rgub.ru
Филиал библиотеки — ИКК «Особняк В.Д. Носова»
107023 Москва, ул. Электрозаводская, 12, стр. 1 Метро «Электрозаводская» Телефоны для справок: +7 499 670-80-01 (доб. 600) E-mail: mansion@rgub.ru
![Брукс Ф., Мифический человеко-месяц, или Как создаются программные системы. [очерки о программной инженерии] — 2022 (Библиотека программиста)](/searchcat/covers/RGUB-BIBL-0000912921.jpg)
