Teoretyczne informatyka

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

3
Jaka jest różnica między przepisywaniem terminów a dopasowywaniem wzorców?
Ponieważ w Lambda Ultimate nie było odpowiedzi , próbuję tutaj jeszcze raz: systemy przepisywania terminów są używane na przykład w automatycznym twierdzeniu potwierdzającym obliczenia symboliczne i oczywiście do zdefiniowania gramatyki formalnej. Istnieje kilka języków programowania opartych na przepisywaniu terminów, ale o ile rozumiem, pojęcie to jest bardziej znane jako dopasowanie …
5
Odzyskiwanie parsowanego lasu z parsera Earley?
Niedawno czytałem parser Earley i uważam, że jest to jeden z najbardziej eleganckich algorytmów, jakie do tej pory widziałem. Jednak algorytm w tradycyjnym znaczeniu jest rozpoznawaczem, a nie analizatorem składni, co oznacza, że ​​może wykryć, czy łańcuch pasuje do określonego CFG, ale nie wygenerować dla niego drzewa analizy. Moje pytanie …
1
Losowy sam unikający się cykl kratowy w obrębie danego obwiedni
W związku z układanką Slither Link zastanawiałem się: Załóżmy, że mam siatkę kwadratowych komórek i chcę znaleźć prosty cykl krawędzi siatki, równomiernie losowy wśród wszystkich możliwych prostych cykli.n × nn×nn\times n Jednym ze sposobów na to byłoby użycie łańcucha Markowa, którego stanami są zbiory kwadratów, których granice są prostymi cyklami …
2
Dolne granice wielkości formuły dla funkcji AC0
Pytanie: Jaka jest najbardziej znana dolna granica rozmiaru formuły dla jawnej funkcji w AC 0 ? Czy istnieje wyraźna funkcja z dolną granicą ?Ω(n2)Ω(n2)\Omega(n^2) Tło: Podobnie jak większość dolnych granic, dolne granice formuł są trudne do osiągnięcia. Interesują mnie dolne granice formuły powyżej standardowego uniwersalnego zestawu bram {AND, OR, NOT}. …
11
Przykład, w którym równoważność jest łatwa, ale znalezienie reprezentanta klasy jest trudne
Załóżmy, że mamy klasę obiektów (np. Wykresy, ciągi) i relację równoważności tych obiektów. W przypadku wykresów może to być izomorfizm wykresów. W przypadku ciągów moglibyśmy zadeklarować dwa równoważne ciągi, jeśli są one wzajemnie anagramami. Jestem zainteresowany obliczeniem przedstawiciela dla klasy równoważności. To znaczy, chcę funkcję f () taką, że dla …
1
Czy są typy typów? (Jakie są dokładnie typy?)
Dużo czytałem o systemach typów i takie i rozumiem z grubsza, dlaczego zostały wprowadzone (w celu rozwiązania paradoksu Russela). Rozumiem też z grubsza ich praktyczne znaczenie w językach programowania i systemach sprawdzających. Nie jestem jednak do końca pewien, czy moje intuicyjne wyobrażenie o typie jest prawidłowe. Moje pytanie brzmi: czy …
4
Jaka jest „najmniejsza” klasa złożoności, dla której znane jest obwody superliniowe?
Przepraszamy za zadawanie pytań, które z pewnością muszą znaleźć się w wielu standardowych źródłach. Ciekawi mnie dokładnie pytanie zawarte w tytule, w szczególności myślę o obwodach boolowskich, bez ograniczeń głębokości. W cudzysłowie wstawiam „najmniejszy”, aby umożliwić istnienie wielu różnych klas, o których nie wiadomo, że zawierają się w sobie, dla …
2
Gramatyka i typy wrażliwe na kontekst
1) Jaki, jeśli w ogóle, jest związek między pisaniem statycznym a gramatyką formalną? 2) Czy w szczególności byłoby możliwe, aby automat z ograniczeniem liniowym sprawdził, czy, powiedzmy, program C ++ lub SML był dobrze napisany? Automat zagnieżdżonego stosu? 3) Czy istnieje naturalny sposób na wyrażenie zasad pisania statycznego w formalnych …
6
Dlaczego badacz TCS potrzebuje finansowania?
Czytałem to . To mówi ... Nie będziesz głodować funduszy takich jak Pure Mathematics. (Nadal zawsze będziesz głodował po fundusze.) ... Dlaczego czystej matematycy potrzebują finansowania? (Ooops, pytanie o przepływ matematyki) Dlaczego ktoś prowadzący badania teoretyczne potrzebuje finansowania? Myślę, że narzędziami handlu są papiery, ołówki, laptop z dobrym połączeniem internetowym …
2
Przybliżenie rangi znaku macierzy
Ranga znaku macierzy A z wpisami + 1, -1 jest najmniejszą rangą (ponad rzeczywistymi) macierzy B, która ma taki sam wzór znaków jak A (tj. dla wszystkich i , j ). Pojęcie to jest ważne w złożoności komunikacji i teorii uczenia się.AijBij>0AijBij>0A_{ij}B_{ij}>0i,ji,ji,j Moje pytanie brzmi: czy są jakieś znane algorytmy …
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.