Teoretyczne informatyka

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

1
Przykłady algorytmów i dowodów, które wydają się poprawne, ale nie są
W moim wstępie do kursu programowania dowiadujemy się o metodzie inicjalizacji, konserwacji i terminacji, aby udowodnić, że algorytm działa zgodnie z oczekiwaniami. Musieliśmy jednak tylko udowodnić, że algorytm, o którym wiadomo, że jest poprawny, jest poprawny. Nigdy nie byliśmy proszeni o wykazanie, że algorytm jest nieprawidłowy. Czy są jakieś klasyczne …
2
Teoretyczne traktowanie różnic, łat i łączenia?
Czy istnieje kategoria łatek, która wygląda mniej więcej tak: Obiekty są ciągami znaków w pewnym alfabecie podstawowym Morfizmy to skrypty edycyjne („diffs” lub „łatki”) między ciągami Interesują mnie następujące pytania: Czy istnieje kategoryczne pojęcie minimalnego skryptu edycji? Może kategoria łatek jest wzbogacona w zestawy PO? Czy łączenie łat jest kategorycznym …
1
Prawdopodobieństwo działania losowej sieci sortującej
Biorąc pod uwagę nnn wejścia x0,…,xn−1x0,…,xn−1x_0, \ldots, x_{n-1} , budujemy losową sieć sortująca z mmm bram poprzez iteracyjne zbieranie dwóch zmiennych xi,xjxi,xjx_i, x_j z i&lt;ji&lt;ji < j i dodanie bramę komparatora że swapy nich, jeśli xi&gt;xjxi&gt;xjx_i > x_j . Pytanie 1 : W przypadku stałej nnn , jak duża musi …
1
Problem decydowania, czy monotoniczny CNF implikuje monotoniczny DNF
Rozważ następujący problem decyzyjny Wejście : monotoniczny CNF ΦΦ\Phi i monotonowy DNFΨΨ\Psi . Pytanie : Czy Φ→ΨΦ→Ψ\Phi \to \Psi jest tautologią? Zdecydowanie możesz rozwiązać ten problem w czasie O(2n⋅poly(l))O(2n⋅poly(l))O(2^n \cdot \mathrm{poly}(l)) , gdzie nnn jest liczbą zmiennych w Φ→ΨΦ→Ψ\Phi \to \Psi a lll jest długością wejściową. Z drugiej strony ten …
4
Reprezentacje base-k w domenie wielomianu - czy jest ona pozbawiona kontekstu?
W rozdziale 4 Drugiego kursu teorii automatu Jeffreya Shallita następujący problem wymieniono jako otwarty: p(n)p(n)p(n)∈Np(n) \in \mathbb{N}n∈Nn \in \mathbb{N} { p ( n ) ∣ n ⩾ 0 }){p(n)∣n⩾0}\{p(n) \mid n \geqslant 0\} jest pozbawione kontekstu, tylko wtedy, gdy stopieńwynosi.ppp ⩽ 1⩽1\leqslant 1 Jaki jest teraz jego status (na październik …
2
Dowód użycia asystenta w badaniach teorii złożoności?
Biorąc pod uwagę tematy poruszane na konferencji, takie jak STOC, czy naukowcy zajmujący się algorytmem lub złożonością aktywnie korzystają z COQ lub Isabelle? Jeśli tak, to jak wykorzystują go w swoich badaniach? Zakładam, że większość ludzi nie użyłaby takich narzędzi, ponieważ dowody byłyby zbyt niskie. Czy ktoś używa tych asystentów …
2
Czy w książce Hott większość redaktorów jest zbędna? A jeśli tak, to dlaczego?
W rozdziale 1 i załączniku A książki Hott przedstawiono kilka rodzin typów pierwotnych (typy wszechświatów, typy funkcji zależnych, typy par zależnych, typy koproduktów, typy puste, typy jednostek, typy liczb naturalnych i typy tożsamości), aby stworzyć podstawę dla teorii typów homotopii. Wydaje się jednak, że biorąc pod uwagę typy wszechświata i …
1
NP-Kompletne problemy, które dopuszczają wydajny algorytm pod obietnicą unikalnego rozwiązania
Niedawno czytałem bardzo fajny artykuł Valianta i Vazirani, który pokazuje, że jeśli , to nie może być skutecznego algorytmu do rozwiązania SAT, nawet pod obietnicą, że jest albo niezadowalający, albo ma unikalne rozwiązanie. W ten sposób pokazując, że SAT nie dopuszcza wydajnego algorytmu nawet pod obietnicą istnienia co najwyżej jednego …
1
Wymiar VC wielomianów nad tropikalnymi półksiężycami?
BPP\mathbf{BPP}P\mathbf{P}poly\mathrm{poly} (max,+)(max,+)(\max,+)(min,+)(min,+)(\min,+) Niech będzie na pół wieku. Zerowej wzorzec sekwencji z wielomianów jest podzbiorem , dla których istnieją , a taki sposób, aby dla wszystkich , f i ( x ) = Y IFF ı ∈ S . Oznacza to, że wykresy dokładnie tych wielomianów f i z i ∈ …
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.