Teoretyczne informatyka

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

5
Czy redukcje powinny nas bardziej lub mniej optymistycznie podchodzić do rozwiązania problemu?
Wydaje mi się, że większość teoretyków złożoności ogólnie uważa następującą zasadę filozoficzną: Jeśli nie możemy wymyślić skuteczny algorytm dla problemu i możemy zmniejszyć problemu A do problemu B , wtedy prawdopodobnie nie jest skuteczny algorytm dla problemu B , albo.ZAAAZAAAbBBbBB Dlatego, na przykład, gdy nowy problem zostanie udowodnione, NP-complete po …
1
obwodu
Czy wiadomo, czy problem z oceną obwodu występuje w ? Co powiesz na (uniform )? N C 1 A L O g T i m e N C 1NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Wiemy, że obwody o głębokości można oceniać za pomocą obwodów o głębokości gdzie jest stałą uniwersalną. Oznacza to, że obwody o …
7
Zastosowania teorii gier w informatyce?
Jako student informatyki zapoznałem się z teorią gier, ale nie widziałem zbyt wielu szczegółów na ten temat. Szukałem w Google i przeglądałem książki o teorii gier, które potwierdziły jej wykorzystanie w informatyce. Rozpocząłem formalne studium teorii gier z perspektywy ekonomisty. Teraz chcę poznać zastosowania teorii gier w informatyce. Jakie są …
2
Optymalny algorytm znajdowania obwodu rzadkiego wykresu?
Zastanawiam się, jak znaleźć obwód rzadkiego niekierowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy w , to znajdę obwód …
1
Kompilator Stalina brutalnie optymalizuje, ale jak?
Oświadczenie badawcze JM Siskinda stwierdza: Stalin jest optymalizującym kompilatorem programu Scheme, który wykonuje analizę statyczną całego programu i wykorzystuje wyniki tej analizy do generowania wyjątkowo wydajnego kodu. Stalin wykorzystuje duży zbiór technik analizy statycznej. Wykonuje nowatorską formę analizy przepływu wielowariantowego, która wykorzystuje iterowaną analizę przepływu monowariantowego w celu wykonania podziału …
14 compilers 
5
Jaki jest limit danych bezstratnej kompresji? (jeśli istnieje taki limit)
Ostatnio miałem do czynienia z algorytmami związanymi z kompresją i zastanawiałem się, który jest najlepszy współczynnik kompresji, jaki można osiągnąć dzięki kompresji danych bezstratnych. Jak dotąd jedynym źródłem, jakie mogłem znaleźć na ten temat, była Wikipedia: Bezstratna kompresja danych cyfrowych, takich jak wideo, filmy cyfrowe i dźwięk, zachowuje wszystkie informacje, …
7
Analiza matematyczna i złożoność obliczeniowa?
złożoność obliczeniowa obejmuje duże ilości kombinatoryki i teorii liczb, niektóre elementy stochastyczne i pojawiającą się ilość algebry. Jednak będąc analitykiem zastanawiam się, czy istnieją zastosowania analizy w tej dziedzinie, czy może pomysły inspirowane analizą. Wiem tylko, co nieco to odpowiada, to transformata Fouriera na grupach skończonych. Możesz mi pomóc?
2
Listy różnic w programowaniu funkcjonalnym
Pytanie Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki? oraz epicka odpowiedź jbapple, wspomniana przy użyciu list różnic w programowaniu funkcjonalnym (w przeciwieństwie do programowania logicznego), co mnie ostatnio interesowało. To doprowadziło mnie do znalezienia implementacji listy różnic dla Haskell. Mam dwa pytania (wybacz mi / popraw, jeśli …
3
Gwarancje twardości dla AES
Wiele kryptosystemów z kluczem publicznym ma pewnego rodzaju sprawdzalne zabezpieczenia. Na przykład kryptosystem Rabin jest tak samo trudny jak faktoring. Zastanawiam się, czy istnieje taki rodzaj możliwego do udowodnienia bezpieczeństwa dla kryptosystemów tajnych kluczy, takich jak AES. Jeśli nie, jakie są dowody na to, że złamanie takich kryptosystemów jest trudne? …
2
Rzutna płaszczyzna zamówienia 12
Cel : ustalenie przypuszczenia, że ​​nie ma rzutowej płaszczyzny rzędu 12. W 1989 r., Korzystając z wyszukiwania komputerowego na kredce, Lam udowodnił, że nie istnieje rzutowa płaszczyzna rzędu 10. Teraz, gdy Boski numer Kostki Rubika został ustalony po zaledwie kilku tygodniach masowych poszukiwań brutalnej siły (plus sprytnej matematyki symetrii), wydaje …
1
Chernoff wyznaczył sumy ważone
Rozważ , gdzie lambda_i> 0 i Y_i są rozłożone jako normalna norma. Jakie granice koncentracji można udowodnić na X, jako funkcję (stałych) współczynników lambda_i?X=∑iλiY2iX=∑iλiYi2X = \sum_i \lambda_i Y_i^2 Jeśli wszystkie lambda_i są równe, oznacza to ograniczenie Chernoffa. Jedyny inny wynik, jaki znam, to lemat z pracy Arory i Kannana („Uczenie …
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.