Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 50

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 50)

. . . . . . . . . . 53§ . Функция затрат рандомизированного алгоритма . . . . . . 58Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Глава . Оценивание числа шагов (итераций) алгоритма§ . Функции, убывающие по ходу выполнения алгоритма .§ .

Качество оценок . . . . . . . . . . . . . . . . . . . . . . . . . . .§ . Завершимость работы алгоритма . . . . . . . . . . . . . . . .§ . Вложенные циклы (дополнительные примеры) . . . . . .§ . Нецелые размеры входа и непрерывные оценочныефункции . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .....74838995. 97100Глава . Нижняя граница сложности алгоритмов некоторого класса. Оптимальные алгоритмы§ . Понятие нижней границы сложности . . . . . . .

. . . . . . 106§ . Оптимальные алгоритмы . . . . . . . . . . . . . . . . . . . . . 109Оглавление§ . Асимптотические нижние границы. Алгоритм, оптимальный по порядку сложности . . . . . . . . . . . . . . . . .§ . Нижняя граница сложности в среднем . . . . . . . . . . . .§ .

Нижние границы сложности рандомизированных алгоритмов. Принцип Яо . . . . . . . . . . . . . . . . . . . . . . . .Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Глава . Битовая сложность§ . Битовые операции . .

. . . . . . . . . . . . . . .§ . Наивная арифметика: умножение . . . . . .§ . Наивная арифметика: деление с остатком .§ . Модулярная арифметика . . . . . . . . . . . . .§ . Булева арифметика . . . . . . . . . . . . . . . .Задачи . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .......................................................114118126129133137140145150154Глава . Рекуррентные соотношения как средство анализа сложности алгоритмов§ . Простейшие рекуррентные уравнения . . . . . . . . . . . . . 158§ . Об одном классе нелинейных рекуррентных соотношений163§ .

Асимптотические оценки решений рекуррентных неравенств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169§ . Добавление нулей . . . . . . . . . . . . . . . . . . . . . . . . . . 172Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . 181Глава . Сводимость§ . Линейная сводимость . . . . . . . . . . . . . . . . . . . . . . . .§ . Линейная сводимость и нижние границы сложности . .§ . Классы P и NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .§ . Существование задач распознавания, не принадлежащих P. Связь моделей МТ и РАМ . . . . . .

. . . . . . . . . .§ . Полиномиальная сводимость. NP-полные задачи . . . . .Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .185190195201204209Приложение A. Основные алгоритмы сортировки и поиска . . . 214Приложение B. Оценивание сумм значений монотонных функций 218Приложение C. Проблема орбит . .

. . . . . . . . . . . . . . . . . . . . 221Приложение D. Оптимальность схемы Горнера . . . . . . . . . . . . 227Приложение E. Об одном свойстве сумм неотрицательных случайных величин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233Приложение F. О сортировке, оптимальной по числу сравненийв худшем случае . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . 236ОглавлениеПриложение G. Метод построения общего решения линейного рекуррентного уравнения с постоянными коэффициентами . . . 238Приложение H. Об одном семействе алгебраических уравнений 240Литература . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248Сергей Александрович АбрамовЛåêöèè î ñëîæíîñòè àëãîðèòìîâИздательство Московского центранепрерывного математического образования, Москва, Большой Власьевский пер., . Тел. () --Подписано в печать .. г. Формат 60×90 /.

Бумага офсетная.Печать офсетная. Печ. л. . Тираж . Заказ.Отпечатано с готовых диапозитивов в ППП «Типография „Наука“»., Москва, Шубинский пер., д. .Книги издательства МЦНМО можно приобрести в магазине «Математическая книга»,Большой Власьевский пер., д. . Тел. () --. E-mail: biblio@mccme.ru.

Характеристики

Список файлов лекций