Informatyka

1

Uzyskiwanie równoległych elementów w rozwiązywaniu zależności

Zaimplementowałem sortowanie topologiczne na podstawie artykułu z Wikipedii, którego używam do rozwiązywania zależności, ale zwraca ono listę liniową. Jakiego algorytmu mogę użyć do znalezienia niezależnych ścieżek?

13 algorithms graphs parallel-computing scheduling

2

Czy funkcje wyższego rzędu zapewniają większą moc programowaniu funkcjonalnemu?

Zadałem podobne pytanie na cstheory.SE . Zgodnie z tą odpowiedzią na Stackoverflow istnieje algorytm, który w nieliniowym czystym funkcjonalnym języku programowania ma złożoność , podczas gdy tym samym algorytmem w programowaniu imperatywnym jest Ω ( n ) . Dodanie lenistwa do języka FP spowodowałoby, że algorytm Ω ( n ) …

13 complexity-theory lambda-calculus functional-programming turing-completeness

1

Ograniczona wersja problemu Clique?

Rozważ następującą wersję problemu Kliki, w której dane wejściowe mają rozmiar a my poprosimy o znalezienie kliki o rozmiarze . Ograniczeniem jest to, że procedura decyzyjna nie może zmienić wykresu wejściowego na żadną inną reprezentację i nie może użyć żadnej innej reprezentacji do obliczenia swojej odpowiedzi, oprócz dodatkowych bitów poza …

13 complexity-theory time-complexity

2

Zamknięcie przed właściwym ilorazem za pomocą ustalonego języka

Naprawdę chciałbym pomóc w następujących kwestiach: W przypadku każdego stałego muszę zdecydować, czy nastąpi zamknięcie w ramach następujących operatorów:L.2)L2L_2 ZAr( L ) = { x ∣ ∃ y∈ L.2): x y∈ L }Ar(L)={x∣∃y∈L2:xy∈L}A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\} .ZAl( L ) = { x ∣ ∃ …

13 formal-languages regular-languages closure-properties

1

Bezpieczne podsumowanie przelewu

Załóżmy, że podano mi liczb całkowitych o stałej szerokości (tzn. Mieszczą się one w rejestrze szerokości ), tak że ich suma również mieści się w rejestrze szerokości .w a 1 , a 2 , … a n a 1 + a 2 + ⋯ + a n = S wnnnwwwa1,a2,…ana1,a2,…ana_1, …

13 algorithms arrays integers numerical-analysis

2

Jak udowodnić, że zwykłe języki są zamknięte pod lewym ilorazem?

to zwykły język nad alfabetem Σ = { a , b } . Lewym ilorazem L dotyczącym w ∈ Σ ∗ jest język w - 1 L : = { v ∣ w v ∈ L }L.LLΣ = { a , b }Σ={a,b}\Sigma = \{a,b\}L.LLw ∈ Σ∗w∈Σ∗w \in \Sigma^*w- 1L …

13 formal-languages regular-languages closure-properties

1

Wybór kranów do rejestru przesuwnego sprzężenia zwrotnego liniowego

Jestem zdezorientowany, jak wybierane są krany dla rejestrów przesunięcia liniowego sprzężenia zwrotnego. Mam schemat, który pokazuje LFSR z wielomianem połączenia . Pięć etapów jest oznaczonych: R 4 , R 3 , R 2 , R 1 i R 0, a kurki wychodzą z R 0 i R 3 .do( X) …

13 cryptography pseudo-random-generators shift-register

2

Zdecydowane ograniczenia problemu z korespondencją pocztową

Post Korespondencja Problem (PCP) jest nierozstrzygalny. Ograniczoną wersją PCP jest -Complete i oznaczone wersja PCP (słowa jednego z obu listach muszą różnić się w pierwszej literze) jest P S P A C E [1].N P.NP\mathrm{NP}P S P A C EPSPACE\mathrm{PSPACE} Czy te ograniczone wersje są wykorzystywane do udowodnienia, że niektóre …

13 complexity-theory computability reference-request

2

Zmniejszenie problemu z 3 partycjami do problemu zrównoważonej partycji

Problem 3 partycji zapytuje, czy zestaw liczb może być podzielona na n zestawy trzech liczb całkowitych takim, że każdy zestaw razem daje z danym całkowitą B . Problem zrównoważonej partycji pyta, czy 2 n liczb całkowitych można podzielić na dwa równe zestawy liczności, tak aby oba zestawy miały tę samą …

13 complexity-theory reductions np-complete

3

Dlaczego używanie leksykera / parsera na danych binarnych jest tak nieprawidłowe?

Często pracuję z lexer / parserami , w przeciwieństwie do kombinatora parserów i widzę osoby, które nigdy nie brały udziału w analizie składniowej, pytają o przetwarzanie danych binarnych. Zazwyczaj dane są nie tylko binarne, ale także kontekstowe. Zasadniczo prowadzi to do posiadania tylko jednego rodzaju tokena, tokena bajtu. Czy ktoś …

13 programming-languages compilers parsers

1

Złam protokół uwierzytelniania na podstawie wstępnie współdzielonego klucza symetrycznego

Rozważ następujący protokół, mający na celu uwierzytelnienie (Alice) na (Bob) i odwrotnie.B.ZAAAbBB A → B :B → A :A → B :„I'm Alice” , RZAmi( RZA, K)mi( ⟨ RZA+ 1 , PZA⟩ , K)A→B:“I'm Alice”,RAB→A:E(RA,K)A→B:E(⟨RA+1,PA⟩,K) \begin{align*} A \to B: &\quad \text{“I'm Alice”}, R_A \\ B \to A: &\quad E(R_A, K) …

13 cryptography protocols authentication

1

Czy wszystkie wywołania systemowe są blokowane?

Czytałem artykuł opisujący przełączanie między przestrzenią użytkownika a przestrzenią jądra, która ma miejsce po wywołaniu systemowym. Artykuł mówi Aplikacja oczekuje na zakończenie wywołania systemowego przed wznowieniem wykonywania w trybie użytkownika. Do tej pory zakładałem, że niektóre wywołania systemowe są blocking, podczas gdy inne są non-blocking. Z powyższym komentarzem jestem teraz …

13 operating-systems os-kernel

1

Sprawdzanie bezpieczeństwa generatora liczb pseudolosowych Nisan-Wigderson

Niech częściowe -design i być funkcją logiczną. Generator Nisan- jest zdefiniowany w następujący sposób:S={Si}1≤i≤nS={Si}1≤i≤n\cal{S}=\{S_i\}_{1\leq i\leq n}(m,k)(m,k)(m,k)f:{0,1}m→{0,1}f:{0,1}m→{0,1}f: \{0,1\}^m \to \{0,1\}Gf:{0,1}l→{0,1}nGf:{0,1}l→{0,1}nG_f: \{0,1\}^l \to \{0,1\}^n Gf(x)=(f(x|S1),…,f(x|Sn))Gf(x)=(f(x|S1),…,f(x|Sn))G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) ) Aby obliczyć ty bit , bierzemy bity z indeksami w a następnie stosujemy do nich .iiiGfGfG_fxxxSiSiS_ifff Załóżmy, że jest twarde dla …

13 cryptography pseudo-random-generators

1

Analiza zmodyfikowanej wersji gry karcianej „War”

Prostą grą, w którą zwykle bawią się dzieci, w grę wojenną grają dwie osoby korzystające ze standardowej talii 52 kart do gry. Początkowo talia jest tasowana i wszystkie karty rozdawane są dwóm graczom, dzięki czemu każda z nich ma 26 losowych kart w losowej kolejności. Zakładamy, że gracze mogą badać …

13 algorithms optimization

2

Identyfikowanie zdarzeń związanych z datami w akapicie

Czy istnieje algorytmiczne podejście do identyfikacji, że daty podane w akapicie są powiązane z określonymi zdarzeniami (frazami) w akapicie? Przykład, rozważ następujący akapit: W czerwcu 1970 roku wielki przywódca złożył przysięgę. Ale dopiero po maju 1972 r., Po śmierci ministra stanu, przejął stery kraju. Chociaż cieszył się popularnym poparciem do …

13 algorithms data-mining natural-language-processing