Powiedzmy, że wiemy, że problem A jest trudny, a następnie redukujemy A do nieznanego problemu B, aby udowodnić, że B jest również trudny. Jako przykład: wiemy, że 3-kolorowanie jest trudne. Następnie redukujemy kolorowanie 3 do koloru 4. Po połączeniu jednego z kolorów 3-kolorowania masz...
Kilka tygodni temu podjąłem egzaminy z teorii obliczeń i było to jedno z pytań: Załóżmy, że językL = { (zanbm)r∣ n , m , r ≥ 0 }L.={(zanbm)r∣n,m,r≥0}L=\{(a^nb^m)^r \mid n,m,r\ge 0\} Czy L jest regularny? Jeśli tak, podaj wyrażenie regularne lub automat. Po tym, jak krótko zapytałem go o...
Wystąpił następujący problem: Biorąc pod uwagę ukierunkowany wykres acykliczny z rzeczywistymi wartościami grubości krawędzi oraz dwoma wierzchołkami s i t, oblicz minimalny st st cut. Dla ogólnych wykresów jest to trudne NP, ponieważ można w prosty sposób zredukować maksymalne cięcie, po prostu...
Mam złożone zapytanie używane do przeszukiwania zestawu danych celu znalezienia . Każde zapytanie zajmuje średni czas więc całkowity czas w wyszukiwaniu liniowym wynosi. Mogę podzielić zapytanie na prostsze zapytania częściowe q_i i znaleźć i gdzie . Każde podzapytanie jest znacznie szybsze do...
Szukam wydajnego algorytmu do znajdowania najdłuższego powtarzającego się wzorca w ciągu. Weźmy na przykład następujący ciąg liczb: 5431428571428571428571428571427623874534. Jak widać, 142857142857jest to najdłuższy wzór, który powtarza się kilka razy (przynajmniej dwa razy) w tym...
Utknąłem na tym problemie: Biorąc pod uwagę tablicę AZAA z pierwszego nnn liczby naturalne losowo permutowane, tablica BbB jest zbudowany tak, że B(k)b(k)B(k) jest liczbą elementów od A(1)ZA(1)A(1) do A(k−1)ZA(k-1)A(k-1) które są mniejsze niż A(k)ZA(k)A(k). i) Biorąc pod uwagę AZAA czy...
Zastanów się nad niekierowanym wykresem ze źródłem i wierzchołkiem ujścia. Chcemy usunąć minimalną liczbę wierzchołków na tym wykresie, aby odłączyć dowolną ścieżkę między źródłem a ujściem. Czy możemy to zrobić, używając algorytmu maksymalnego przepływu, minimalnego...
Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.LϵLϵL_\epsilon222φφ\varphi(12+ϵ)(12+ϵ)(\frac{1}{2}+\epsilon)φφ\varphi Muszę udowodnić, że istnieje st is twardy dla każdego
Dlaczego liczby obliczalne (w sensie Turinga) są policzalne? To musi być bardzo oczywiste, ale obecnie po prostu tego nie
Jestem zdezorientowany co do definicji PP i BPP . Załóżmy, że jest charakterystyczną funkcją języka . M być probabilistyczną Maszyną Turinga. Czy następujące definicje są poprawne:χχ\chiLL\mathcal{L} BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ>0}BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ>0}BPP =\{\mathcal{L}...
Czy ten wariant problemu sumy częściowej jest łatwy / znany? Biorąc pod uwagę liczbę całkowitą oraz zestaw dodatnich liczb całkowitych tak, że każdy ma co najwyżej bity ustawione na ( ); czy jest podzestaw taki, że suma jego elementów jest równa ?mmmA = {x1,x2), . . . ,xn}A={x1,x2,...,xn}A =...
Chcemy kafelki m×mm×mm\times m-kwadrat przy użyciu dwóch rodzajów kafelków: 1×11×11 \times 1- kwadratowa płytka i 2×22×22 \times 2- kwadratowy kafelek, tak aby każdy leżący pod nim kwadrat był przykryty bez nakładania się. Zdefiniujmy funkcjęf(n)f(n)f(n) co daje rozmiar największego, unikalnego,...
Po przeczytaniu tego pytania „ Naturalne problemy RE nierozstrzygalne, ale nie pełne Turinga ” przyszedł mi do głowy następujący język: Jeśli jest funkcją bobra zajętego (maksymalny osiągalny wynik wśród wszystkich zatrzymujących 2-symbolowych maszyn Turinga n-stanu opisanego powyżej typu, gdy...
Walczę z kilkoma definicjami reprezentacji wiedzy i szukam wiarygodnej pomocy w ich rozróżnieniu. Szukałem na wikipedii i wielu stronach internetowych różnicy między ontologiami a sieciami semantycznymi (nie mylić z siecią semantyczną). Chociaż strona wikipedii w sieci semantycznej nigdy nie...
Biorąc pod uwagę (binarny) program liczbowy w postaci:0 , 10,10,1 minśwfa( x )A x = bxja≥ 0xja∈ { 0 , 1 }∀ i∀ iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall...
Pamięci podręczne procesora są wykorzystywane przez wykorzystanie lokalizacji czasowej i przestrzennej. Moje pytanie brzmi: kto jest odpowiedzialny za zarządzanie tymi pamięciami podręcznymi? Czy ten system operacyjny rozpoznaje określony wzorzec dostępu, a następnie zarządza pamięcią podręczną...
W wideo recytacyjnym dla MIT OCW 6.006 o 43:30, Biorąc pod uwagę m × nm×nm \times n matryca ZAAA z mmm kolumny i nnn wiersze, algorytm 2-D znajdowania pików, w którym pik jest dowolną wartością większą lub równą sąsiednim sąsiadom, opisano jako: Uwaga: W przypadku nieporozumień przy opisywaniu...
SkipList zapewnia to samo O(logn)O(logn)O(\log n)ogranicza wyszukiwanie jako drzewo zrównoważone z tą zaletą, że ponowne zbalansowanie nie jest konieczne. Ponieważ SkipList jest konstruowany przy użyciu losowych rzutów monetą, granice te obowiązują tylko tak długo, jak długo struktura SkipList...
Zainspirowane tym pytaniem, w którym pytający chce wiedzieć, czy czas działania zmienia się, gdy komparator użyty w standardowym algorytmie wyszukiwania zostaje zastąpiony uczciwym rzucie monetą, a także wyraźnym niepowodzeniem Microsoftu w napisaniu jednolitego generatora permutacji, moje pytanie...
Ostatnio zadałem pytanie na temat Math SE. Na razie brak odpowiedzi. To pytanie jest związane z tym pytaniem, ale bardziej technicznymi szczegółami w kierunku informatyki. Biorąc pod uwagę dwa DFA i gdzie zbiór stanów, alfabet wejściowy i funkcja przejścia i są takie same, stany początkowe i stany...