Вопросы об алгоритмах, поведение которых определяется не только его вводом, но и источником случайных чисел.
У меня есть два способа составить список предметов в случайном порядке, и я хотел бы определить, являются ли они одинаково справедливыми (беспристрастными). Первый метод, который я использую, состоит в том, чтобы создать весь список элементов, а затем выполнить случайное перемешивание (скажем,...
Обычные алгоритмы сортировки обычно используют набор данных для сортировки и функцию сравнения, которая может сравнивать два отдельных элемента. Если компаратор представляет собой отношение порядка¹, то результатом алгоритма является отсортированный список / массив. Мне интересно, однако, какие...
Предположим, что у нас есть черный ящик который мы можем запросить и сбросить. Когда мы сбрасываем , состояние для устанавливается произвольно выбранному элементу из набора где фиксировано и известно для данного . Для запроса предоставляется элемент (предположение) из , а возвращаемое значение...
Есть ли в проблемы, в которых рандомизированные алгоритмы бьют нижние оценки для детерминированных алгоритмов? Конкретнее, знаем ли мы для которого ? Здесь \ mathsf {PTIME} (f (n)) означает набор языков, разрешимых рандомизированным TM с постоянной (одной или двухсторонней) ошибкой в f (n) шагах. k...
Алгоритм Рамер-Дуглас-Peucker для упрощения линии имеет наихудший среда выполнения. Для правильно распределенных случайных входов ожидаемая сложность времени выполнения . В 2D есть другие алгоритмы со сложностью времени выполнения худшем случае , которые вычисляют точно такой же результат, что и...
В своей книге Рандомизированных алгоритмы , Motwani и Raghavan открыть введение с описанием их функции RandQS - Рандомизированная - где быстрой сортировкой стержень, используемый для разделения множества на две части, выбирается случайным образом . В течение некоторого времени я ломал свои мозги...
Учитывая смещенную NNN стороннюю матрицу, как можно случайное число в диапазоне [1,N][1,N][1,N]равномерно генерировать N ] ? Распределение вероятностей граней матрицы неизвестно, все, что известно, это то, что каждая грань имеет ненулевую вероятность и что распределение вероятности одинаково для...
Вы и друг потеряли друг друга в очереди на концерт, и никто не уверен, кто из вас еще впереди. Формально каждый из них имеет некоторую целочисленную координату и может идти только к более высокой координате или оставаться на месте. Предполагая, что вы и ваш друг придерживаетесь одного и того же...
Я читал эту книгу для своего класса рандомизированных алгоритмов. В этой конкретной книге есть целый раздел, посвященный поиску медианы массива с использованием случайного выбора, что приводит к более эффективному алгоритму. Теперь я хотел бы знать, есть ли какие-либо практические применения этого...
Из Википедии о рандомизированных алгоритмах Нужно различать алгоритмы, которые используют случайный ввод для уменьшения ожидаемого времени работы или использования памяти, но всегда заканчивают с правильным результатом в ограниченное время, и вероятностные алгоритмы , которые, в зависимости от...
Алгоритм рандомизированного выбора следующий: Входные данные: массив из n (различных, для простоты) чисел и числа k ∈ [ n ]AAAnnnk∈[n]k∈[n]k\in [n] Выходные данные: « элемент ранга » в A (т. Е. Элемент в позиции k, если A был отсортирован)kkkAAAkkkAAA Метод: Если в есть один элемент , верните...
Рассмотрим последовательность из nnn бросков несмещенной монеты. Пусть HiHiH_i обозначает абсолютное значение превышения количества голов над хвостами, которые были замечены в первом iii броске. Определить H=maxiHiH=maxiHiH=\text{max}_i H_i . Покажите, что E[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta (...
У Алисы, студентки, есть много домашней работы в течение следующих недель. Каждый предмет домашнего задания занимает у нее ровно один день. Каждый элемент также имеет крайний срок и отрицательно влияет на ее оценки (допустим реальное число, бонусные баллы только при условии сопоставимости), если...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Обычный простой алгоритм для нахождения медианного элемента в массиве из чисел:нAAANnn Пример элементов из с заменой на БN3 / 4n3/4n^{3/4}AAAВBB Сортируйте и найдите элементы ранга и из| Б | ± √ВBB lrB| Б | ± n--√|B|±n|B|\pm \sqrt{n}LllрrrВBB Убедитесь , что и находятся на противоположных сторонах...
Вдохновленный этим вопросом, в котором спрашивающий хочет знать, изменяется ли время выполнения, когда компаратор, используемый в стандартном алгоритме поиска, заменяется честным броском монеты, а также заметной неудачей Microsoft в написании генератора равномерной перестановки, мой вопрос, таким...
Я не совсем понимаю, как определяются PP и BPP . Пусть характеристическая функция для языка L . М - вероятностная машина Тьюринга. Верны ли следующие определения: B P P = { L : P r [ χ ( x ) ≠ M ( x ) ] ≥ 1χχ\chiLL\mathcal{L} P P = { L : P r [ χ ( x ) ≠ M ( x ) ] > 1BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀ x...
Рандомизированные связываемые кучи имеют операцию «соединение», которую мы затем используем для определения всех других операций, включая вставку. Вопрос в том, какова ожидаемая высота этого дерева с узлами?nnn Теорема 1 Гамбина и Малинковского « Рандомизированные смешиваемые приоритетные очереди»...