Математические методы анализа алгоритмов, Грин Д., Кнут Д., 1987

Математические методы анализа алгоритмов, Грин Д., Кнут Д., 1987.

   Оригинальное и нестандартное изложение известных методов анализа алгоритмов, написанное крупным американским специалистом Д. Кнутом в соавторство с Д. Грином. В книге представлены: комбинаторные тождества, рекуррентные соотношения, асимптотические представления, От читателя требуется знакомство с основами теории вероятностей, комбинаторного анализа и теории функций комплексного переменного.
Для системных программистов, математиков-прикладников, аспирантов и студентов университетов.




Соотношения с функциями максимума или минимума.
При решении рекуррентного соотношения с mах- или min-функциями прежде всего важно знать, где достигается максимум или минимум. Это не всегда очевидно, поскольку max- или min-функции могут зависеть от предыдущих членов последовательности, вид которых первоначально неизвестен. Типичный подход состоит в вычислении с помощью рекуррентного соотношения первых членов последовательности до тех пор, пока мы не сможем сделать предположение о местоположении максимума (или минимума) на каждой итерации. Сделанное предположение используется для решения рекуррентного соотношения, а полученное решение — для индуктивности доказательства правильности предположения.

Проиллюстрируем этот подход следующим примером анализа алгоритма перестановки на том же месте (Кнут (72); см. также Кнут (I, разд. 1.3.3]. — Перев.). Кратко говоря, данная задача возникает при анализе одного варианта алгоритма, который с целью выявления лидеров цикла осуществляет поиск одновременно в двух направлениях. Для некоторого j алгоритм вначале рассматривает p(j) и р-1 (j), затем p2(j) и p-2(j) и т. д. до тех пор, пока не встретится либо элемент, меньший чем j (в этом случае j не является лидером цикла (и отклоняется. — Ред.)), либо само j (в этом случае j является лидером цикла, поскольку весь цикл уже просмотрен).

ОГЛАВЛЕНИЕ.
От редактора и переводчика.
К русскому изданию.
Предисловие.
1. БИНОМИАЛЬНЫЕ ТОЖДЕСТВА.
1.1. Сводка полезных тождеств.
1.2. Вывод тождеств.
1.3. Обратимые соотношения.
1.4. Операторное исчисление.
1.5. Гипергеометрический ряд.
1.6. Тождества с гармоническими числами.
2. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ.
2.1. Линейные рекуррентные соотношения.
2.1.1. Частичная предыстория.
2.1.1.1. Постоянные коэффициенты.
2.1.1.2. Переменные коэффициенты.
2.1.2. Полная предыстория.
2.1.2.1. Вычитание.
2.1.2.2. Из репертуара.
2.2. Нелинейные рекуррентные соотношения.
2.2.1. Соотношения с функциями максимума или минимума.
2.2.2. Непрерывные дроби и другие скрытые линейные рекуррентные соотношения.
2.2.3. Дважды экспоненциальные последовательности.
3. ОПЕРАТОРНЫЕ МЕТОДЫ.
3.1. Монстр — пожиратель печенья.
3.2. Срастающееся хеширование.
3.3. Открытая адресация: равномерное хеширование.
3.4. Открытая адресация: вторичное скучивание.
4. АСИМПТОТИЧЕСКИЙ АНАЛИЗ.
4.1. Основные понятия.
4.1.1. Обозначения.
4.1.2. Раскрутка.
4.1.3. Расчленение.
4.1.4. Пределы пределов.
4.1.5. Сводка полезных асимптотических разложений.
4.1.6. Пример.
4.2. Интегрирование по Стилтьесу и асимптотике.
4.2.1. Символ О и интегралы.
4.2.2. Формула суммирования Эйлера.
4.2.3. Теоретико-числовой пример.
4.3. Асимптотики из производящих функций.
4 3.1. Метод Дарбу.
4.3.2. Метод вычетов.
4.3.3. Метод перевала.
ЗАДАЧИ.
РЕШЕНИЯ ЗАДАЧ.
ПРИМЕЧАНИЯ РЕДАКТОРА И ПЕРЕВОДЧИКА ЛИТЕРАТУРА.
Д.Э. Кнут и его «фабрика книг» (дополнение переводчика).  
Указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Математические методы анализа алгоритмов, Грин Д., Кнут Д., 1987 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Грин :: Кнут