Магазин издательства МЦНМО

Лекции о сложности алгоритмов (3-е, исправленное и дополненное)

175 ₽
  • Издательство: МЦНМО
  • ISBN: 978-5-4439-1464-0
  • Год издания: 2020
  • Тираж: 1500
  • Страниц: 256
  • Обложка: мягкая
  • Формат (мм): 140 х 215 х 10
Описание:

В книге излагаются основные (начальные) разделы теории сложности алгоритмов. Различаются алгебраическая и битовая сложности, каждая из которых рассматривается в худшем случае и в среднем. Ряд основных понятий теории сложности, как-то: оценки снизу и сверху, нижняя граница сложности алгоритмов некоторого класса, оптимальный алгоритм и т. д., рассматривается не только в обычном функциональном, но и в асимптотическом смысле: асимптотические оценки, асимптотическая нижняя граница, оптимальность по порядку сложности и т. д. Показывается, что при исследовании существования алгоритма решения задачи, имеющего «не очень высокую» сложность, важную роль может играть сводимость одной задачи к другой.

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

Для студентов, специализирующихся в области математики и информатики.

Предыдущее издание книги вышло в 2012 г.