Teoretyczne informatyka

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

1
Zamknięcie w ramach sumy Minkowskiego.
Sumę Minkowskiego dwóch zbiorów wektorów podajeA , B ∈ RreA,B∈RdA, B \in R^d A ⊕ B = { a + b ∣ a ∈ A , b ∈ B }A⊕B={a+b∣a∈A,b∈B} A \oplus B = \{ a + b \mid a \in A, b \in B \} Właśnie usłyszałem interesujący problem …
1
Czy istnieje algorytm wielomianowy do rozwiązywania izomorfizmu grafów dla grafów Delaunaya (skończonych) heksagonalnych teselacji?
Biorąc pod uwagę skończoną płaszczyznę, mam sześciokątną teselację tej płaszczyzny z regularnym sześciokątem o stałej wielkości. Następnie obliczam wykres G Delaunaya dla teselacji. Biorąc pod uwagę taki wykres G, usuwam określone zestawy węzłów na tym wykresie, aby uzyskać wiele podgraphów G. Muszę ustalić, czy podgrupy te są izomorficzne (względem siebie). …
1
Które klasyfikatory uczenia maszynowego są najbardziej równoległe?
Które klasyfikatory uczenia maszynowego są najbardziej równoległe? Jeśli miałbyś trudny problem z klasyfikacją, ograniczony czas, ale przyzwoitą sieć LAN komputerów do pracy, z jakimi klasyfikatorami byś spróbował? Z drugiej strony wygląda mi to na kilka standardowych klasyfikatorów, które znam w następujący sposób, ale mogę się całkowicie mylić: Losowe lasy - …
1
sieci w odniesieniu do normy cięcia
Przeciętna norma ||A||C||ZA||do||A||_C rzeczywistej macierzy A=(ai,j)∈Rn×nZA=(zaja,jot)∈Rn×nA = (a_{i,j}) \in \mathcal{R}^{n\times n} jest maksimum we wszystkich I⊆ [ n ] ,J⊆ [ n ]ja⊆[n],jot⊆[n]I \subseteq [n], J \subseteq [n] ilości ∣∣∑i ∈I, j ∈ Jzaja , j∣∣|∑ja∈ja,jot∈jotzaja,jot|\left|\sum_{i \in I, j \in J}a_{i,j}\right|. Zdefiniuj odległość między dwiema macierzami ZAZAA i bbB aby …
1
Czy można zastosować opisową złożoną wersję twierdzenia Rice'a do oddzielenia AC0 i PSPACE?
W tym pytaniu wspomniano, że istnieją opisowe wersje złożoności twierdzenia Rice'a. Znalazłem dowód na następujące twierdzenie: Biorąc pod uwagę klasę złożoności C , nietrywialnych właściwości języków w C nie można obliczyć w C Wcześniej opublikowałem znaleziony dowód, ale ponieważ był on tak długi i ponieważ w komentarzach wskazano, że ten …
1
W teorii domen, do czego można wykorzystać dodatkową strukturę występującą w przestrzeniach metrycznych?
Rozdział Smytta w podręczniku logiki w informatyce i inne źródła opisują, w jaki sposób przestrzeni metrycznych można użyć jako domen. Rozumiem, że pełne przestrzenie metryczne dają unikalne stałe punkty, ale nie rozumiem, dlaczego przestrzenie metryczne są ważne. Byłbym wdzięczny za wszelkie przemyślenia na następujące pytania. Jakie są dobre przykłady wykorzystania …
3
Dlaczego nie używamy większych klas do badania determinizmu kontra niedeterminizmu?
W poprzednim pytaniu dotyczącym hierarchii czasu dowiedziałem się, że równości między dwiema klasami mogą być propagowane do bardziej złożonych klas, a nierówności mogą być propagowane do mniej złożonych klas, z argumentami wykorzystującymi wypełnianie. Dlatego przychodzi mi na myśl pytanie. Dlaczego badamy pytanie dotyczące różnych rodzajów obliczeń (lub zasobów) w najmniejszej …
2
Taksonomia znaczących automatów wyrażeń regularnych
Próbuję opracować systematykę algorytmów do przekształcania wyrażeń regularnych w automaty, aby przeprowadzić pewne testy empiryczne ich właściwości złożoności w określonych domenach. Znam kilka „większych” nazw, np. Thompson „Algorytm wyszukiwania wyrażeń regularnych”, Thompson, 1968 Glushkov „Nowy algorytm kwadratowy do przekształcenia wyrażenia regularnego w automat”, Ponty i in. al. 1996 Antimirov „Częściowe …
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.