Teoretyczne informatyka

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

1
Teoria typów homotopii i twierdzenia o niekompletności Gödla
Twierdzenia Kurta Gödela o niekompletności ustanawiają „nieodłączne ograniczenia wszystkich oprócz najbardziej trywialnych systemów aksomatycznych zdolnych do wykonywania arytmetyki”. Teoria typów homotopii stanowi alternatywną podstawę dla matematyki, podstawę jednoznaczną opartą na wyższych typach indukcyjnych i aksjomat jedności . Książka HoTT wyjaśnia, że typy są wyższe groupoids funkcje są funktory, rodziny typu …
1
Odwracalne plandeki Turinga?
To pytanie o to, czy istnieją jakieś znane tarpits odwracalny Turinga, gdzie „odwracalne” oznacza w sensie Axelsen i Glück , a „Tarpit” jest znacznie bardziej nieformalny pojęcie (i może nie być bardzo dobrym wyborem słowa), ale postaram się wyjaśnić, co mam na myśli. Co rozumiem przez „tarpit” Niektóre modele obliczeń …
1
Minimalizacja programu
Minimalizacja obwodu to problem polegający na zminimalizowaniu rozmiaru danego obwodu. Czy jest coś podobnego do programów ogólnych? W szczególności moje pytanie brzmi - Czy istnieją algorytmy minimalizujące liczbę instrukcji dla danego programu? Wiem, że to nierozstrzygalny problem, ale nie szukam rozwiązania, które zwróci coś optymalnego. Podczas gdy można zastosować wcześniej …
1
Kodowanie zestawów permutacji za pomocą zestawu generującego i zestawu elementów wykluczonych
Algorytmy czasu wielomianowego znane są ze znajdowania generujących zestawów grup permutacji, co jest interesujące, ponieważ możemy następnie przedstawić te grupy zwięźle, nie rezygnując z algorytmów czasu wielomianowego do odpowiedzi na wiele interesujących pytań związanych z tymi grupami. Czasami jednak możemy być zainteresowani zestawem permutacji, który nie tworzy grupy, więc zestaw …
1
Jaka jest zaleta projektowania deterministycznych algorytmów rozproszonych?
Algorytmy rozproszone odporne na awarie mogą być deterministyczne lub probabilistyczne. Weźmy na przykład problem konsensusu. Paxos jest deterministyczny w tym sensie, że biorąc pod uwagę przyjęte założenie, zawsze działa. Natomiast randomizowany konsensus działa z określonym prawdopodobieństwem. Jaka jest zaleta projektowania i stosowania algorytmu deterministycznego? Założenia, na których opierają się algorytmy …
2
Dlaczego linearyzowalność jest właściwością bezpieczeństwa i dlaczego zestawy właściwości bezpieczeństwa są zamknięte?
W rozdziale 13 „Obiekty atomowe” książki „Algorytmy rozproszone” Nancy Lynch udowodniono, że linearyzowalność (znana również jako atomowość) jest właściwością bezpieczeństwa. To znaczy, że jego odpowiednia właściwość śledzenia jest niepusta, zamknięta z prefiksem i zamknięta z ograniczeniem , jak zdefiniowano w sekcji 8.5.3. Nieformalnie właściwość bezpieczeństwa jest często interpretowana jako powiedzenie, …
1
Zerowa przypadkowa złożoność komunikacji a deterministyczna złożoność komunikacji
Wiadomo, że dla błędu definicja najgorszego przypadku złożoności losowej komunikacji i definicja średniego przypadku są równoważne. Ale gdy błąd wynosi , najgorszy przypadek złożoności komunikacji losowej jest taki sam, jak deterministyczna złożoność komunikacji.Θ ( 1 )Θ(1)\Theta(1)000 Czy jakaś funkcja ma super-stałą deterministyczną złożoność komunikacji, ale stałą losową złożoność komunikacji przy …
1
Złożoność splotu w pierścieniu max / plus
Możemy wykonać splot w O(nlogn)O(nlog⁡n)O(n\log n) dla wielomianów dodatnich / wielokrotnych za pomocą FFT. Jednak podejście to nie wydaje się zbyt ogólne w odniesieniu do pierścieni w ogóle. Czy nastąpił postęp w stosunku do naiwnego splotu O(n2)O(n2)O(n^2) dla pierścienia max / plus? soft-max(x,y)=log(ex+ey)=max(x,y)+log(1+emin(x,y)−max(x,y))soft-max(x,y)=log⁡(ex+ey)=max(x,y)+log⁡(1+emin(x,y)−max(x,y))\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y) + \log(1+e^{\min(x,y)-\max(x,y)})
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.