Rozmawiałem o tym, jak zdefiniować kwantowe maszyny Turinga? i czuję, że kwantowa TM i niedetermistyczna TM są jednym i tym samym. Odpowiedzi na inne pytanie nie dotyczą tego. Czy te dwa modele są takie same? Jeśli nie, Jakie są różnice między Quantum TM i NDTM? Czy jest jakieś obliczenie,...
Jakie różnice i zależności występują między algorytmami losowymi a algorytmami niedeterministycznymi? Z Wikipedii Randomizowane algorytm jest algorytmem, w którym stosuje się stopniem losowości jako część logiki. Algorytm zwykle wykorzystuje jednolicie losowe bity jako pomocnicze dane wejściowe...
Rozumiem, że jeśli istnieją 2 lub więcej drzew lewej lub prawej pochodnej, gramatyka jest niejednoznaczna, ale nie jestem w stanie zrozumieć, dlaczego jest tak źle, że wszyscy chcą się go
Wiele podręczników obejmuje typy przecięć w rachunku lambda. Reguły pisania dla przecięcia można zdefiniować w następujący sposób (na górze zwykłego rachunku lambda z podtypami): Γ⊢M:T1Γ⊢M:T2Γ⊢M:T1∧T2(∧I)Γ⊢M:⊤(⊤I)Γ⊢M.:T.1Γ⊢M.:T.2)Γ⊢M.:T.1∧T.2)(∧ja)Γ⊢M.:⊤(⊤ja) \dfrac{\Gamma \vdash M : T_1 \quad...
Czy SQL potrzebuje podkwerend? Wyobraź sobie wystarczająco uogólnioną implementację ustrukturyzowanego języka zapytań dla baz danych relacji. Ponieważ struktura kanonicznej SELECTinstrukcji SQL jest naprawdę bardzo ważna, aby miało to sens, nie odwołuję się bezpośrednio do algebry relacyjnej, ale...
Teza Church-Turinga stwierdza, że wszystko, co można fizycznie obliczyć, można obliczyć na maszynie Turinga. Artykuł „Obliczenia analogowe przez sieci neuronowe” (Siegelmannn i Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) twierdzi, że sieć neuronowa o określonej formie...
Obecnie czytam książkę o algorytmach i złożoności. W tej chwili czytam o funkcjach obliczalnych i niepoliczalnych, a moja książka stwierdza, że jest o wiele więcej funkcji, które nie są obliczalne niż obliczalne, w rzeczywistości większość jest niepoliczalna. W pewnym sensie intuicyjnie mogę to...
Interesuje mnie określenie podejścia do rozwiązania algorytmu „sugerowanych przyjaciół”. Facebook ma funkcję, w której poleci ci osoby, z którymi według ciebie możesz się zapoznać. Ci użytkownicy zwykle (z wyłączeniem skrajnych przypadków, w których użytkownik szczególnie poleca znajomemu ) mają...
Dowiedzieliśmy się o koncepcji wyliczenia funkcji. W praktyce odpowiadają one językom programowania. W pewnej uwadze profesor wspomniał, że klasa wszystkich całkowitych funkcji (tj. Funkcji, które zawsze kończą się dla każdego wejścia) nie jest wyliczalna. Oznaczałoby to, że nie możemy opracować...
Mam chciwy algorytm, który, jak podejrzewam, może być poprawny, ale nie jestem pewien. Jak sprawdzić, czy jest poprawny? Jakich technik należy użyć do udowodnienia, że chciwy algorytm jest poprawny? Czy istnieją wspólne wzorce lub techniki? Mam nadzieję, że stanie się to pytaniem referencyjnym,...
Istnieje prosty algorytm wielomianowy, który decyduje, czy istnieje ścieżka między dwoma węzłami na ukierunkowanym wykresie (po prostu wykonaj rutynowe przemierzanie wykresu za pomocą, powiedzmy, głębokości pierwszego wyszukiwania). Jednak wydaje się, że, co zaskakujące, problem staje się znacznie...
Natknąłem poniżej rachunku przez Alana M. Turinga tutaj : „Pogląd, że maszyny nie mogą wywoływać niespodzianek, jest, jak sądzę, spowodowany błędem, któremu szczególnie podoba się filozofów i matematyków. Jest to założenie, że jak tylko fakt zostanie przedstawiony umysłowi, wszystkie...
Kiedy wyjaśniłem dowód Baker-Gill-Solovay, że istnieje wyrocznia, którą możemy mieć, , oraz wyrocznia, z którą możemy otrzymać P ≠ N P przyjacielowi, pojawiło się pytanie, dlaczego takie techniki nie nadają się do udowodnienia problemu P ≠ N P i nie mogłem udzielić zadowalającej odpowiedzi.P = N...
W pełni połączone (przynajmniej warstwa po warstwie z więcej niż 2 ukrytymi warstwami) sieci backprop są uniwersalnymi uczniami. Niestety, często są powolne w nauce i mają tendencję do nadmiernego dopasowania lub mają niezręczne uogólnienia. Po wygłupianiu się z tymi sieciami zauważyłem, że...
Przez jakiś czas studiowałem kompilatory i szukałem, co rozumie się przez „kontekst” w gramatyce i co to znaczy, że gramatyka jest „bezkontekstowa”, ale bez rezultatu. Czy ktoś może w tym
Moja matka bierze udział w kursie internetowym, aby zostać bibliotekarką, w tym kursie obejmują wyszukiwania boolowskie, dzięki czemu mogą skutecznie przeszukiwać bazy danych, jednak pojawiło się pytanie brzmiące mniej więcej tak: Wyszukiwanie „x OR y” spowoduje 105 000 trafień, podczas gdy...
Wdrażam zestaw algorytmów wyszukiwania ścieżek, takich jak Dijkstra's, Depth First itp. Początkowo korzystałem z kilku samodzielnie wykonanych wykresów, ale teraz chciałbym podjąć wyzwanie nieco dalej, dlatego szukam jednego z nich wykresy stosowane w testach porównawczych; wykresy miast świata...
Czytałem od kilku tygodni o rachunku Lambda, ale jeszcze nie widziałem niczego, co różni się materialnie od istniejących funkcji matematycznych i chcę wiedzieć, czy to tylko kwestia notacji, czy też są jakieś nowe właściwości lub reguły utworzone przez aksjomaty rachunku lambda, które nie mają...
Szukam algorytmu do generowania tablicy N liczb losowych, tak że suma N liczb wynosi 1, a wszystkie liczby mieszczą się w przedziale 0 i 1. Na przykład N = 3, losowy punkt (x, y, z) powinien leżeć w trójkącie: x + y + z = 1 0 < x < 1 0 < y < 1 0 < z < 1 Idealnie chciałbym, aby...
W 3SUM problemów próbuje zidentyfikować 3 liczb całkowitych z zestawu wielkości takie, że .S n a + b + c = 0a,b,ca,b,ca,b,cSSSnnna+b+c=0a+b+c=0a + b + c = 0 Przypuszcza się, że nie ma lepszego rozwiązania niż kwadratowe, tj. . Lub inaczej: .o ( n log ( n ) + n 2