С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 48

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

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

P.  —.[] J. von zur Gathen, J. Gerhard. Modern computer algebra. New York:Cambrige University Press, .[] R. Kannan, R. J. Lipton. Polynomial-time algorithm for the orbitproblem // J. Assoc. Comput. Mach. . V. , № . P.  — .[] D. E.

Knuth. Big omicron and big omega and big theta // ACMSIGACT News. . V. , iss. . P.  —.[] J. C. Lagarias. The 3x + 1 problem and its generalizations // TheAmerican Mathematical Monthly. . V. , № . P.  —.[] E. P. Miles, Jr.

Generalized Fibonacci numbers and associated matrices // The American Mathematical Monthly. . V. , № .P.  —.[] R. Motwani, P. Raghavan. Randomized algorithms. Cambridge: Cambridge University Press, .[] I. Pohl. A sorting problem and its complexity // Comm. ACM. .V. , № . P. — .Литература[] E. M. Reingold, A. I. Stocks. Simple proofs of lower bounds forpolynomial evaluation // Complexity of computer computations(Proc.

Sympos., IBM Thomas J. Watson Res. Center, YorktownHeights, N. Y., ). New York: Plenum, . P. —.[] A. Schinzel, H. Zassenhaus. A refinement of two theorems ofKronecker // Michigan Math. J. . V. . P. — .[] R. Sedgewick, P. Flajolet. An introduction to the analysis of algorithms.Boston, MA: Addison-Wesley, .Предметный указательАлгоритм— Агравала—Кайала—Саксены(AKS) — бинарный возведения в степень (RS) , — Грэхема (G) , — Евклида (E) , , — — расширенный (EE) , ,— Карацубы (KM) — кратных карт — наивного деления с остатком(ND) — — умножения (NM) — оптимальный — — по порядку сложности — пробных делений (TD) , — рандомизированный , , — сложения (Add) — Тоома (TM) — Уоршелла , — Шенхаге—Штрассена — Шеймоса—Хоя (SH) — Штрассена умножения матриц(St) Асимптотики символ— o , — O , e — O— Θ , — Ω , — ∼ Задача NP-полная Затраты алгоритма (функции затрат) Класс— P — P — NP Модель вычислений , , Нижняя граница сложности — асимптотическая Оценка точная , Поиск — бинарный места элемента (BS), — наименьшего элемента , ,— наименьшего и наибольшегоэлементов , , — m-го наименьшего элементаПолиномиальная ограниченностьПринцип Яо ?Проблема P = NP , Размер входа Сегмент массива Сертификат Сводимость— линейная — полиномиальная Сложность — аддитивная Предметный указательСложность алгебраическая — битовая — в среднем — в худшем случае — временная — мультипликативная — пространственная — словесная Сортировка — быстрая (QS) , — — рандомизированная — вставками— — бинарными (B) , — — простыми (I1 , I2 ) , — выбором , ————оптимальная (opt) пузырьковая , , слияниями и вставками (F) слияниями рекурсивная (MS), , — фон Неймана (vN) , Стратегия «разделяй и властвуй»Схемы Горнера оптимальность Теорема— Кука — о рекуррентном неравенстве— Фишера—Рабина ОглавлениеПредисловие .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Наиболее часто используемые обозначения . . . . . . . . . . . . . . .358Глава . Сложности алгоритмов как функции числовых аргументов. Сложность в худшем случае§ . Затраты алгоритма для данного входа, алгебраическаясложность .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9§ . Асимптотические оценки (формализм) . . . . . . . . . . . . . 18§ . Асимптотические оценки (два примера) . . . . . . . . . . . . 23§ . Длина числа как возможный размер входа . . . . .

. . . . . 31Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Глава . Сложность в среднем§ . Понятие сложности в среднем . . . . . . . . . . . . . . . . . . . 42§ . Сортировка и конечные вероятностные пространства.Применение формулы полного математического ожидания46§ . Пример медленного роста сложности в среднем в сравнении со сложностью в худшем случае . .

. . . . . . . . . . . 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.

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

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