Informatyka

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

3
Multicore SAT Solver
Próbuję rozwiązać problem SAT z 25k klauzul 5k zmiennych. Ponieważ działa od godziny (precosat), a potem chciałbym rozwiązać większe, szukam wielordzeniowego SAT-Solvera. Ponieważ wydaje się, że jest wiele rozwiązań SAT, jestem całkiem zagubiony. Czy ktoś mógłby wskazać mi najlepszy dla mojej sprawy? Byłbym również szczęśliwy, gdyby ktoś mógł podać mi …
2
Czy kompletność coNP implikuje twardość NP?
Czy kompletność coNP implikuje twardość NP? W szczególności mam problem, który wykazałem, że jest kompletny coNP. Czy mogę twierdzić, że jest to trudne NP? Zdaję sobie sprawę, że mogę żądać twardości coNP, ale nie jestem pewien, czy ta terminologia jest standardowa. Nie mam nic przeciwko twierdzeniu, że jeśli problem NP-zupełny …
1
Zliczanie liczby sum z przyległych podtablic tablicy
Otrzymujemy tablicę ze wszystkimi .a[1…n]a[1…n]a[1 \ldots n]a[i]>0a[i]>0a[i]>0 Teraz musimy dowiedzieć się, ile różnych sum można uformować z jego podstron (gdzie podtablica to ciągły zakres tablicy, tj. dla niektórych , suma jest sumą wszystkich elementy podtablicy). Na przykład, jeśli , to odpowiedź brzmi 4: możemy utworzyć .a[j…k]a[j…k]a[j\ldots k]j,kj,kj,ka=[1,2,1]a=[1,2,1]a=[1,2,1]1,2,3,41,2,3,4 1,2,3,4 Wiem, jak …
2
Maszyny Turinga z pojedynczą taśmą z wejściem chronionym przed zapisem rozpoznają tylko zwykłe języki
Oto problem: Udowodnij, że maszyny Turinga z pojedynczą taśmą, które nie mogą pisać na części taśmy zawierającej łańcuch wejściowy, rozpoznają tylko zwykłe języki. Moim pomysłem jest udowodnienie, że ta konkretna baza TM jest odpowiednikiem DFA. Używanie tej TM do symulacji DFA jest bardzo proste. Jednak gdy chcę użyć tego DFA …
2
Czy istnieje formalna definicja CS VCS i wersji plików?
Nie wiem, czy to był żart, ale kiedy przeczytałem coś, co nazywano formalną definicją pliku w systemie kontroli wersji, takim jak git, hg lub svn. To było coś w rodzaju przedmiotu matematycznego, takiego jak homeomorfizm. Czy to był żart, czy naprawdę istnieje teoria informatyki na temat systemów wersjonowania i matematyki …
2
Wykazać kompletność NP decydującej o satysfakcji monotonicznej formuły boolowskiej
Próbuję rozwiązać ten problem i naprawdę walczę. Monotoniczne logiczna wzór jest wzorem w zdań logiki, gdy wszystkie literałami dodatnie. Na przykład, ( x1∨ x2)) ∧ ( x1∨ x3)) ∧ ( x3)∨ x4∨ x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5) jest monotoniczną funkcją logiczną. …
2
Algorytm liniowego oznaczania czasu dla drzewa?
Mam drzewo bezkierunkowe, którego wierzchołki chcę opisać. Węzły liści powinny być oznaczone jako jeden. Następnie załóżmy, że liście zostały usunięte. W drzewie, które pozostaje, liście powinny być oznaczone jako dwa. Proces ten trwa w oczywisty sposób, dopóki wszystkie wierzchołki nie będą miały etykiety. Powodem tego jest to, że chcę przechowywać …
12 algorithms  trees 
4
Czy złożoność problemów silnie NP-trudnych lub -kompletnych zmienia się, gdy ich dane wejściowe są kodowane w sposób jednoznaczny?
Czy trudność silnie trudnego NP lub problemu NP-zupełnego (jak np. Zdefiniowano tutaj ) zmienia się, gdy jego wejście jest jednoargumentowe zamiast kodowane binarnie? Jaką różnicę ma to, że wejście problemu silnie trudnego NP jest zakodowane w sposób jednoznaczny? Chodzi mi o to, że jeśli wezmę na przykład słabo NP-kompletny problem …
3
Znaczenie normalnych form, takich jak normalna forma Chomsky'ego dla CFG
Rozumiem, że gramatyki bezkontekstowe mogą być używane do reprezentowania języków bezkontekstowych. Mogą być niejasne. Mamy również normalne formy, takie jak normalna postać Chomsky'ego i Greibacha . Nie mogłem zrozumieć takiej potrzeby. Dlaczego są ważne w teorii języków? Wszystkie podręczniki, o których mówiłem, mówią o tych normalnych formach, ale nie mówią …
2
Jeśli
Na przykład, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Jak więc możemy udowodnić, że L∗L∗L^* jest regularne? Jeśli LLL jest regularne, to oczywiście L∗L∗L^* jest również regularne. Jeśli LLL jest skończone, to jest regularne i znowu L∗L∗L^* jest regularne. Zauważyłem również, że dla L={0p∣p is a prime}L={0p∣p is a prime}L = \{0^p \mid …
4
Uczenie maszynowe a identyfikacja systemu?
Czy ktoś mógłby mi wyjaśnić różnice i podobieństwa między uczeniem maszynowym a identyfikacją systemu? Czy to tylko dwie nazwy tego samego? Na tej stronie mówią: Społeczności uczenia maszynowego i identyfikacji systemów mają do czynienia z podobnymi problemami, gdy trzeba zbudować model na podstawie ograniczonych lub hałaśliwych obserwacji. Przeczytałem również wczesne …
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.