Pytania oznaczone «reference-request»

13
Rozróżnianie dwóch monet

Powszechnie wiadomo, że złożoność odróżnianie się stronniczy monetę z jednego sprawiedliwego jest θ ( ε - 2 ) . Czy istnieją wyniki dla odróżnienia monety p od monety p + ϵ ? Widzę, że dla specjalnego przypadku p = 0 złożoność będzie wynosić ϵ - 1 . Mam przeczucie, że złożoność będzie zależeć od...

13
Wdrożony kod do obliczania szerokości ścieżki (= numer wyszukiwania węzła, numer separacji wierzchołków, grubość przedziału)

Szukam implementacji algorytmu do obliczania szerokości ścieżki wykresu. Dobrze wiadomo, że obliczenie szerokości ścieżki jest równoważne z obliczeniem numeru wyszukiwania węzła, numeru separacji wierzchołków lub grubości przedziału wykresu. Algorytm nie musi być bardzo szybki; Chcę uruchomić go na...

13
Zastosowanie liczb Ramseya

Definicja liczb Ramseya jest następująca: Niech jest dodatnią liczbą taką, że każdy wykres zamówienia na przynajmniej R ( , b ) obejmuje albo klika w ciągu wierzchołków lub zestaw się na stałym b wierzchołków.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Pracuję nad jakimś rozszerzeniem Ramsey...