Teoretyczne informatyka

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

3
NP kompletne problemy graficzne na temat właściwości strukturalnych
(To pytanie jest trochę „ankietą”). Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie N.P.NP\mathcal{NP} -complete.For jakiegoś powodu mam problemy ze znalezieniem nawet …
1
Niewielkie zamknięte właściwości, które są wyraźnie wyrażalne przez MSO
Poniżej MSO oznacza monadyczną logikę drugiego rzędu grafów z kwantyfikacjami zbioru wierzchołków i zbocza. Niech będzie niewielką zamkniętą rodziną grafów. Z teorii drugorzędnej grafu Robertsona i Seymour wynika, że charakteryzuje się skończoną listą zakazanych nieletnich. Innymi słowy, dla każdego wykresu mamy, że należy do wtedy i tylko wtedy, gdy wyklucza …
1
Czy można rozstrzygać o równoważności jednoznacznych języków bezkontekstowych?
Dobrze wiadomo, że problem równoważności jest nierozstrzygalny dla ogólnych języków bezkontekstowych. Jednak wszystkie dowody tego faktu, o których jestem świadomy, wydają się obejmować pewne niejednoznaczne gramatyki bezkontekstowe. Z tego powodu chciałbym zapytać, czy wiadomo, czy problem pozostaje nierozstrzygalny, ograniczając się do jednoznacznych języków bezkontekstowych. To znaczy, biorąc pod uwagę dwie …
3
Dlaczego dwukropek oznacza, że ​​wartość należy do typu?
Pierce (2002) wprowadza relację pisania na stronie 92, pisząc: Relacja typowania wyrażeń arytmetycznych, zapisana „t: T”, jest zdefiniowana przez zestaw reguł wnioskowania przypisujących typy do terminów a przypis mówi: Symbol ∈∈\in jest często używany zamiast:. Moje pytanie brzmi po prostu, dlaczego teoretycy tekstu wolą używać: ponad ∈∈\in ? Jeśli typ …
4
Jak wymyślić nietrywialny pomysł w informatyce teoretycznej?
Jestem doktorantem pracującym w dziedzinie informatyki teoretycznej. Przeczytałem artykuły badawcze wielu badaczy i widziałem wiele narzędzi i matematyki, których używają do projektowania algorytmu. Na przykład patrz ten artykuł badawczy [Pierwotność w P] . Nie powiedziałbym, że ten artykuł badawczy opiera się na jednym lub dwóch pomysłach, ale opiera się na …
3
Obliczanie liczb rzeczywistych: zmiennoprzecinkowy vs TTE vs teoria domen vs itd
Obecnie obliczanie liczb rzeczywistych w najpopularniejszych językach jest nadal wykonywane za pomocą operacji zmiennoprzecinkowych. Z drugiej strony, teorie takie jak efektywność typu drugiego (TTE) i teoria domen od dawna obiecują dokładne obliczenie rzeczywistych liczb. Najwyraźniej problem precyzji zmiennoprzecinkowej nie zmniejszył się, więc dlaczego te teorie nie stały się bardziej popularne …
1
Edytuj odległość w przestrzeni podliniowej
Jaka jest najbardziej znana złożoność obliczenia dokładnej odległości edycji między dwoma ciągami o tej samej długości przy użyciu przestrzeni roboczej, która jest podliniowa w wielkości wejścia? Zakładam, że dane wejściowe są przechowywane w jakimś formacie tylko do odczytu. Czy to wcześniej badany problem? Aby uczynić pytanie nieco bardziej szczegółowym, co …
1
Stochastyczne obliczenia lambda Scotta
Ostatnio Dana Scott zaproponowała stochastyczny rachunek lambda, próbę wprowadzenia elementów probabilistycznych do (nietypowego) rachunku lambda w oparciu o semantykę zwaną modelem grafowym. Jego slajdy można znaleźć na przykład w Internecie , a jego artykuł w Journal of Applied Logic , t. 12 (2014). Jednak po szybkim przeszukaniu Internetu znalazłem podobne …
2
Algorytmy kwantowe oparte na transformatach innych niż transformaty Fouriera
W obliczeniach kwantowych i informacjach kwantowych Nielsena i Chuanga twierdzą, że wiele algorytmów opartych na kwantowych transformacjach Fouriera opiera się na właściwości niezmienniczości Coseta transformatów Fouriera i sugeruje, że właściwości niezmienniczości innych transformacji mogą dać nowe algorytmy. Czy przeprowadzono jakieś owocne badania nad innymi transformacjami?
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.