ISBN: 978-5-4439-0204-3
Внешнее покрытие издания: в обл.
Тираж издания: 1500
Фамилия автора в заголовке: Абрамов
Инициалы автора (личного имени (имен)): С. А.
Код отношений (роль соавтора в издании): 070 Автор
Основное заглавие: Лекции о сложности алгоритмов
Первые сведения об ответственности: С. А. Абрамов
Сведения об издании: 2-е изд.
Дополнительные сведения об издании: перераб.
Место издания: Москва
Издатель: МЦНМО
Дата издания: 2012
Объем издания (количество страниц): 245
Высота, см.: 22
Полная форма имени (имен) и отчества: Сергей Александрович
Индекс УДК: 510.52
Статус записи (Тип информации): В наличии
Ширина, см: 14,3
Толщина, см: 1,1
Вес в граммах: 260
Индекс ББК: 22.12
Артикул: 2400253
Аннотация:

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

Читайте также: