Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Ustaw strukturę danych w celu wydajnego powtarzania wstawień
Szukam struktury danych zajmującej mało miejsca, która przechowuje zestawy (bez powtórzeń) elementów wordize i obsługuje szybkie wstawianie (amortyzowane O (1)). Przez „oszczędny przestrzennie” rozumiem idealnie, słów do przechowywania n elementów.n + o ( n )n+o(n)n + o(n)nnn Bycie zestawem jest ważną częścią pytania: jeśli każdy element zostanie dodany, razy wykorzystana …
2
Gry nielokalne i komunikacja kwantowa
Obecnie szukam dobrych materiałów referencyjnych dotyczących nielokalnych gier o korzystnych aspektach w komunikacji kwantowej. Na przykład jestem świadomy, że gry nielokalne są dobre w ograniczaniu złożoności komunikacji, a także w zapewnieniu bezpieczeństwa protokołów QKD. Chciałbym wiedzieć, jakie są niektóre z wielkich artykułów na temat nielokalnych gier w komunikacji kwantowej? Czy …
1
Złożoność unikalnej łączności st
Chciałbym wiedzieć, czy w (niedeterministyczny obszar logów) można rozstrzygnąć następujący problem :N L.NL\mathsf{NL} Biorąc pod uwagę ukierunkowany wykres z dwoma wyróżnionymi wierzchołkami s i t , czy istnieje unikalna ścieżka od s do t w G ?solGGssstttssstttsolGG Czuję, że to może być w ponieważ możemy zdecydować, zarówno jeśli istnieje s …
1
Prosty (?) Śmieszny problem kombinatoryczny!
Pozwólmy naprawić 0<E<10<E<100 . dla dowolnego nnn i dla dowolnego wektora c¯∈[0,1]nc¯∈[0,1]n\bar{c} \in [0,1]^n taki, że ∑i∈[n]ci≥E×n∑i∈[n]ci≥E×n\sum_{i\in [n]} c_i \geq E \times n Ac¯:=|{S⊆[n]:∑i∈S ci≥E×t}|≥(E×nt)Ac¯:=|{S⊆[n]:∑i∈S ci≥E×t}|≥(E×nt)A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t } Nie wiem, czy …
1
Biorąc pod uwagę PDA M taki, że L (M) jest w DCFL konstruuj DPDA N, tak że L (N) = L (M)
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 język przez M ?MMML(M)L(M)L(M)N.NNM.MM Równoważne problemu byłoby skonstruować algorytm, który …
1
Równoważność dwóch definicji kompletności i solidności w interaktywnych systemach dowodowych
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 weryfikatora (o ważności fałszywego oświadczenia) Termin „bicz” jest albo interpretowany jako „z prawdopodobieństwem większym …
2
Eksponaty dla muzeum komputerów
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 tematów związanych z informatyką / informatyką / komunikacją / matematyką. Choć …
2
Rozpuszczalność wypełnienia matrycy
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 kolumn.AAA …
3
Czy środowisko MapReduce jest rodzajem BSP?
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ę mapReduce?
4
Czy diagonalizacja oddaje istotę separacji klasowej?
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 diagonalizowanej maszyny Turinga. Oto kilka powiązanych pytań: Czy istnieją dowody separacji klas nieoparte na …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.