|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[42] Задачи к главе 6 135 сваивание в строке 5. Предполагается, что числа в массиве А различны и расположены в случайном порядке (все перестановки равновероятны). а.Если число х случайно выбрано из г различных чисел, то с какой вероятностью оно окажется максимальным числом среди них? б.Как соотносится A[i] с предыдущими элементами массива для тех г, при которых выполняется строка 5? в.Чему равна вероятность выполнения строки 5 программы для данного значения г? г.Пусть Si - случайная величина, равная 1 или 0 в зависимости от того, выполнялась строка 5 на г-м шаге цикла или нет. Чему равно M[s4-]? д.Пусть s = S1+S2 + - • -+sn - общее число присваиваний в строке 5 при исполнении всей программы. Покажите, что M[s] = O(lgra). 6-3 Проблема выбора Заведующая кафедрой принимает на работу нового сотрудника. Она назначила собеседования га претендентам и хочет выбрать наиболее квалифицированного из них. Однако университетские правила требуют, чтобы после беседы претенденту сразу сообщалось, принят он или нет. Для этого она применяет такое правило. Сначала она говорит с первыми к претендентами, отказывая им независимо от их квалификации. Если среди оставшихся есть более квалифицированный, чем первые к, то первый из таковых принимается. Если нет, принимается последний из претендентов. Покажите, что вероятность выбрать таким способом лучшего из претендентов будет максимальна (и равна примерно 1/е), если к примерно равно га/е. 6-4 Вероятностный счётчик С помощью -битного счётчика мы можем считать до 2* - 1. Следующий приём вероятностного подсчёта (probabilistic counting, R. Morris) даёт возможность вести счёт до куда больших значений, правда ценою некоторой потери точности. Выберем возрастающую последовательность целых неотрицательных чисел щ (где г меняется от 0 до 2* - 1). Её смысл таков: если значение -битного регистра равно г, то это означает, что подсчитываемое количество (число выполненных операций Increment) примерно равно гц. Мы считаем, что щ = 0. Операция Increment увеличивает значение счетчика, содержащего г, с некоторой вероятностью. Именно, число г увеличивается на 1 с вероятностью 1/(гаг+1 -щ), и остается неизменным в остальных случаях. (Если г = 2* - 1, то происходит переполнение.) Идея проста: в среднем для увеличения г на единицу потребуется как раз гаг 1 - щ операций. Если гц = г для всех г 0, то получаем обычный счётчик. Более интересные ситуации возникают, если выбрать, например, гц = 28-1 для г > 0 или гц = Fi (г-е число Фибоначчи, см. разд. 2.2). Мы будем предполагать, что гг2* 1 достаточно велико, и пренебрегать возможностью переполнения. а.Покажите, что математическое ожидание содержимого счётчика после выполнения п операций Increment, в точности равно п. б.Дисперсия случайной величины, равной содержимому счётчика после п операций Increment, зависит от выбора последовательности по,щ,.... Найдите эту дисперсию для случая гц = 100г. Замечания Общие методы решения вероятностных задач обсуждались в знаменитой переписке Паскаля (B.Pascal) и Ферма (P.de Fermat), начавшейся в 1654 году, и в книге Гюйгенса (C.Huygens, 1657). Более строгое изложение теории вероятностей было дано в работах Бернулли (J.Bernoulli, 1713) и Муавра (A.De Moivre, 1730). Дальнейшее развитие теории вероятностей связано с именами Лапласа (P. S.de Faplace), Пуассона (S.-D. Poisson) и Гаусса (C.F.Gauss). Суммы случайных величин исследовались П. Л. Чебышёвым и А.А.Марковым (старшим). В 1933 году А.Н.Колмогоров сформулировал аксиомы теории вероятностей. Оценки хвостов распределений приводят Чернов [40] и Хофдинг [99]. Важные результаты о случайных комбинаторных структурах принадлежат Эрдёшу (P. Erd6s). Литература по теме главы: Кнут [121], Лю [140] (хорошие пособия по элементарной комбинаторике и подсчету); Биллингсли [28], Чанг [41], Дрейк [57], Феллер [66], Розанов [171] (стандартные учебники по теории вероятностей); Боллобас [30], Хофри [100], Спенсер [179] (техника вероятностного анализа). |
Среды: 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 | ||