Teoretyczne informatyka

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

1
Uogólnianie FFT
Czy dzielenie i podbijanie FFT może być automatycznie uogólnione na inne transformacje (z Transform, ćwierkanie itp.) Automatycznie? Czy istnieje algorytm, który przyjmuje opis transformacji (nie wiem, jakie informacje byłyby potrzebne) i może wygenerować szybką funkcję podobną do FFT?
3
Bardziej intuicyjny dowód twierdzenia o strefie?
Twierdzenie o strefie mówi, że jeśli dźgniemy układ n linii inną linią, całkowita złożoność jego strefy , zbiór wszystkich ścian 0, 1 i 2 sąsiadujących z nią, wynosi O (n). Rzeczywista stała to mniej więcej 6n, jak podano w różnych podręcznikach, a dowodem jest indukcja z rozsądnie ostrożnym argumentem ładowania. …
5
Jakie są dobre referencje na temat zrozumienia uczenia się online?
W szczególności proszę o zasoby, aby dowiedzieć się o systemach uczenia maszynowego, które mogą aktualizować ich odpowiednie sieci przekonań (lub ich odpowiedniki) podczas pracy. Natknąłem się nawet na kilka, ale nie udało mi się ich dodać do zakładek. Jak można sobie wyobrazić, wyszukiwanie w Internecie jest dość trudne.
1
Naturalni kandydaci na NP-E i E-NP
Od wczesnych lat 70. wiadomo, że i nie są równe (ponieważ nie jest zamknięty w czasie wielomianowym wiele -jedna redukcja, w przeciwieństwie do ). O ile mi wiadomo, wciąż pozostaje otwarte, czy jedna klasa jest podzbiorem drugiej, czy też są nieporównywalne, co oznacza, że i są niepuste.NPNP{\bf NP}E=DTIME(2O(n))E=DTIME(2O(n)){\bf E}=DTIME(2^{O(n)})EE{\bf E}NPNP{\bf …
1
Na jakie „pytanie” stara się odpowiedzieć teoria języka programowania?
Od jakiegoś czasu interesowałem się różnymi tematami, takimi jak logika kombinacyjna, rachunek lambda, programowanie funkcjonalne i studiowałem je. Jednak w przeciwieństwie do „teorii obliczeń”, która stara się odpowiedzieć na pytanie „obliczalności”, tj. Rzeczy, które można / nie można obliczyć z różnymi ograniczeniami, staram się znaleźć analogię do „teorii programowania” Wikipedia …
1
Jaka jest domniemana zależność między językami P (PTime) i Type 1 (kontekstowymi)?
Nie wiadomo czy P⊆CSLP⊆CSLP\subseteq CSL lub P⊈CSLP⊈CSLP\not\subseteq CSL, gdzie PPP jest zbiorem wszystkich języków rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga, oraz CSLCSLCSL jest klasą języków kontekstowych, znanych jako równoważne NSPACE(O(n))NSPACE(O(n))NSPACE(O(n)) , języki ustalane przez automaty ograniczane liniowo. W przypadku wielu otwartych pytań istnieje tendencja do jednej odpowiedzi ( …
1
Czy złożoność Kołmogorowa w tabelach prawdy problemu zatrzymania jest znana asymptotycznie?
Pozwolić HALTnHALTnHALT_n oznacz ciąg długości 2n2n2^n odpowiadający tabeli prawdy problemu zatrzymania dla danych wejściowych długości nnn. Jeśli sekwencja złożoności Kołmogorowa K(HALTn)K(HALTn)K(HALT_n) byli O(1)O(1)O(1), wtedy jeden z ciągów porad byłby używany nieskończenie często, a TM z tym ciągiem zakodowanym na stałe byłby w stanie rozwiązać HALTHALTHALT równomiernie nieskończenie często, o czym …
1
Oceń obwód logiczny na partii podobnych danych wejściowych
Załóżmy, że mam obwód boolowski CCC która oblicza jakąś funkcję f:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}. Załóżmy, że obwód składa się z AND, OR i NOT bramek z wachlarzem i wachlowaniem co najwyżej 2. Pozwolić x∈{0,1}nx∈{0,1}nx \in \{0,1\}^nbyć danym wkładem. DanyCCC i xxx, Chcę ocenić CCC na nnn dane wejściowe, które różnią się …
1
Powiązanie uniwalencji teorii teorii kości z koncepcją szkieletu
Powiedzmy, że pracuję w teorii typów homotopii, a moim jedynym przedmiotem badań są kategorie konwencjonalne. Równoważności są podane przez funktory i które zapewniają równoważność kategorii . Istnieją naturalne izomorfizmy i więc ten funktor i „odwrotny” funktor są przekształcane w funktor jednostkowy.fa: D ⟶ CF:D⟶CF:{\bf D}\longrightarrow{\bf C}G : C ⟶ DG:C⟶DG:{\bf …
1
Dlaczego komplementarność jest ważna?
Komplementarny luz (CS) jest powszechnie nauczany, gdy mówi się o dualności. Ustanawia ładny związek między pierwotnym a podwójnym ograniczeniem / zmiennymi z matematycznego punktu widzenia. Dwa główne powody stosowania CS (zgodnie z nauczaniem na kursach dla absolwentów i podręcznikach): Aby sprawdzić optymalność LP Aby pomóc rozwiązać problem podwójny Biorąc pod …
1
Wielojęzyczna minimalizacja DFA
Jestem zainteresowany niewielkim uogólnieniem DFA. Jak zwykle mamy ustawiony stan , skończony alfabet , działanie zdefiniowane na przez i stan początkowy ; lecz w zwykłym zestawem terminali wziąć rodziny podzbiorów . Wielojęzyczny DFA jest wtedy krotkąQQQΣΣ\SigmaΣ∗Σ∗\Sigma^*QQQδ:Q×Σ→Qδ:Q×Σ→Q\delta : Q\times\Sigma\rightarrow Qq0q0q_0(Ti)i∈1..n(T.ja)ja∈1 ..n(T_i)_{i\in 1..n}QQQMM.M (Q,Σ,δ,q0,(Ti))(Q,Σ,δ,q0,(T.ja))(Q, \Sigma, \delta, q_0, (T_i)) a jest rozpoznawany przez …
1
Prawidłowa nauka PAC 2-DNF w jednolitym rozkładzie
Jaki jest najnowszy wynik w zakresie złożoności zapytań dotyczących prawidłowych formuł uczenia się PAC 2-DNF z przykładowymi zapytaniami i w jednolitym rozkładzie ? A może jakieś nietrywialne ograniczenia? Ponieważ w ogóle nie znam teorii uczenia się, a to pytanie jest motywowane inną dziedziną, odpowiedź może być oczywista. Sprawdziłem książkę Kearnsa …
2
Niekonstruowalne funkcje i nietypowe wyniki
W książce Arora-Barak w definicji funkcji konstruowalnych w czasie mówi się, że użycie funkcji, które nie są konstruowalne w czasie, może prowadzić do „anomalnych wyników”. Czy ktoś ma przykład takiego „anomalnego wyniku”? Słyszałem w szczególności, że mogą istnieć funkcje, których nie utrzymuje twierdzenie o hierarchii czasu, czy ktoś ma przykład …
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.