Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Czy język wyrażeń regularnych wymaga automatycznych mechanizmów wypychania w celu jego parsowania?
Chcę przekonwertować wprowadzone przez użytkownika wyrażenie regularne na NFA, aby móc następnie uruchomić NFA dla łańcucha w celu dopasowania. Jakiej minimalnej maszyny można użyć do parsowania wyrażeń regularnych? Zakładam, że musi to być automat push, ponieważ obecność nawiasów oznacza konieczność liczenia, a DFA / NFA nie może wykonać dowolnego liczenia. …
3
Jak szybko możemy znaleźć wszystkie kombinacje czterech kwadratów, które sumują się do N?
Pytanie zostało zadane w Stack Overflow ( tutaj ): Biorąc pod uwagę całkowitą wydrukować wszystkie możliwe kombinacje wartości całkowitych z i dzięki którym rozwiązuje się równanie .N.N.NA , B , C.ZA,b,doA,B,CrereDZA2)+ B2)+ C.2)+ D2)= NZA2)+b2)+do2)+re2)=N.A^2+B^2+C^2+D^2 = N To pytanie jest oczywiście związane z hipotezą Bacheta w teorii liczb (czasami nazywaną …
2
Rekonstrukcja wykresów z rozkładu stopni
Biorąc pod uwagę rozkład stopni, jak szybko możemy zbudować wykres zgodny z danym rozkładem stopni? Szkic łącza lub algorytmu byłby dobry. Algorytm powinien zgłaszać „brak”, ponieważ nie można zbudować żadnego wykresu i dowolnego przykładu, jeśli można zbudować wiele wykresów.
2
Wyrocznia do oddzielenia NP od CoNP
Jak udowodnić, że ? Właśnie szukam takiej wyroczni TM M i języka rekurencyjnego L ( M ) = L, dla którego to się utrzymuje.NPA≠coNPANPA≠coNPA\mathsf{NP}^A \neq \mathsf{coNP}^AMMML(M)=LL(M)=LL(M) = L Znam dowód gdzie można pokazać, że nie jest wyrocznią takie, że P ≠ N P i wyrocznią takie, że P = N …
1
Co to jest klasa złożoności
Co oznacza klasa złożoności ? Wiem, że jest klasą złożoności, która zawiera języki dla których istnieje wielomianowa niedeterministyczna maszyna Turinga taka, że iff liczba akceptujących stanów maszyny na wejściu jest nieparzysta. ⊕ P A M x ∈ A M x⊕P⊕P⊕P⊕P\oplus P^{\oplus P}⊕P⊕P\oplus PAAAMMMx∈Ax∈Ax \in AMMMxxx Ale co oznacza ? Po …
2
Czy redukcja karp jest identyczna z redukcją Levina
Definicja: Redukcja karp Język jest karpem redukowalnym do języka jeśli istnieje funkcja obliczalna w czasie wielomianowym tak, że dla każdego , wtedy i tylko wtedy, .AAABBBf:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f:\{0,1\}^*\rightarrow\{0,1\}^*xxxx∈Ax∈Ax\in Af(x)∈Bf(x)∈Bf(x)\in B Definicja: Redukcja Levina Problem wyszukiwania można sprowadzić do Levina do problemu wyszukiwania jeśli istnieje funkcja czasu wielomianowego której Karp redukuje do a …
4
Operacje, w których klasa nierozstrzygalnych języków nie jest zamknięta
Czy istnieją nierozstrzygalne języki, tak że ich związek / język przecięcia / konkatenacji jest rozstrzygalny? Jaka jest fizyczna interpretacja takiego przykładu, ponieważ ogólnie nierozstrzygalne języki nie są zamknięte w ramach tych operacji? Co możemy powiedzieć o zamknięciu kleene? Czy mamy też na to przykłady? Czy to znaczy, że zamknięcie nierozstrzygalnego …
1
O algorytmie redukcji Codda
Algorytm Codda konwertuje wyrażenie w krotkowym rachunku relacyjnym na relacyjną algebrę. Czy istnieje standardowa implementacja algorytmu? Czy ten algorytm jest używany gdziekolwiek? (Wydaje się, że branża potrzebuje tylko SQL i wariantów, nie jestem pewien co do teoretyków baz danych w środowisku akademickim). Jaka jest złożoność redukcji? Zostało to opublikowane w …
1
Znajdź najkrótsze ścieżki na zważonym wykresie unipatycznym
Mówi się, że ukierunkowany wykres jest unipatyczny, jeśli dla dowolnych dwóch wierzchołków i na wykresie istnieje co najwyżej jedna prosta ścieżka od do .uuuvvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Załóżmy, że otrzymałem wykres jednoczynnościowy taki, że każda krawędź ma dodatnią lub ujemną wagę, ale nie zawiera żadnych ujemnych cykli masy.GGG Z tego chcę znaleźć algorytm, …
2
Czy wszystkie języki bezkontekstowe i zwykłe są skutecznie rozstrzygalne?
Natknąłem się na ten rysunek, który pokazuje, że języki kontekstowe i zwykłe są (odpowiednimi) podzbiorami sprawnych problemów (podobno ). Doskonale rozumiem, że wydajne problemy stanowią podzbiór wszystkich rozstrzygalnych problemów, ponieważ możemy je rozwiązać, ale może to zająć bardzo dużo czasu.P.P\mathrm{P} Dlaczego wszystkie bezkontekstowe i regularne języki są skutecznie rozstrzygalne? Czy …
1
Czy twierdzenie smn to ta sama koncepcja co curry?
Studiuję twierdzenie smn, a koncepcja przypominała mi curry. Z artykułu w Wikipedii o twierdzeniu smn : twierdzenie mówi, że dla danego języka programowania i dodatnich liczb całkowitych m i n istnieje szczególny algorytm, który przyjmuje jako dane wejściowe kod źródłowy programu z m + n dowolnymi zmiennymi, wraz z m …
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.