Teoretyczne informatyka

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

2
Niezależni gaussowie parami
Biorąc pod uwagę X1,…,XkX1,…,XkX_1,\ldots,X_k (iid gaussians ze średnią 000 i wariancją 111 ), czy możliwe jest (jak?) Próbkowanie (dla m=k2m=k2m=k^2 ) Y1,…,YmY1,…,YmY_1, \ldots, Y_m takie, że YiYiY_i są parami niezależni gaussowie ze średnią 000 i wariancją 111 .
3
Czy istnieje algorytm online do śledzenia komponentów na zmieniającym się niekierowanym wykresie?
Problem Mam nieukierunkowany wykres (z wieloma krawędziami), który z czasem się zmieni, węzły i krawędzie można wstawiać i usuwać. Przy każdej modyfikacji wykresu muszę aktualizować połączone elementy tego wykresu. Nieruchomości Dodatkowe właściwości polegają na tym, że żadne dwa składniki nigdy nie zostaną ponownie połączone. Oczywiście wykres może mieć dowolne cykle …
1
Znalezienie półcienia problemu satysfakcji z ograniczeń
Podczas testowania bezpieczeństwa systemu lub modelu wielokrotnie pojawiło się następujące pytanie . Motywacja: Wady bezpieczeństwa oprogramowania często nie wynikają z błędów spowodowanych prawidłowymi danymi wejściowymi, ale z błędów wynikających z nieprawidłowych danych wejściowych, które są wystarczająco zbliżone do prawidłowych danych wejściowych, aby przejść przez wiele prostych kontroli poprawności. Klasycznym przykładem …
12 lo.logic  csp  security 
2
Czy
Przez http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Jeśli jest językiem PSPACE uzupełniania, P = N P A .AAAPA=NPAPA=NPAP^{A}=NP^{A} Jeśli jest deterministyczną wyrocznią wielomianową, P B ≠ N P B (przy założeniu P ≠ N P ).BBBPB≠NPBPB≠NPBP^{B}\ne NP^{B}P≠NPP≠NPP\ne NP to klasa problemów decyzyjnych analogiczna dla # P i P ⊆ P P ⊆ P S P …
5
algorytm grupowania dla danych niewymiarowych
Mam zestaw danych zawierający tysiące punktów i sposób pomiaru odległości między dowolnymi dwoma punktami, ale punkty danych nie mają wymiarów. Chcę algorytmu, aby znaleźć centra klastrów w tym zestawie danych. Wyobrażam sobie, że ponieważ dane nie mają wymiarów, centrum klastrów może składać się z kilku punktów danych i tolerancji, a …
7
Tematy interdyscyplinarne między teorią sterowania a informatyką teoretyczną
Jestem na drugim roku studiów magisterskich, które nie odnoszą się zbytnio do TCS, choć tego chciałbym. Chodzi przede wszystkim o teorię sterowania, sygnały i systemy, a ja wziąłem zajęcia z zaawansowanych systemów (solidne, nieliniowe, optymalne, stochastyczne), zaawansowanego przetwarzania sygnałów i optymalizacji wypukłej. Próbuję znaleźć dobry obszar do rozwiązania w mojej …
2
Szybki rzadki produkt typu boolean z możliwym przetwarzaniem wstępnym
Jakie są najbardziej efektywne algorytmy mnożenia dwóch bardzo rzadkich macierzy boolowskich (powiedzmy, N = 200, a jest tylko około 100-200 niezerowych elementów)? W rzeczywistości mam tę zaletę, że kiedy mnożę A przez B, B są predefiniowane i mogę na nich dowolnie skomplikowane przetwarzanie wstępne. Wiem też, że wyniki produktów są …
4
Skierowane trudne NP problemy na DAG
Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Kilka problemów trudnych dla NP można rozwiązać na wykresach z ograniczoną szerokością drzewa. Jeśli na drzewach nadal występuje trudny NP, szerokość drzewa nie może nas uratować. Taka była motywacja jednego z moich wcześniejszych pytań, które dotyczyły trudnych NP problemów na drzewach. …
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.