|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[79] от предыдущих. Пусть М - максимальная длина цепочек после добавления га ключей. Ваша задача - доказать, что математическое ожидание М есть О (lg тг/ lg lg га). а. Фиксируем некоторое хеш-значение. Пусть Qk - вероятность того, ему соответствует к различных ключей. Покажите, что б.Пусть Рк - вероятность того, что максимальная длина цепочки равна к. Покажите, что Рк nQk- в.Выведите из формулы Стирлинга (2.11), что Qk < ек/кк. г.Покажите, что существует такая константа с > 1, что Qk < 1/га3 при к clgra/lglgra. Заключите отсюда, что Р < 1/га2 при таких к. д.Покажите, что математическое ожидание величины М не превосходит и выведите отсюда, что это математическое ожидание есть 0(lg га/ lg lg га). 12-4 Пример квадратичной последовательности проб Пусть нам надо поместить запись с ключом к в хеш-таблицу, ячейки которой пронумерованы числами 0,1,..., т - 1. У нас есть хеш-функция h, отображающая множество ключей в множество {0,1,..., т - 1}. Будем действовать так: 1.Находим г <- h(k) и полагаем j <- 0. 2.Проверяем позицию номер г. Если она свободна, заносим туда запись и на этом останавливаемся. 3.Полагаем j <- (j + 1) mod т и г <- (i+j) mod т и возвращаемся к шагу 2. а.Покажите, что описанный алгоритм - частный случай «квадратичного метода» для подходящих значений с\ и с2. Предположим, что т является степенью двойки. б.Покажите, что в худшем случае будет просмотрена вся таблица. 12-5 /г-универсальное хеширование Пусть И - семейство хеш-функций, отображающих множество возможных ключей U в {0,1,..., т - 1}. Будем говорить, что И является /г-универсальным, если для любой последовательности к различных ключей (xi,...,Xk) случайная величина (h(xi),..., h(xk)) (где h - случайный элемент %) принимает все тк своих возможных значений с равными вероятностями. а.Покажите, что всякое 2-универсальное семейство универсально. б.Покажите, что семейство 7i, описанное в разделе 12.3.3, не является 2-универсальным. в.Расширим семейство И из разд. 12.3.3 и рассмотрим всевозможные функции вида ha<b(x) = ha(x) + b mod то, где b - некоторый вычет по модулю то. Покажите, что полученное семейство будет 2-универсальным. Замечания Алгоритмы хеширования прекрасно изложены у Кнута [123] и Гоннета [90]. Согласно Кнуту, хеш-таблицы и метод цепочек были изобретены Луном (Н.Р. Luhn) в 1953 году. Примерно в то же время Амдаль (G.M.Amdahl) изобрёл открытую адресацию. Двоичные деревья поиска Деревья поиска (search trees) позволяют выполнять следующие операции с динамическими множествами: Search (поиск), Minimum (минимум), Maximum (максимум), Predecessor (предыдущий), Successor (следующий), Insert (вставить) и Delete (удалить). Таким образом, дерево поиска может быть использовано и как словарь, и как очередь с приоритетами. Время выполнения основных операций пропорционально высоте дерева. Если двоичное дерево «плотно заполнено» (все его уровни имеют максимально возможное число вершин), то его высота (и время выполнения операций) пропорциональны логарифму числа вершин. Напротив, если дерево представляет собой линейную цепочку из га вершин, это время вырастает до О(га). В разделе 13.4 мы увидим, что высота случайного двоичного дерева поиска есть О (lgra), так что в этом случае время выполнения основных операций есть 0(lgга). Конечно, возникающие на практике двоичные деревья поиска могут быть далеки от случайных. Однако, приняв специальные меры по балансировке деревьев, мы можем гарантировать, что высота деревьев с га вершинами будет О (log га). В главе 14 рассмотрен один из подходов такого рода (красно-чёрные деревья). В главе 19 рассматриваются Б-деревья, которые особенно удобны для данных, хранящихся во вторичной памяти с произвольным доступом (на диске). В этой главе мы рассмотрим основные операции с двоичными деревьями поиска и покажем, как напечатать элементы дерева в неубывающем порядке, как искать заданный элемент, как найти максимальный или минимальный элемент, как найти элемент, следующий за данным и предшествующий данному, и, наконец, как добавить или удалить элемент. Напомним, что определение дерева и основные свойства деревьев приводятся в главе 5. |
Среды: 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 | ||