Informatyka

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

3
Zwykłe języki, których nie można wyrazić za pomocą tylko 2 operacji wyrażenia regularnego
Myślałem, że wszystkie języki regularne można wyrazić za pomocą wyrażeń regularnych (jeśli język jest regularny, można go wyrazić za pomocą wyrażenia regularnego), ale powiedziano mi, że potrzebujesz do tego wszystkich trzech operacji regularnych (konkatenacji, zjednoczenia i gwiazdki) trzymać. Powiedziano mi na przykład, że jeśli mogę korzystać tylko z operacji wyrażenia …
2
Czy problem korespondencyjny występuje w NP?
Właśnie przeczytałem kilka stron w książce Sipsera Wprowadzenie do teorii obliczeń na temat problemu z korespondencją pocztową i myślę, że PCP jest w rzeczywistości w NP. Certyfikującej wynosi: dla konfiguracji wejściowej stos łączenie T 1 , T 2 , . . . , t n jako ciąg t i konkatenacja …
2
Jak udowodnić P
Zdaję sobie sprawę, że wydaje się to bardzo głupie (lub zbyt oczywiste, by stwierdzić) pytanie. Jednak w pewnym momencie jestem zdezorientowany. Możemy pokazać, że P NP=== wtedy i tylko wtedy, gdy możemy zaprojektować algorytm, który rozwiązuje dowolny przypadek problemu w NP w czasie wielomianowym. Nie rozumiem jednak, jak, u licha, …
1
Napełnianie pojemników parami kulek
Kosz jest nazywany pełnym, jeśli zawiera co najmniej kulek. Naszym celem jest, aby jak najwięcej pojemników było pełnych.kkk W najprostszym scenariuszu otrzymujemy piłek i możemy je dowolnie rozmieścić. W takim przypadku, oczywiście najlepsze, co możemy zrobić, to wybrać kosze i umieścić dowolnie kulki w każdej z nich.nnn⌊n/k⌋⌊n/k⌋\lfloor n/k \rfloorkkk Interesuje …
1
Różnica między wyrażeniem regularnym a gramatyką w automatach
Jestem nowy w automatach. Krótkie wprowadzenie do wyrażeń regularnych otrzymałem wczoraj. Przeczytałem różne reguły definiujące wyrażenie regularne. Ale nie jestem w stanie odróżnić wyrażeń regularnych od gramatyki języka (nie uczono mnie gramatyki wyrażeń regularnych). Rozumiem, że gramatyka pomaga nam generować poprawne ciągi w języku, ale wtedy właśnie takie są reguły …
1
Edytuj odległość listy za pomocą unikalnych elementów
Odległość edycji Levenshtein-Distance między listami jest dobrze zbadanym problemem. Ale nie mogę znaleźć wiele możliwych ulepszeń, jeśli wiadomo, że żaden element nie występuje więcej niż raz na każdej liście . Załóżmy również, że elementy są porównywalne / sortowalne (ale listy do porównania nie są sortowane na początek). O(min(m,n)s)O(min(m,n)s)O(\min(m,n)s)O(min(s,m,n)s)O(min(s,m,n)s)O(\min(s,m,n)s)sss Bardziej formalnie, …
1
Czy są jakieś znane problemy z kompletnym AM / czy kompletne AM jest dobrze zdefiniowane?
Jestem ciekawy, czy w klasie złożoności Arthura-Merlina występują jakieś kompletne problemy. Graph Non-Isomorphism (GNI) wydaje się być kanonicznym przykładem problemu w AM, ale prawdopodobnie nie jest kompletny. Chyba zastanawiam się również, czy „kompletny” problem jest dobrze zdefiniowany dla AM. Ponieważ AM = BP.NP, wydaje się, że przejście na „redukcję” do …
1
Jaki jest pożytek ze znalezienia minimalnej liczby linii prostych w celu pokrycia zestawu punktów?
Istnieje popularny problem [1] [2] w informatyce, który polega na znalezieniu minimalnej liczby linii prostych pokrywających dany zestaw punktów w 2D. Mimo że zeskanowałem wiele artykułów, żaden z nich nie ma wyraźnej motywacji do rozwiązania problemu. Jaki jest pożytek z rozwiązania tego problemu? Czy istnieje dokument, który to wyjaśnia?
2
Dobra struktura danych migawkowych dla indeksu w pamięci
Projektuję bazę danych obiektów w pamięci dla bardzo konkretnego przypadku użycia. Jest to pojedynczy program piszący, ale musi obsługiwać wydajne jednoczesne odczyty. Odczyty muszą być izolowane. Nie ma języka zapytań, baza danych obsługuje tylko: pobierz obiekt / -y przez atrybut / zestaw atrybutów (może istnieć obsługa wyrażeń, np. x.count < …
2
Dlaczego twierdzenie Schaefera nie dowodzi, że P = NP?
To chyba głupie pytanie, ale po prostu nie rozumiem. W kolejnym pytaniu wymyślili dychotomia twierdzenia Schaefer jest . Dla mnie wygląda na to, że udowadnia, że ​​każdy problem CSP jest w P lub NP-kompletny, ale nie pomiędzy. Skoro każdy problem NP można przekształcić w czasie wielomianowym w CSP (ponieważ CSP …
2
Czy uogólniony XOR-SAT jest sprawnie rozwiązywalny?
Widziałem, w jaki sposób XOR-3-SAT można skutecznie rozwiązać (na przykład zobacz sekcję „Zgodność XOR” we wpisie w Wikipedii na temat problemu logicznej satysfakcji ). Zastanawiam się nad podstawowym pytaniem: czy XOR-k-SAT można skutecznie rozwiązać w przypadku formuł o różnej ilości literałów w klauzuli? Naprawdę chciałbym wiedzieć, czy możemy zwiększyć liczbę …
3
Czy dowód nierozstrzygalności problemu zatrzymania oszukuje poprzez odwrócenie wyników?
Mam problem ze zrozumieniem problemu zatrzymania Turinga. Jego dowód zakłada, że ​​istnieje magiczna maszyna która może ustalić, czy komputer zatrzyma się lub zapętli na zawsze dla danego wejścia. Następnie dołączamy inną maszynę, która odwraca dane wyjściowe i mamy sprzeczność i dlatego H nie może istnieć.H.HHH.HH Obawiam się, że wydaje się, …
3
Jak utworzyć DFA z wyrażenia regularnego bez użycia NFA?
Celem jest utworzenie DFA z wyrażenia regularnego, a użycie opcji „Regular exp> NFA> Konwersja DFA” nie jest opcją. Jak należy to zrobić? Zadałem to pytanie naszemu profesorowi, ale powiedział mi, że możemy korzystać z intuicji i uprzejmie odmówił podania jakichkolwiek wyjaśnień. Więc chciałem cię zapytać. Opcja „Regular exp> NFA> Konwersja …
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.