|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[85] Рассмотрим (ср. главу 5, упр. 5.5-6) сумму глубин d(x,T) всех вершин х дерева Г, которую мы будем обозначать Р(Т). а. Средняя глубина вершины в дереве Г есть 1ф,г) = 1р(г). га хет Таким образом, надо показать, что математическое ожидание Р(Т) есть О (га lgra). б. Обозначим через Tl и Tr левое и правое поддеревья дерева Т. Убедитесь, что если Г содержит га вершин, то Р(Т) = P(TL) + P(TR) + п - 1. е. Обозначим через Р(п) математическое ожидание внутренней суммы длин для случайного двоичного дерева поиска с га вершинами. Покажите, что Р(п) = -+ Р(п - i - 1) + га - 1). П г=0 г.Покажите, что 2 п~Х Р(п) = - Р{к) + @{п). П к=1 д.Вспоминая рассуждение из раздела 8.4.2 (оценка математического ожидания времени быстрой сортировки), покажите, что Р(га) = О (га lgra). В каждом рекурсивном вызове быстрой сортировки мы случайным образом выбираем граничный элемент. Подобно этому, каждая вершина дерева поиска является границей между левым и правым своим поддеревом. е.Опишите реализацию алгоритма быстрой сортировки, при котором в процессе сортировки элементов к\,..., кп выполняются в точности те же сравнения, что и при добавлении их в (изначально пустое) дерево. (Порядок сравнений может быть другим.) 13-4 Количество разных двоичных деревьев Обозначим через Ьп количество различных двоичных деревьев с га вершинами. В этой задаче требуется вывести формулу для Ьп и оценить скорость роста числа Ьп. а.Покажите, что 60 = 1 и что п-1 К = Е Фп-1-k к=0 при га 1. б.Пусть В(х) - производящая функция оо В{х) = Ьпхп п=0 (определение производящих функций дано в задаче 4-6). Покажите, что В(х) = хВ(х)2 + 1 и, таким образом, В{х) = -L(i-vT4). Ряд Тейлора (Taylor expansion) функции f(x) в точке х = а определяется формулой к=0 где f(k\a) - к-я производная / в точке а. е. Покажите, что разложив в ряд Тейлора функцию \J\ - Ах в точке 0. (Ряд для \/l + h = (1 + /г)1/2 можно получить также как обобщение бинома Ньютона, если для нецелых га и целых неотрицательных к положить Ск = п(п - 1) ... (га - к + 1)/к\.) Число Ьп называется га-м числом Каталана (Catalan number). г. Покажите, что Ьп = --(1 + 0(1/п)). Замечания Подробное обсуждение двоичных деревьев поиска и многих аналогичных структур данных можно найти у Кнута [123]. Видимо, двоичные деревья поиска были независимо придуманы многими людьми незадолго до 1960 года.
(б) Рис. 13.5 Множества Gj и Lj, составляющие множество ключей на пути к ключу kj = 17. (а) Черные вершины содержат ключи из Gj, белые из Lj, остальные вершины - серые. Выделен путь к ключу kj. Ключи левее пунктирной линии меньше kj, ключи правее - больше, (б) Множество G3 = {21, 25, 19, 29} состоит из ключей, добавленных раньше ключа 17 и больших 17. Множество Gj = {21, 19} содержит ключи, бывшие ближайшими справа к ключу 17, то есть бывшие минимальными в уже появившейся части Gj. Ключ 21 был добавлен первым к Gj и попал в Gj; ключ 25 не попал (он больше текущего минимума, равного 21). Ключ 19 попадает в Gj, потому что он меньше 21, а 29 - нет, так как 29 > 19. Множества Lj и L3 строятся аналогичным образом. |
Среды: 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||