Teoretyczne informatyka

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

2
Książki z algorytmami online
Czy są jakieś najnowsze książki na temat algorytmów online? Znam tylko dwie książki na ten temat. Obliczenia online i analiza konkurencji Allana Borodina i Ran El-Yaniv: Jest to klasyczna, ale stara książka i nie zawiera wielu najnowszych osiągnięć w tej dziedzinie. Projektowanie konkurencyjnych algorytmów online za pomocą podejścia pierwotnego podwójnego …
1
Czy kontekstowa równoważność języka z `quote`-`eval` jest trywialna, czy nie?
W [1] Mitchell Wand wykazał, że dodanie fexprs do czystego rachunku lambda trywializuje teorię równoważności kontekstowej, co oznacza, że ​​dwa terminy są równoważne kontekstowo, jeśli są zgodne. Badając pokrewną pracę, stwierdził: „nasz wynik rozszerza starą obserwację Alberta Meyera [2] i czyni banalną równoważność kontekstową”. Ale odnosząc się do [2], można …
3
Czy każdy program można wdrożyć mechanicznie?
Czy można zbudować mechaniczną implementację powiedzmy Microsoft Word w jednym celu (bez Turinga)? Czy można wdrożyć takie rzeczy jak iteratory, funkcje pierwszego rzędu, całą gamę technik programowania? Czy koła zębate i inne części mechaniczne mogą reprezentować struktury danych, a nawet obiekty programu? Czy w pewnym momencie wymaga to zbudowania maszyny …
3
Jednokierunkowa weryfikacja kwantowa
Teoria obliczania stanu skupienia jest już dobrze ugruntowana, pokazując, że dowolny obwód BQP może być modyfikowany, więc używa tylko pojedynczych bramek kwantowych, ewentualnie sterowanych klasycznie, pod warunkiem wystarczającej podaży stanu zwanego „stanem skupienia” - który jest prostym w produkcji stanem stabilizatora. Moje pytanie brzmi: czy podobne pojęcie jest znane z …
1
Pojemność jednoznacznie rozwiązanej układanki (USP)
W swoim kluczowym artykule Teoretyczne algorytmy grupowania macierzy Cohn, Kleinberg, Szegedy i Umans przedstawiają koncepcję unikatowej układanki (zdefiniowanej poniżej) i zdolności USP. Twierdzą oni, że Coppersmith i Winograd, w ich własnym papierze przełomowy Mnożenie macierzy poprzez ciąg arytmetyczny , „pośrednio” udowodnić, że zdolność USP jest 3/22/33/22/33/2^{2/3} . Twierdzenie to zostało …
2
Czy można zastosować ograniczenia losowe, aby uzyskać dolną granicę dla
Istnieje wiele dobrze znanych C 0 wielkości obwód dolny związanego wyniki w oparciu o losowe ograniczeń i przełączania lematu .AC0AC0\mathsf{AC^0} Czy możemy opracować wynik zamiany lematu, aby udowodnić niższą wielkość dla obwodów TC0TC0\mathsf{TC^0} (podobnie do dolnej granicy dla AC0AC0\mathsf{AC^0} )? Czy jest jakaś nieodłączna przeszkoda w stosowaniu tego podejścia do …
2
Eliminacja gaussowska pod względem działania grupowego
Eliminacja Gaussa sprawia, że ​​wyznacznik macierzy obliczany jest w czasie wielomianowym. Zmniejszenie złożoności obliczania wyznacznika, które w przeciwnym razie jest sumą terminów wykładniczych, wynika z obecności alternatywnych znaków ujemnych (których brak sprawia, że ​​obliczenia są trwałe, tj. Trudniejszy niż problemy ). Prowadzi to do pewnego rodzaju symetrii w wyznaczniku, np. …
2
Jaka jest tendencja do losowych wielomianów o niskim stopniu nad GF (2)?
ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Gdy piszę losowy wielomian o stopniu ≤d≤d\le d a n zmiennych, można myśleć o każdy jednomianów całkowitego stopnia ≤d≤d\le d pobrane z prawdopodobieństwem 1/2. Jedyną istotną rzeczą, jaką znam, jest wariant Schwartza-Zippla, który stwierdza, że ​​jeśli wielomian jest niestały, wówczas jego odchylenie wynosi …
2
Nauka trójkątów w płaszczyźnie
I przypisany Moi studenci problem znalezienia trójkąt spójne z kolekcją punktów w R 2 , oznaczonego ± 1 . (Trójkąt T jest zgodny z próbką oznaczoną, jeśli T zawiera wszystkie punkty dodatnie i żaden z punktów ujemnych; z założenia próbka przyjmuje co najmniej 1 spójny trójkąt).mmmR2R2\mathbb{R}^2±1±1\pm1TTTTTT Najlepsze, co mogliby zrobić …
1
Zależność między analizą składniową redukującą przesunięcie a ograniczonymi kontynuacjami?
Czy ktoś sformalizował związek między technikami analizy składniowej redukującej przesunięcie a ograniczonymi kontynuacjami? Podczas konstruowania analizatora składniowego typu oddolnego (np. Parserów LR) bierzemy gramatykę, a następnie reprezentujemy stany analizy jako zestawy elementów : rozszerzone produkcje od postaci , gdzie i są sekwencje terminali i nieterminali. Marker reprezentuje, jak daleko parser …
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.