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

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

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

Алексеев. Введение в теорию сложности алгоритмов: Учебное пособие для студентов. М.: Издательский отдел ф-та ВМиКМГУ, .[] А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.: Мир, .[] Н. Г. де Брейн.

Асимптотические методы в анализе. М.: ИЛ, .[] А. А. Васин, В. В. Морозов. Теория игр и модели математическойэкономики. Учебное пособие. М.: МАКС Пресс, .[] Введение в криптографию / Под общей редакцией В. В. Ященко.М.: МЦНМО: ЧеРо, .[] Н. К. Верещагин, А. Шень. Начала теории множеств. М.: МЦНМО,.[] М.

Н. Вялый. Сложность вычислительных задач // Математическое просвещение, вып. . M.: МЦНМО, . С. —.[] С. Б. Гашков, В. Н. Чубариков. Арифметика. Алгоритмы. Сложность вычислений. М.: Высшая школа, .[] А. О. Гельфонд. Исчисление конечных разностей. М.: Наука, .Литература[] М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи.

М.: Мир, .[] В. А. Ильин, Г. Д. Ким. Линейная алгебра и аналитическая геометрия. М.: Изд-во Моск. ун-та, .[] А. А. Карацуба, Ю. П. Офман. Умножение многозначных чисел наавтоматах // Докл. АН СССР. . Т. , № . С.  —.[] А.

А. Карацуба. Основы аналитической теории чисел. М.: Наука,.[] А. А. Карацуба. Сложность вычислений // Труды Математического института РАН. . Т. . С.  —.[] Д. Кнут. Искусство программирования для ЭВМ. Т. . Основныеалгоритмы. М.—СПб.—Киев: ИД «Вильямс», .[] Д. Кнут. Искусство программирования для ЭВМ. Т. . Получисленные алгоритмы. М.—СПб.—Киев: ИД «Вильямс», .[] Д.

Кнут. Искусство программирования для ЭВМ. Т. . Сортировка и поиск. М.—СПб.—Киев: ИД «Вильямс», .[] Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, .[] А. И. Кострикин. Введение в алгебру. М.: Наука, .[] В. H. Крупский. Введение в сложность вычислений. М.: Факториал-Пресс, .[] С. С. Лавров. Программирование. Математические основы, средства, теория. СПб: БХВ-Петербург, .[] В. H. Латышев. Комбинаторная теория колец: сложность алгебраических алгоритмов.

М.: Изд-во Моск. ун-та, .[] Дж. Макконелл. Анализ алгоритмов. Вводный курс. М.: Техносфера, .[] Ф. Мостеллер.  занимательных вероятностных задач с решениями. М.: URSS, .[] А. М. Островский. Решение уравнений и систем уравнений. М.:ИЛ, .Литература[] В. В. Прасолов. Многочлены. М.: МЦНМО, .[] Ф. Препарата, М. Шеймос. Вычислительная геометрия: введение.М.: Мир, .[] Э. Рейнгольд, Ю. Нивергельт, Н. Део.

Комбинаторные алгоритмы.Теория и практика. М.: Мир, .[] В. К. Романко. Разностные уравнения. М.: БИНОМ. Лабораториязнаний, .[] А. А. Сапоженко. Некоторые вопросы сложности алгоритмов:учебное пособие. М.: Издательский отдел ф-та ВМиК МГУ, .[] А. Г.

Свешников, А. Н. Тихонов. Теория функций комплексной переменной. М.: Физматлит, .[] В. Серпинский.  задач по теории чисел. Москва—Ижевск: Регулярная и хаотическая динамика, .[] А. Л. Тоом. О сложности схемы из функциональных элементов,реализующей умножение целых чисел // Докл. АН СССР. .Т. , № . С.  — .[] Дж. Хартманис, Дж. Э. Хопкрофт. Обзор теории сложности //Кибернетический сборник.

. Вып. . С. —.[] П. Л. Чебышев. Полное собрание сочинений. Т. . М.—Л.: АНСССР, .[] И. Р. Шафаревич. Избранные главы алгебры. М.: Журнал «Математическое образование», .[] Математическая энциклопедия. Т. . М.: Издательство «Советская энциклопедия», .[] S. A. Abramov, M. Bronstein. Hypergeometric dispersion and the orbitproblem // Proceedings of the  International Symposiumon Symbolic and Algebraic Computation. New York: ACM, .P.

 —.[] M. Agrawal, N. Kayal, N. Saxena. PRIMES is in P // Ann. of Math.(). . V. , № . P. —.[] S. Baase, A. van Gelder. Computer algorithms: introduction to designand analysis. Boston, MA: Addison-Wesley, .Литература[] E. Bach, J.

Shallit. Algorithmic number theory. V. . Efficientalgorithms. Cambridge, MA: MIT Press, .[] P. E. Blanksby, H. L. Montgomery. Algebraic integers near the unitcircle // Acta Arith. . V. . P.  —.[] G. Brassard, P. Bratley. Fundamentals of algorithms. EnglewoodCliffs, NJ: Prentice Hall, .[] D. Coppersmith, S. Winograd.

Matrix multiplication via arithmeticprogressions // J. Symbolic Comput. . V. , № . P. —.[] M. J. Fischer, M. O. Rabin. Super-exponential complexity of Presburgerarithmetic // Complexity of computation (Proc. SIAM-AMS Sympos.,New York, ). Providence, RI: AMS, . (SIAM-AMS Proc.;Vol. VII). P. — .[] N.

Friedman. Some results on the effect of arithmetics on comparisonproblems // Proc. th IEEE Ann. Symp. on Switching and AutomataTheory. Los Alamitos, CA: IEEE Computer Society, . 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§ . Пример медленного роста сложности в среднем в сравнении со сложностью в худшем случае . . .

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

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