Czy istnieje klasa algorytmów mieszających, teoretycznych lub praktycznych, tak że algorytm w tej klasie można uznać za „zwrotny” zgodnie z definicją podaną poniżej: hash1 = algo1 („tekst wejściowy 1”) hash1 = algo1 („tekst wejściowy 1” + hash1) Operator + może być konkatenacją lub dowolną inną...
Angluin i Laird ('88) sformalizowali uczenie się z przypadkowo uszkodzonymi danymi w modelu „PAC z losowym szumem klasyfikacyjnym” (lub hałaśliwym PAC). Model ten jest podobny do PAC uczenia , z wyjątkiem etykiet z przykładów podanych w uczącej są uszkodzone (grzbiet), niezależnie w sposób losowy,...
To pytanie było motywowane pytaniem dotyczącym przepływu stosu . Załóżmy, że otrzymujesz zrootowane drzewo (tzn. Jest to root, a węzły mają dzieci itp.) W węzłach (oznaczonych ).n 1 , 2 , … , nT.T.Tnnn1 , 2 , … , n1,2),…,n1, 2, \dots, n Każdy wierzchołek ma powiązaną nieujemną masę całkowitą: .w...
Jestem studentką CS. Zrobiliśmy teorię grafów w jednym kursie. Uważam to za interesujące. Jakie są prawdziwe zastosowania teorii grafów w dziedzinie informatyki? Na przykład odkryłem, że niektóre koncepcje teorii grafów można wykorzystać do projektowania sieci. Jakie są inne podobne...
Bezpieczeństwo SHA-1 zostało omówione, ponieważ algorytm znajdowania kolizji został po raz pierwszy opublikowany w CRYPTO 2004, a następnie został ulepszony. Wikipedia wymienia kilka odniesień , jednak wydaje się, że najnowsze badania opublikowane (a później wycofane) na ten temat miały miejsce w...
Merlin, który ma nieograniczone zasoby obliczeniowe, chce przekonać Arturowi, że m | ∑p ≤ N, p pierwsza pkm|∑p≤N., p głównypkm|\sum_{p\le N,\ p\text{ prime}}p^k dla ( N, m , k )(N.,m,k)(N,m,k) przy k = O ( logN.)k=O(logN.)k=O(\log N) i m = O ( N) .m=O(N.).m=O(N). Obliczenie tej sumy w prosty...
Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana. Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją...
Czy były prace nad odzyskaniem nachylenia segmentu linii po digitalizacji? Oczywiście nie można tego zrobić z idealną dokładnością; to, czego się chce, to metoda wyprowadzenia z linii cyfrowej przedziału możliwych nachyleń. (Pojęcie cyfrowej linii, której używam, to Rosenfelda: zbiór par gdzie...
Nurikabe to układanka wypełniająca siatki oparta na ograniczeniach, luźno podobna do Saperów / Nonogramów; liczby są umieszczane na siatce, która ma być wypełniona wartościami włączania / wyłączania dla każdej komórki, przy czym każda liczba wskazuje region połączonych komórek „on” o tej wielkości,...
Mam problem, który jest w NEXP NP i który może być rozwiązany przez przemienną TM przy użyciu czasu wykładniczego i tylko jednej alternacji (zaczynając od stanu egzystencjalnego).NPNP^{\text{NP}} Czy jest coś znanego na temat NEXP NP ? Czy jest równy NEXP lub innej klasie? Czy istnieją inne...
Logiki warunkowe to logiki, które rozszerzają tradycyjną implikację logiczną za pomocą operatorów modalnych odpowiadających innym pojęciom warunku (na przykład przyczynowy warunkowy brzmi „ powoduje„ B ”lub warunkowanie probabilistyczne „ ”, które brzmi „ dany B ”).A A | B AA□→BA◻→BA\;...
Wiem, że pytanie „czy formuła pierwszego rzędu ma model” jest ogólnie nierozstrzygalne.ϕϕ\phi Czy ktoś mógłby mi dać link lub książkę, która da odpowiedź na skończone modele. Jeśli mam wzór pierwszego rzędu , czy można rozstrzygnąć, czy ϕ ma model skończony? Jestem pewien, że pytanie jest dobrze...
Chciałbym zapytać, czy jest na to już opublikowany wynik: Bierzemy wszystkie możliwe różne ścieżki między każdą parą węzłów dwóch połączonych regularnych (o powiedzmy stopnia , i liczby węzłów ) wykresów i zapisujemy ich długości. Oczywiście ta liczba odrębnych ścieżek ma charakter wykładniczy....
Czy nazywanie frameworku mapReduce jest rodzajem masowego synchronicznego frameworku programowania równoległego bez przechowywania pamięci lokalnej w procesorach między synchronizacjami? Jeśli nie, to jaki model programowania równoległego najdokładniej ujmuje strukturę
Macierz ma wymiar n × n ( n - 1 ) . Chcemy wypełnić A za pomocą liczb całkowitych od 1 do n włącznie.AAAn×n(n−1)n×n(n−1)n \times n(n-1)AAA111nnn Wymagania: Każda kolumna jest permutacją 1 , … , n .AAA1,…,n1,…,n1, \dots, n Żadna submatrix utworzona z dwóch rzędów nie może mieć identycznych...
Wydaje mi się, że wszystkie muzea i wystawy związane z komputerami obejmują jedynie historię maszyn komputerowych, ale nic na temat informatyki. Uczestniczysz w tworzeniu nowego Muzeum Informatyki, którego zadaniem jest edukacja, rozrywka i inspirowanie ogółu społeczeństwa w szerokim zakresie...
Szukam wysoce wydajnej struktury danych do przechowywania danych podobnych do poniższych. Identyfikatory Zamówienie 1 Zamówienie 2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 Muszę być w stanie kwerendy tej struktury w taki sposób, że daje mi listę wszystkich...
Kompletność i solidność w interaktywnych systemach dowodowych są nieformalnie definiowane jako: Kompletność: Jeśli stwierdzenie jest prawdziwe, szczery Prover może przekonać uczciwego weryfikatorem tego faktu WHP . Poprawność: jeśli oświadczenie jest fałszywe, oszust nie może przekonać uczciwego...
Nie pamiętam, że widziałem separację klas nieopartą na wynikach diagonalizacji i relatywizacji. Diagonalizacja może być nadal używana do oddzielania pozostałych znanych klas, ponieważ argumenty nierelatywizujące mogą być nadal stosowane w konkluzji o diagonalizacji lub w konstrukcji...
Czy można zbudować algorytm, który przyjmuje jako dane wejściowe automat do przesuwania wraz z obietnicą, że język zaakceptowany przez ten automat L ( M ) jest deterministycznym językiem bezkontekstowym i wysyła deterministyczny automat do przesuwania N, który akceptuje dokładnie zaakceptowany...