Informatyka

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

1
Algorytm do tłumaczenia deterministycznego automatu Büchi na LTL (jeśli to możliwe)
Logika LTL i deterministycznych automatów BUCHI są nieporównywalne: DBA nie może wyrazić , i nie mogą wyrażać LTL „co najmniej dziwne jest każda litera«a»” . Ale czasami interesujące jest, czy język DBA może być wyrażony w LTL.FGaFGaFGa Potrzebuję algorytmu, który decyduje, czy język danego DBA można opisać w LTL. Czy …
5
Język wartości funkcji afinicznej
Napisz n¯n¯\bar n dla dziesiętnego rozszerzenia nnn (bez wiodącego 0). Niech aaa i bbb będą liczbami całkowitymi o a>0a>0a > 0 . Rozważmy język rozwinięć dziesiętnych wielokrotności plus stałej:aaa M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈N}M={ax+b¯∣x∈N}M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \} Czy MMM regularne? bez kontekstu? (Kontrast z językiem wykresu funkcji afinicznej ) Myślę, że …
3
Intuicja za wartościami własnymi macierzy przylegania
Obecnie pracuję nad zrozumieniem użycia granicy Cheegera i nierówności Cheegera, a także ich zastosowania do podziału widmowego, przewodnictwa, ekspansji itp., Ale wciąż mam trudności z początkową intuicją dotyczącą drugiej wartości własnej macierzy przylegania. Zwykle w teorii grafów większość pojęć, które spotykamy, jest dość prosta do intuicji, ale w tym przypadku …
1
Dlaczego P i P / poli nie są takie same?
Definicja P jest językiem, o którym decyduje algorytm wielomianowy. Definicja P / poly może być rozumiana jako język, który może być ustalony przez obwód wielkości wielomianowej (patrz http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Dlaczego więc nie można symulować obwodu wielomianowego w czasie wielomianowym?
5
Czy istnieje znana metoda konstruowania gramatyki przy skończonym zestawie skończonych łańcuchów?
Z mojego czytania wynika, że ​​większość gramatyk dotyczy generowania nieskończonej liczby łańcuchów. Co jeśli pracowałeś na odwrót? Jeśli podano n łańcuchów o długości m, powinno być możliwe stworzenie gramatyki, która wygeneruje te łańcuchy i tylko te łańcuchy. Czy istnieje znana metoda wykonania tego? Idealnie nazwa techniki, którą mogę badać. Alternatywnie, …
2
Złożoność znalezienia związku z kompresją ścieżki, bez rangi
Wikipedia twierdzi, że związek według rangi bez kompresji ścieżki daje zamortyzowaną złożoność czasu O(logn)O(log⁡n)O(\log n)oraz że zarówno połączenie według kompresji rang, jak i ścieżki zapewnia zamortyzowaną złożoność czasową O(α(n))O(α(n))O(\alpha(n)) (gdzie αα\alphajest odwrotnością funkcji Ackermana). Jednak nie wspomina o czasie działania kompresji ścieżki bez rangi związkowej, co zwykle realizuję sam. Jaka …
1
Dlaczego porównania są tak drogie na GPU?
Próbując poprawić wydajność mojej klasy wykrywania kolizji, odkryłem, że ~ 80% czasu spędzonego na GPU spędza na warunkach, jeśli tylko próbuję ustalić granice wiader, przez które powinna się zapętlać. Dokładniej: każdy wątek otrzymuje identyfikator, przez ten identyfikator pobiera swój trójkąt z pamięci (3 liczby całkowite), a przez te 3 pobiera …
1
Dowód złożoności czasu dla implementacji problemu segmentu dystansowego w drzewie segmentów
Rozumiem, że drzewa segmentów można wykorzystać do znalezienia sumy podgrupy ZAAA. I to można zrobić wO (logn )O(log⁡n)\mathcal{O}(\log n)czas zgodnie z tutorialem tutaj . Jednak nie jestem w stanie udowodnić, że czas na zapytanie jest rzeczywiście O (logn )O(log⁡n)\mathcal{O}(\log n). Ten link (i wiele innych) mówi, że możemy udowodnić, że …
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.