Teoretyczne informatyka

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

2
Złożoność czasowa liczenia trójkątów na wykresach płaskich
Liczenie trójkątów na ogólnych wykresach można trywialnie wykonać w czasie i myślę, że znacznie szybsze wykonanie jest trudne (mile widziane referencje). Co z grafami płaskimi? Poniższa prosta procedura pokazuje, że można tego dokonać w czasie O ( n log n ) . Moje pytanie jest dwojakie:O(n3)O(n3)O(n^3)O(nlogn)O(nlog⁡n)O(n\log{n}) Jakie jest odniesienie do …
1
Jakie monotoniczne funkcje boolowskie są reprezentowane jako progi sum?
Przedstawię mój problem na przykładzie. Powiedzmy, że projektujesz egzamin, który składa się z pewnego zestawu niezależnych pytań (że kandydaci mogą mieć rację albo dobrze). Chcesz zdecydować o wyniku dla każdego pytania, z tą regułą, że kandydaci z całkowitą liczbą punktów powyżej pewnego progu przejdą, a pozostałe zawiodą.nnn W rzeczywistości jesteś …
3
Znalezienie świadka w minkowskiej sumie liczb całkowitych
Niech i będą podzbiorami . Interesuje nas znalezienie sumy Minkowskiego .ZAAABBB{0,…,n}{0,…,n}\{0,\ldots,n\}A+B={a+b | a∈A,b∈B}A+B={a+b | a∈A,b∈B}A+B=\{a+b~|~a\in A,b\in B\} χX:{0,…,2n}→{0,1}χX:{0,…,2n}→{0,1}\chi_X:\{0,\ldots,2n\}\to \{0,1\} jest charakterystyczną funkcją ifXXXχX(x)={1 if x∈X0 otherwiseχX(x)={1 if x∈X0 otherwise\chi_X(x) = \begin{cases} 1 \text{ if } x\in X\\ 0 \text{ otherwise}\end{cases} Niech będzie dyskretne splot i , a , wtedy i …
16 convolution  fft 
1
Obliczanie parzystości permutacji w sposób strumieniowy
Szukam algorytmu jednoprzebiegowego, który oblicza parzystość permutacji. Zakładam, że permutacja wejściowa jest podawana przez strumień . Wyjście powinno być parzystością permutacji. Pytanie mnie interesuje, ile pamięci powinien użyć algorytm deterministyczny. Czy istnieje jakiś losowy algorytm dotyczący problemu?π[1],π[2],⋯,π[n]π[1],π[2],⋯,π[n]\pi[1], \pi[2], \cdots, \pi[n] Wiem, że obliczanie liczby inwersji w jednym przebiegu wykorzystuje pamięć …
1
W jakim stopniu matematykę Rzeczywistości można zastosować do Rzeczywistości Obliczalnych?
Czy istnieje ogólne twierdzenie, które przy odpowiedniej dezynfekcji stanowiłoby, że najbardziej znane wyniki dotyczące użycia liczb rzeczywistych mogą być rzeczywiście wykorzystane przy rozważaniu tylko liczb rzeczywistych? Czy też istnieje właściwa charakterystyka wyników, które pozostają aktualne, biorąc pod uwagę tylko rzeczywiste obliczalne? Bocznym pytaniem jest to, czy wyniki dotyczące liczb obliczalnych …
3
Przykłady
Potrzebuję listę pełnych językach. Istnieją dwa takie problemy wymienione w zoo złożoności , a mianowicie:Σp2Σ2p\Sigma_2^p Minimalny równoważny DNF. Biorąc pod uwagę formułę DNF F i liczbę całkowitą k, czy istnieje formuła DNF równoważna F z k lub mniejszą liczbą literałów? Najkrótszy implant. Biorąc pod uwagę wzór F i liczbę całkowitą …
1
Historyczna relacja między wpisaną metodą Lambda Calculus a Lisp?
Niedawno rozmawiałem z przyjacielem (który jest zwolennikiem silnie pisanych języków). Skomentował: Wynalazcy Lambda Calculus zawsze zamierzali go pisać na maszynie. Teraz widzimy, że Kościół był związany z tym po prostu wpisane rachunek lambda . Rzeczywiście wydaje się, że wyjaśnił on prosty typ rachunku Lambda, aby ograniczyć nieporozumienia dotyczące rachunku Lambda. …
1
Czy ciągła dwuznaczność może zmniejszyć złożoność stanu zwykłych języków?
Mówimy, że NFA jest stale niejednoznaczny, jeśli istnieje tak że każde słowo jest akceptowane przez lub (dokładnie) ścieżek.MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Jeśli automat jest stale niejednoznaczny dla , wówczas nazywa się Jednoznacznym FA (UFA).MMMk=1k=1k=1MMM Niech będzie zwykłym językiem.LLL Czy jakiś stale dwuznaczny automat dla być mniejszy niż najmniejszy UFA, który akceptuje …
2
O statusie zdolności uczenia się w
Próbuję zrozumieć złożoność funkcji wyrażanych przez bramki progowe, co doprowadziło mnie do . W szczególności interesuje mnie to, co obecnie wiadomo na temat uczenia się w T C 0 , ponieważ nie jestem ekspertem w tej dziedzinie.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 Do tej pory odkryłem: Wszystkie można wyciągnąć w quasipolynomial czasie w jednorodnym rozkładzie …
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.