Informatyka

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

1
Sztuczka zastosowana w dowodzie podwójnie wykładniczej złożoności arytmetyki Presburger'a
Wysłałem to na MathUnderflow, ale nie otrzymałem odpowiedzi, więc pomyślałem, że spróbuję tutaj, Czytam stary artykuł Rabina i Fischera [opublikuje link, jeśli to możliwe], gdzie między innymi udowodniono podwójnie wykładniczą złożoność arytmetyki Presburger'a. Dowód opiera się na istnieniu formuły jan( x )In(x)I_{n}(x) nieformalne stwierdzenie „x &lt;2)2)k x + 1x&lt;22kx+1x < …
1
Jak zmierzyć złożoność problemu dyskretnego logarytmu?
Odpowiedzi na to pytanie na Crypto Stack Exchange mówią w zasadzie, że aby zmierzyć złożoność problemu z logarytmem, musimy wziąć pod uwagę długość liczby reprezentującej wielkość grupy. Wydaje się to arbitralne, dlaczego nie wybraliśmy wielkości grupy jako argumentu? Czy istnieje kryterium pozwalające ustalić, który argument wybrać? W rzeczywistości wiem, że …
3
Dlaczego stan pozostaje niezmieniony w niewielkiej semantyce operacyjnej pętli while?
Zwykle widzę, że w strukturalnej reprezentacji operacyjnej semantyki dla pętli while stan programu nie zmienia się: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \> else \> SKIP, \sigma) Dla mnie nie jest to intuicyjne, jeśli stan się nie …
2
Warunki, aby wykres dwudzielny był płaski, bez krawędzi biegnących wokół wierzchołków
Dwustronny wykres jest płaski, jeśli nie ma nieletnich lub .K.3 , 3K3,3K_{3, 3}K.5K5K_5 Szukam koniecznych i / lub wystarczających warunków, aby umożliwić rysunki planarne bez krawędzi „przechodzących” przez zestawy wierzchołków. Są to rysunki spełniające: Wszystkie wierzchołki jednej części są rysowane na jednej linii pionowej. Wierzchołki drugiej części są rysowane na …
2
Ograniczenie maksymalnego przepływu do dopasowania dwustronnego?
Istnieje słynna i elegancka redukcja od maksymalnego problemu dwustronnego dopasowania do problemu maksymalnego przepływu: tworzymy sieć z węzłem źródłowym , węzłem końcowym i jednym węzłem dla każdego elementu, który ma być dopasowany, a następnie dodajemy odpowiednie krawędzie.sssttt Z pewnością istnieje sposób na ograniczenie maksymalnego przepływu do maksymalnego dopasowania dwustronnego w …
1
Czy potrafimy znaleźć k najkrótszych ścieżek między wszystkimi parami szybciej niż wielokrotne rozwiązywanie problemu parami?
Chcę produkować kkk najkrótsza droga (kkkbyłoby mniej niż 10) między wszystkimi parami na wykresie. Wykres to (właściwie mapa metra): dodatnio ważony bezkierunkowy rzadki z około 100 węzłami Mój obecny plan ma zastosowanie kkknajkrótsza ścieżka trasy do każdej pary; Teraz szukam bardziej wydajnej alternatywy (prawdopodobnie z programowaniem dynamicznym).
1
Unikalne dualne triangulacje prostych wielokątów
Biorąc pod uwagę triangulację (bez punktów Steinera) prostego wielokąta , można rozważyć podwójność tej triangulacji, która jest zdefiniowana następująco. Tworzymy wierzchołek dla każdego trójkąta w naszej triangulacji i łączymy dwa wierzchołki, jeśli odpowiednie trójkąty mają wspólną krawędź. Podwójny wykres jest znany jako drzewo o maksymalnym stopniu trzecim.P.PP W przypadku mojej …
1
Czy stosowane jako stos wywołań wolne od śmieci stosy spaghetti tworzą DAG?
Patrzę na techniki implementacji języków programowania, a ostatnio natknąłem się na stosy spaghetti, które podobno dobrze pasują do modelu stylu kontynuacji przechodzenia (biorąc pod uwagę ich zastosowanie np. W Scheme i SML / NJ ). Dla uproszczenia rozważmy tylko jedno-wątkowe procesy dla tego pytania. Jestem jednak nieco zdezorientowany schematem na …
2
Czy to możliwe, że problem zatrzymania można rozwiązać dla wszystkich danych wejściowych oprócz kodu maszyny?
To pytanie przyszło mi do głowy z powodu problemu z zatrzymaniem i nie mogłem znaleźć dobrej odpowiedzi online, zastanawiając się, czy ktoś może pomóc. Czy jest możliwe, że problem zatrzymania jest rozstrzygalny dla dowolnej TM na dowolnym wejściu, o ile wejście nie jest samą TM? Gruntownie: Halts(TM, I) IF TM …
4
Dlaczego powinniśmy studiować wszystkie trzy formy reprezentacji automatów skończonych?
DFA, NFA i epsilon NFA wszystkie trzy pozwalają nam reprezentować konkretny język. Za pomocą dowolnej z tych reprezentacji możemy dojść do tego samego wyrażenia regularnego, dlaczego więc musimy studiować wszystkie trzy formy reprezentacji automatów skończonych? Można wyjaśnić, co NFA może zrobić, czego DFA nie może zrobić, to znaczy, że NFA …
1
Randomized Meldable Heap - Oczekiwana wysokość
Randomizowane zgrzewalne stosy mają operację „łączenie”, której następnie używamy do zdefiniowania wszystkich innych operacji, w tym wstawiania. Pytanie brzmi: jaka jest oczekiwana wysokość tego drzewa nnn węzły? Twierdzenie 1 Gambina i Malinkowskiego, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, ss. 344–349, 1998; …
3
Konstruktywna wersja rozstrzygalności?
Dzisiaj podczas lunchu poruszyłem ten problem z kolegami i ku mojemu zdziwieniu argument Jeffa E., że problem jest rozstrzygalny, nie przekonał ich ( oto ściśle powiązany post na temat przepływu matematyki). Stwierdzenie problemu, które jest łatwiejsze do wyjaśnienia („czy P = NP?”) Jest również rozstrzygalne: albo tak, albo nie, a …
2
Jak udowodnić, że 3-kolorowanie jest rozstrzygalne?
Czy w celu udowodnienia, że ​​3-zabarwienie jest rozstrzygalne, wystarczy powiedzieć: Każdy węzeł na wykresie ma 3 możliwe kolory Dlatego możemy policzyć wszystkie możliwości, a następnie sprawdzić, czy żadne dwie krawędzie nie łączą węzłów o tym samym kolorze3n3n3^n Czy to dowodzi, że 3-kolorowanie jest rozstrzygalne? Czy też muszę zbudować maszynę Turinga, …
1
Co robi strzałka w górę (
Uczę się drzew punktów obserwacyjnych i spotkałem się z tym, czytając artykuł Struktury danych i algorytmy wyszukiwania najbliższych sąsiadów w ogólnych przestrzeniach metrycznych, autorstwa Petera Yianilosa ( Proceedings of SODA 1993 , SIAM, strony 311–321; PDF ). Poniższy pseudokod pojawia się w algorytmie 1. funkcja Make_vp_tree (S)jeśli S= ∅, a …
9 notation 
3
DFA za akceptację wszystkich ciągów binarnych mocy formy
Możemy utworzyć DFA, przyjmując liczby binarne podzielne przez .nnn Na przykład DFA akceptujący liczby binarne podzielne przez 2 można utworzyć w następujący sposób: Podobnie DFA akceptujący liczby binarne podzielne przez 3 można utworzyć w następujący sposób: Możemy zastosować dobrze zdefiniowaną procedurę, aby utworzyć tego rodzaju DFA. Czy jednak może istnieć …
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.