Teoretyczne informatyka

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

2
Jak tasować kolorowe kulki?
Mam 400 piłek, w których 100 to czerwone, 40 to żółte, 50 to zielone, 60 to niebieskie, 70 to fioletowe, 80 to czarne. (kule tego samego koloru są identyczne) Potrzebuję wydajnego algorytmu tasowania, aby po tasowaniu kulki znalazły się na liście i 3 kolejne kule nie są tego samego koloru. …
3
Twardość obliczeniowa „prawdziwych” programów komputerowych
Często słyszałem, jak mówiono, że nie można napisać programu do wychwytywania błędów w przeglądarce internetowej, edytorze tekstu lub systemie operacyjnym z powodu twierdzenia Rice'a: każda właściwość semantyczna dla języka pełnego Turinga jest nierozstrzygalna. Nie jestem jednak pewien, w jakim stopniu dotyczy to rzeczywistego programu, takiego jak systemy operacyjne. Czy tego …
3
Udoskonalenia aproksymacji par do analizy sieci
Rozważając interakcje w sieci, zwykle bardzo trudno jest analitycznie obliczyć dynamikę i stosuje się przybliżenia. Przybliżenia pola średniego zwykle całkowicie ignorują strukturę sieci, a zatem rzadko są dobrym przybliżeniem. Popularnym aproksymacją jest aproksymacja pary, która uwzględnia korelacje nieodłączne między sąsiednimi węzłami (intuicyjnie możemy myśleć o tym jako o typie aproksymacji …
1
Gęstość języków P-zupełnych
Załóżmy, że jest językiem boolowskim o skończonych łańcuchach ponad . Niech będzie liczbą łańcuchów w o długości . Dla funkcji od dodatnich liczb całkowitych do dodatnich liczb rzeczywistych, ma górną gęstość jeśli dla wszystkich wystarczająco dużych .L.L.LL n L n d ( n ) L d ( n ) L …
2
Czy kryptologowie odradzają rejestrom przesuwnym liniowe sprzężenie zwrotne?
Katz i Lindell wspominają w swojej książce, że LFSR są okropne jako podstawa dla generatorów pseudolosowych i zalecają, aby nie były już używane (cóż, zalecają również, aby ludzie używali szyfrów blokowych zamiast szyfrów strumieniowych). Widzę jednak na przykład, że jeden z szyfrów w portfolio estream ( ziarno , ukierunkowane na …
1
Znalezienie płaszczyzny cięcia, która równomiernie dzieli wielościan
Powiedzmy, że mamy wielościan w standardowej formie: A x = bx ≥ 0ZAx=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Czy są znane metody znalezienia hiperpłaszczyzny która dzieli wielościan w taki sposób, że liczba wierzchołków po każdej stronie hiperpłaszczyzny jest w przybliżeniu taka sama? (tj. algorytm minimalizujący …
1
Zredukowanie podstawowych produktów faktoringowych do faktoringowych liczb całkowitych (w przeciętnym przypadku)
Moje pytanie dotyczy równoważności bezpieczeństwa różnych kandydujących funkcji jednokierunkowych, które można zbudować w oparciu o twardość faktoringu. Zakładając problem FAKTORING: [Biorąc pod uwagę dla losowych liczb pierwszych , znajdź , ]P , Q &lt; 2 n P QN.= PQN=PQN = PQP., Q &lt; 2nP,Q&lt;2nP, Q < 2^nP.PPQQQ funkcja nie może …
1
Odwołanie do niezdefiniowanego modułu ciągłości funkcjonalnej w PCF?
Czy ktoś może wskazać mi odniesienie do niezdefiniowalności modułu ciągłości funkcjonalnej w PCF? \ newcommand {\ bool} {\ mathsf {bool}}\newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Andrej Bauer napisał bardzo fajny post na blogu , w którym szczegółowo omawia niektóre problemy, ale streszczę tylko trochę jego postu, aby nadać kontekst temu pytaniu. Baire'a przestrzeń jest …
3
Dopasowanie wzorca permutacji w ciągach
Luźno mówiąc, dopasowanie wzorców permutacji dotyczy następujących problemów: Biorąc pod uwagę permutacje w S n i w , przy , czy zawiera podsekwencję o długości której elementy są uporządkowane według ?ππ\piSnSnS_nS m m ≤ n π τ m σσσ\sigmaSmSmS_mm≤nm≤nm\leq nππ\pi ττ\taummmσσ\sigma Na przykład, jeśli i , to podsekwencja pasuje do …
1
Odcisk palca dla zestawów dynamicznych
Czy istnieje w-bitowa struktura danych słowo-RAM z czasem O (1) na operację dla następującego problemu ?: Utrzymanie zestawu w-bitowych nieujemnych liczb całkowitych, które obsługują operacje add (x): dodaj x do zestawu remove (x): usuń x z zestawu odcisk palca (): zwraca odcisk palca zestawu. Ten w-bitowy odcisk palca ma właściwość …
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.