Teoretyczne informatyka randomized-algorithms

1

W artykule Na temat dwóch problemów teorii informacji Erdõs i Rényi wyznaczają dolne granice minimalnej liczby ważeń, które należy zrobić, aby określić liczbę fałszywych monet w zestawie monet.nnn Bardziej formalnie: Fałszywe monety mają mniejszą wagę niż właściwe monety; znane są wagi i zarówno prawych, jak i fałszywych monet. Podana jest …

10 ds.algorithms reference-request co.combinatorics it.information-theory randomized-algorithms

2

Jak tasować kolorowe kulki?

Mam 400 piłek, w których 100 to czerwone, 40 to żółte, 50 to zielone, 60 to niebieskie, 70 to fioletowe, 80 to czarne. (kule tego samego koloru są identyczne) Potrzebuję wydajnego algorytmu tasowania, aby po tasowaniu kulki znalazły się na liście i 3 kolejne kule nie są tego samego koloru. …

10 ds.algorithms randomized-algorithms permutations

1

Algorytm do obliczania odległości między mocami

Biorąc pod uwagę coprime a , ba,ba, b, czy możesz szybko obliczyć minx , y> 0|zax-by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Tutaj są liczbami całkowitymi. Oczywiście przyjęcie daje nieciekawą odpowiedź; ogólnie, jak blisko te moce mogą się zbliżyć? Jak szybko obliczyć minimalizujące ?x, yx,yx, yx = y= 0x=y=0x …

9 ds.algorithms randomized-algorithms nt.number-theory comp-number-theory

1

Jednolita derandomizacja klas złożoności obwodów

Pozwolić CC\mathcal{C} być klasą złożoności i BP-CBP-C\textrm{BP-}\mathcal{C} być randomizowanym odpowiednikiem CC\mathcal{C} zdefiniowane w taki sam sposób jak BPPBPP\textrm{BPP} jest zdefiniowany w odniesieniu do PP\textrm{P}. Bardziej formalnie zapewniamy wielomianowo wiele losowych bitów i akceptujemy dane wejściowe, jeśli prawdopodobieństwo, że zostanie zaakceptowane, jest zakończone2323\frac{2}{3}. W poprzednim poście zapytałem, czy wiadomo, czy równość …

9 circuit-complexity randomized-algorithms derandomization

1

Jaki jest najgorszy przypadek losowego algorytmu triangulacji przyrostowej delauny?

Wiem, że oczekiwany najgorszy czas działania randomizowanego przyrostowego algorytmu triangulacji delauny (jak podano w geometrii obliczeniowej ) to . Istnieje ćwiczenie sugerujące, że najgorszym środowiskiem uruchomieniowym jest . Próbowałem skonstruować przykład, w którym tak naprawdę jest, ale jak dotąd nie udało się.O(nlogn)O(nlog⁡n)\mathcal O(n \log n)Ω(n2)Ω(n2)\Omega(n^2) Jeden z tych prób było …

9 ds.algorithms randomized-algorithms delaunay-triangulation worst-case

Pytania otagowane jako randomized-algorithms