|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[15] 3.2-3 Разбивая сумму на части, покажите, что п-я частичная сумма гармонического ряда есть fi(lgn). 3.2-4 Заключите сумму Ук=1 к3 между двумя интегралами. 3.2-5 Почему при получении верхней оценки для частичной суммы гармонического ряда мы отбросили первый член и только потом применили оценку (3.10)? Задачи 3-1 Оценки для сумм Найдите асимптотически точные оценки для следующих сумм (считая г ) 0 и s ) 0 константами): Замечания Книга Кнута [121] - прекрасный справочник по материалу этой главы. Основные свойства рядов можно найти в любом учебнике по математическому анализу (авторы отсылают англоязычного читателя к книгам [12] и [192]). Рекуррентные соотношения Оценивая время работы рекурсивной процедуры, мы часто приходим к соотношению, которое оценивает это время через время работы той же процедуры на входных данных меньшего размера. Такого рода соотношения называются рекуррентными (recurrences). Например, как мы видели в главе 1, время работы процедуры Merge-Sort описывается соотношением I 21 (п/2) + О(га), если га > 1. из которого вытекает (как мы увидим), что Т(п) = ©(гаlgra). В этой главе предлагаются три способа, позволяющие решить рекуррентное соотношение, т.е. найти асимптотическую («О» или «О») оценку для его решений. Во-первых, можно угадать оценку, а затем доказать её по индукции, подставляя угаданную формулу в правую часть соотношения (метод подстановки, substitution method). Во-вторых, можно «развернуть» рекуррентную формулу, получив при этом сумму, которую можно затем оценивать (метод итераций, iteration method). Наконец, мы приводим общий результат о рекуррентных соотношениях вида Т(п) = аТ(п/Ъ) + /(га), где а 1, Ь > 1 - некоторые константы, а /(га) - заданная функция. Соответствующий результат мы будет называть основной теоремой о рекуррентных соотношениях (master theorem). Формулировка этой теоремы довольно длинна, зато во многих случаях она сразу приводит к ответу. Технические детали Формулируя и доказывая утверждения про рекуррентные соотношения, мы будем опускать некоторые технические подробности. Например, в приведённой выше формуле для процедуры Merge- Sort должны стоять целые части (Т(п) определено лишь при целых га): т/ .0(1),если га = 1,. Т п) = <4 2) KJ \ Т(\п/2]) + Т([п/2\) + в(п), если га > 1.V7 Кроме того, обычно мы будем опускать начальные условия, имея в виду, что Т(п) = 0(1) для небольших га. Таким образом, соотношение (4.1) запишется в виде Г(га) = 2Г(га/2) + 0(га).(4.3) Это позволительно, так как начальное условие (значение Т(1)) влияет только на постоянный множитель, но не на порядок роста функции Т{п). Такое небрежное обращение с деталями, конечно, требует осторожности, чтобы не упустить (пусть редких) случаев, в которых подобные детали влияют на результат. В этой главе мы разберём несколько примеров, показывающих, как восполнить пропущенные детали (см. доказательство теоремы 4.1 и задачу 4.5). 4.1. Метод подстановки Идея проста: отгадать ответ и доказать его по индукции. Часто ответ содержит коэффициенты, которые надо выбрать так, чтобы рассуждение по индукции проходило. Индуктивный метод применим и к нижним, и к верхним оценкам. В качестве примера найдём верхнюю оценку для функции, заданной соотношением Г(га) = 2T([ra/2j) + га,(4.4) которое аналогично (4.2) и (4.3). Можно предположить, что Т(п) = O(ralgra), т.е. что Т(п) cralgra для подходящего с > 0. Будем доказывать это по индукции. Пусть эта оценка верна для га/2 , т.е. T([ra/2j) c[ra/2j lg([ra/2j). Подставив её в соотношение, получим Г(га) 2(cLra/2j lg(n/2j)) + га <С era lg (та/2) + га = era lg га - era lg 2 + га = era lg га - era + га era lg ra. Последний переход законен при с 1. Для завершения рассуждения остаётся проверить базис индукции, т. е. доказать оценку для начального значения га. Тут мы сталкиваемся с тем, что при га = 1 правая часть неравенства обращается в нуль, каким бы ни взять с (поскольку lg 1 = 0). Приходится вспомнить, что асимптотическую оценку достаточно доказать |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||