Teoretyczne informatyka

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

2
Wyjaśnienie funktora aplikacyjnego w kategoriach kategorycznych - funktory monoidalne
Chciałbym zrozumieć Applicativew kategoriach teorii kategorii. Dokumentacja dla Applicativetwierdzi, że jest to silny funktor LAX monoidal . Po pierwsze, strona Wikipedii o funktorach monoidalnych mówi, że funktor monoidalny jest luźny lub silny . Wydaje mi się więc, że jedno ze źródeł jest niepoprawne lub używają terminów inaczej. Czy ktoś może …
5
Przytulne dzielnice „P” i „NP-hard”
Niech będzie zadaniem algorytmicznym. (Może to być problem decyzyjny, problem optymalizacji lub inne zadanie.) Nazwijmy X „po stronie wielomianowej”, jeśli wiadomo, że założenie, że X jest trudne NP, oznacza, że ​​załamuje się wielomianowa hierarchia. Nazwijmy X „po stronie NP”, jeśli wiadomo, że X przyjmuje algorytm wielomianowy, który implikuje załamanie się …
3
Wybór artykułów do przeczytania
OŚWIADCZENIE: To pytanie jest otwarte, a purytanie z wymiany stosów prawdopodobnie odczuwaliby niezwykłą potrzebę głosowania w celu zapomnienia. Nie mogę jednak wymyślić żadnego innego forum bardziej odpowiedniego i obiecującego na uzyskanie odpowiedzi na to pytanie. Pracując nad problemem badawczym do projektu kursu, zdaję sobie sprawę, że jeśli w szczególny sposób …
2
Alfabet maszyny Turinga z pojedynczą taśmą
Czy każda funkcja która jest obliczalna w czasie t na maszynie Turinga z pojedynczą taśmą, używając alfabetu wielkości k = O ( 1 ), może być obliczona w czasie O ( t ) na single-taśma maszyna Turinga za pomocą alfabetu wielkości 3 (powiedzmy, 0 , 1 , i puste)?fa: { …
6
Złożoność znalezienia składowej macierzy
Moje pytanie jest proste: Jaki jest najgorszy czas z najbardziej znanych algorytm działa dla wyliczania eigendecomposition danego matrycy?n×nn×nn \times n Czy skład eigend redukuje się do mnożenia macierzy, czy w najgorszym przypadku są najlepiej znanymi algorytmami (przez SVD )?O(n3)O(n3)O(n^3) Proszę zauważyć, że proszę o analizę najgorszego przypadku (tylko w kategoriach …
3
Jakie są powody, dla których badacze geometrii obliczeniowej preferują model BSS / real-RAM?
tło Obliczenia na liczbach rzeczywistych są bardziej skomplikowane niż obliczenia na liczbach naturalnych, ponieważ liczby rzeczywiste są obiektami nieskończonymi i istnieje niezliczona liczba liczb rzeczywistych, dlatego liczb rzeczywistych nie można wiernie przedstawić za pomocą ciągów skończonych nad skończonym alfabetem. W przeciwieństwie do klasycznego obliczania ciągów skończonych, w którym różne modele …
1
Czy istnieje Rabin / Yao (przynajmniej w formie, którą można zacytować)?
W klasycznym artykule Andrew Chi-Chiha Yao z 1979 r. Nawiązuje do „MO Rabin i AC Yao w przygotowaniu”. Wynika to z tego, że złożoność komunikacji z błędem ograniczonym funkcji równości EQ (czy dwie liczby całkowite z zakresu od do są równe) wynosi .NN_N000N−1N−1N-1O(loglogN)O(log⁡log⁡N)O(\log\log N) Andrew Chi-Chih Yao, Niektóre pytania dotyczące …
4
Czy są jakieś dowody na nierozstrzygalność problemu zatrzymania, który nie zależy od samoreferencji lub diagonalizacji?
To pytanie jest z tym związane . Po wielu rozmowach po raz kolejny, w znacznie prostszej formie, wydawało się, że to zupełnie inne pytanie. Klasyczny dowód nierozstrzygalności problemu zatrzymania zależy od wykazania sprzeczności przy próbie nałożenia na siebie hipotetycznego decydenta HALT. Myślę, że oznacza to po prostu niemożność posiadania decydenta …
5
Kiedy randomizacja przyspiesza algorytmy i „nie powinna”?
Dowód Adlemana, że jest zawarty w pokazuje, że jeśli istnieje algorytm losowy dla problemu, który działa w czasie na wejściach o rozmiarze , to istnieje również algorytm deterministyczny dla problemu, który działa w czasie na materiale o wielkości [algorytm prowadzi randomizowane algorytm na niezależnych łańcuchów losowości. Musi istnieć losowość powtarzanego …
1
Algorytm sortowania, dzięki któremu każdy element jest porównywany razy i nie zależy od sieci sortującej
Czy istnieją znane algorytmy porównywania, które nie ograniczają się do sortowania sieci, tak że każdy element jest porównywany razy?O ( logn )O(log⁡n)O(\log n) O ile mi wiadomo, jedynym sposobem sortowania za pomocą porównania na każdym elemencie jest zbudowanie sieci sortującej AKS dla danych wejściowych i uruchomienie danych wejściowych w sieci …
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.