W Hromkovič's Algorytmics for Hard Problems (2nd edition) znajduje się takie twierdzenie (2.3.3.3, strona 117): Istnieje (rozstrzygalny) problem decyzyjny taki że dla każdego algorytmu A, który rozwiązuje P, istnieje inny algorytm A ', który również rozwiązuje P i dodatkowo...
Prawo De Morgana jest często wprowadzane we wstępnym kursie matematyki dla informatyki i często postrzegam to jako sposób na przekierowanie zdań z AND na OR poprzez negację terminów. Czy istnieje bardziej intuicyjne wyjaśnienie, dlaczego to działa, niż tylko zapamiętywanie tabel prawdy? Dla mnie...
Pozwolić L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. Czy regularny?LLL To pytanie wyglądało podejrzanie na pierwszy rzut oka i zdałem sobie sprawę, że jest związane z hipotezą o podwójnej liczbie pierwszych ....
Kursy grafiki wstępnej zwykle mają projekt, w którym prosi się o zbudowanie ray tracera do renderowania sceny. Wielu studentów grafiki rozpoczynających naukę w grad grad mówi, że chcą pracować nad ray tracingiem. A jednak wydaje się, że ray tracing jest martwym polem w miejscach takich jak SIGGRAPH...
Niedawno przeczytałem, że można mieć tablice, które nie muszą być inicjowane, tzn. Można z nich korzystać bez konieczności poświęcania czasu na ustawianie wartości domyślnej dla każdego elementu. tzn. możesz zacząć używać tablicy tak, jakby została ona zainicjowana wartością domyślną, bez...
Wykres unipatyczny jest wykresem ukierunkowanym, tak że istnieje co najwyżej jedna prosta ścieżka z jednego wierzchołka do dowolnego innego wierzchołka. Wykresy unipatyczne mogą mieć cykle. Na przykład podwójnie połączona lista (nie okrągła!) Jest grafem unipatycznym; jeśli lista zawiera...
Szukam wydajnego algorytmu, który pozwala mi przetwarzać drzewo wyszukiwania minimax dla szachów z przycinaniem alfa-beta w architekturze rozproszonej. Algorytmy, które znalazłem (PVS, YBWC, DTS, patrz poniżej) są dość stare (najpóźniej 1990). Zakładam, że od tego czasu nastąpiło wiele istotnych...
Próbuję użyć lematu pompującego, aby udowodnić, że nie jest regularne.L = { ( 01 )m2)m∣ m ≥ 0 }L={(01)m2m∣m≥0}L = \{(01)^m 2^m \mid m \ge0\} Oto co mam do tej pory: Załóżmy, że jest regularne i niech p będzie długością pompowania, więc w = ( 01 ) p 2 p . Rozważ każdy rozkład pompowania w = x y z...
Czy dla każdej funkcji obliczalnej fff istnieje problem, który można najlepiej rozwiązać w czasie Θ(f(n))Θ(f(n))\Theta(f(n)) czy też istnieje funkcja obliczalna fff tak że każdy problem, który można rozwiązać w O(f(n))O(f(n))O(f(n)) może również być rozwiązany w czasie o(f(n))o(f(n))o(f(n)) ? To...
Pomyślałem więc, że należy do tego (choć nieco podstawowego) pytania: Powiedzmy, że mam wykres wielkości 100 węzłów ułożonych we wzór 10x10 (pomyśl szachownica). Wykres jest nieukierowany i nieważony. Poruszanie się po wykresie wymaga przesunięcia o trzy pola do przodu i jedno pole w prawo lub w...
Moim celem jest rozwiązanie następującego problemu, który opisałem na podstawie jego danych wejściowych i wyjściowych: Wejście: Kierunkowy wykres acykliczny z m węzłami, n źródłami i 1 ujściem ( m > n ≥ 1 ).GGGmmmnnn111m>n≥1m>n≥1m > n \geq 1 Wynik: VC wymiar (lub zbliżanie niego) dla...
Czy istnieje sposób na stwierdzenie, czy dwa zestawy punktów można oddzielić linią? Mamy dwa zestawy punktów i jeśli istnieje linia, która oddziela i tak że wszystkie punkty i tylko po jednej stronie linii oraz wszystkie punkty i tylko po drugiej stronie.B A B A A B
Próbuję znaleźć podejście do następującego problemu: Biorąc pod uwagę zestaw punktu i promień , znajdź punkt środkowy okręgu, tak aby okrąg zawierał maksymalną liczbę punktów ze zbioru. Czas działania powinien wynosić .SSSrrrO(n2)O(n2)O(n^2) Na początku wydawało się, że jest to coś podobnego...
Tożsamości używane w algorytmach mnożenia przez Karatsuba (liczby całkowite) Gauss (liczby zespolone) Strassen (matryce) wydają się bardzo blisko spokrewnione. Czy istnieje wspólna abstrakcyjna struktura /
Podczas testowania algorytmów powszechnym podejściem jest testowanie losowe: generuj znaczną liczbę danych wejściowych zgodnie z pewnym rozkładem (zwykle jednolitym), uruchom na nich algorytm i sprawdź poprawność. Nowoczesne ramy testowania mogą generować dane wejściowe automatycznie na podstawie...
Próbuję znaleźć maksymalny niezależny zestaw wykresu biparytu. W niektórych notatkach „13 maja 1998 r. - University of Washington - CSE 521 - Zastosowania przepływu sieci” znalazłem : Problem: Biorąc pod uwagę dwudzielny wykres , znalezienie niezależnego zestawu , który jest tak duży, jak to...
Niech . Muszę zdecydować, czy F jest rozstrzygalne, czy rekurencyjnie wyliczalne. Myślę, że jest to rozstrzygalne, ale nie wiem, jak to udowodnić.F={⟨M⟩:M is a TM which stops for every input in at most 50 steps}F={⟨M⟩:M is a TM which stops for every input in at most 50 steps}F = \{⟨M⟩:\text{M is a...
Zauważam, że w kilku artykułach z badań CS, w celu porównania wydajności dwóch algorytmów, zamiast samych rzeczywistych czasów obliczeniowych użyto całkowitej liczby kluczowych porównań w algorytmach. Dlaczego nie możemy porównać, który z nich jest lepszy, uruchamiając oba programy i licząc...
Utknąłem na następujące pytanie: „Zwykłe języki są dokładnie tymi, które są akceptowane przez automaty skończone. Biorąc pod uwagę ten fakt, pokaż, że jeśli język jest akceptowany przez jakiś automat skończony, wówczas jest również akceptowany przez niektóre skończone; składa się ze wszystkich...
Ciągle natrafiam na odniesienia do stałego punktu w pytaniach i odpowiedziach na stackexchange i szukam znaczenia w Internecie, oczywiście znajdując odnośniki na stronach takich jak Wikipedia. Jednak żadne z odniesień tak naprawdę nie odpowiada na moje pytanie, co jest stałym punktem i co to znaczy...