Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Czy jest rozstrzygalne, czy długość wyjściowa przetwornika jest ograniczona długością wejściową?
Rozważane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff .[ T ] y x x [ T ] yT.TT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pytanie: Czy można rozstrzygnąć następujący problem: Biorąc pod uwagę: Przetwornik …
1
Czy `sort 'można pisać na elementarnej logice afinicznej?
Następujący termin λ, tutaj w formie normalnej: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Implementuje algorytm sortowania dla list zakodowanych w kościele. Oznacza to, że wynik: sort (λ c n . (c 3 (c 1 (c 2 n)))) β→ (λ c n . (c 1 (c 2 (c 3 n)))) Podobnie, sort_below …
2
Losowy spacer i średni czas trafienia na prostym niekierowanym wykresie
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ ) τGsolGO(τ)O(τ)O(\tau)ττ\tauτ=∑v∈Vπ(v)⋅H(u,v),τ=∑v∈V.π(v)⋅H.(u,v),\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), ππ\pi to rozkład …
1
Jak kodujesz abstrakcyjny algorytm Lampinga za pomocą kombinacji interakcji?
Kombinatory interakcji były wcześniej proponowane jako cel kompilacji dla rachunku λ. Ten papier implementuje pełny rachunek λ. Wiadomo również, że możliwe jest zoptymalizowanie kodowania sieci interakcji rachunku λ dla podzbioru terminów λ, który jest typowy dla EAL. W tym artykule zaimplementowano ten podzbiór rachunku λ, tłumacząc wyrażenia λ typu EAL …
1
Czy ktoś zna przeciwny przykład algorytmu grafowego izomorfizmu Dharwadkera-Teveta?
Na stronie http://www.dharwadker.org/tevet/isomorphism/ znajduje się prezentacja algorytmu do określania, czy dwa wykresy są izomorficzne. Biorąc pod uwagę wiele „powiedzmy” interesujących twierdzeń A Dharwadkera, nie jestem skłonny w to uwierzyć. W trakcie mojego dochodzenia stwierdziłem, że algorytm z pewnością da poprawną odpowiedź i powiem, że dwa wykresy nie są izomorficzne, chociaż …
2
Czy dziedziczna klasa grafów może zawierać prawie wszystkie, ale nie wszystkie, wykresy n-wierzchołkowe?
Niech będzie dziedziczną klasą grafów. (Dziedziczne = zamknięte w odniesieniu do pobierania indukowane subgraphs). Let oznacza zbiór wykresów -Vertex w . Powiedzmy, że zawiera prawie wszystkie wykresy, jeśli ułamek wszystkich wykresów -vertex przypadających na zbliża się do 1, jako .QQQQnQnQ_nnnnQQQQQQnnnQnQnQ_nn → ∞n→∞n\rightarrow\infty Pytanie: Czy to możliwe, że dziedziczna klasa grafów …
2
Dokładna formuła dla liczby drzew rozpinających prostokąta
Ten blog mówi o generowaniu „krętych małych labiryntów” za pomocą komputera i ich liczeniu. Wyliczenia można dokonać za pomocą algorytmu Wilsona, aby uzyskać UST , ale nie pamiętam wzoru na ich liczbę. http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike Zasadniczo Twierdzenie o Drzewie Matrycowym stwierdza, że ​​liczba drzew spinających na wykresie jest równa wyznacznikowi macierzy Laplaciana …
1
Kanoniczna reprezentacja binarnego drzewa decyzyjnego w czasie?
Zastanawiam się, czy może istnieć sposób na nadanie pewnego rodzaju „normalnej formy” binarnym drzewom decyzyjnym (BDT) w sposób możliwy do wdrożenia. Mówiąc dokładniej: BDT jest drzewem z wewnętrznymi węzłami oznaczonymi zmiennymi logicznymi i liśćmi oznaczonymi przez lub . BDT reprezentuje funkcję logiczną w oczywisty sposób. Dwa BDT są równoważne ( …
1
Problemy z komunikacją, o których nie wiadomo, że istnieje deterministyczne twierdzenie o sumie bezpośredniej
Jest to stary otwarty problem, czy bezpośrednim suma twierdzenie zachodzi dla deterministycznego złożoności komunikacyjnej, to znaczy, czy rozwiązywania niezależnych instancji problemu jest razy twardszy niż rozwiązywanie pojedynczą instancję. [FKNN95] wykazał następujące wyniki:ttttttt Wynik negatywny: istnieje funkcja częściowa (z powodu [O90]), której deterministyczna złożoność komunikacji wynosi , ale obliczenie jej w …
1
O derandomizacji wielomianowych testów tożsamości
W teście tożsamości wielomianowej szukamy algorytmu deterministycznego, aby wnioskować o równości dwóch wielomianów . Ważnym otwartym problemem jest derandomizacja znanych skutecznych algorytmów randomizowanych i wytwarzanie wydajnego algorytmu deterministycznego. Czy istnieje kompletny problem dla PIT, tak że derandomizacja testów tożsamości dla tej jednej klasy wielomianów rozwiązuje ten otwarty problem? Jeśli nie, …
1
Czy możemy skonstruować k-mądrą niezależną permutację na [n], używając tylko stałego czasu i przestrzeni?
Niech k>0k>0k>0 będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą nnn , chcemy skonstruować permutację σ∈Snσ∈Sn\sigma \in S_n tak aby: Konstrukcja wykorzystuje stały czas i przestrzeń (tj. Wstępne przetwarzanie zajmuje stały czas i przestrzeń). Możemy użyć randomizacji. Biorąc pod uwagę i∈[n]i∈[n]i\in[n] , σ(i)σ(i)\sigma(i) można obliczyć w stałym czasie i przestrzeni. …
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.