Informatyka

Na przykład wiem, że nieregularny język zanbnzanbna^nb^n jest w . Chciałbym poznać więcej takich przykładów.A

Mam prosty problem z utworzeniem DFA, który akceptuje wszystkie dane wejściowe zaczynające się od podwójnych liter (aa, bb) lub kończące się na podwójnych literach (aa, bb), biorąc pod uwagę, że jest zestawem alfabetu dany język.Σ={a,b}Σ={a,b}\Sigma =\{a, b\} Próbowałem rozwiązać to w sposób...

W komentarzu do Nauka F #: Jakie książki w innych językach programowania można przetłumaczyć na F #, aby nauczyć się funkcjonalnych koncepcji? Makarius stwierdził: Zauważ, że podejście „CPS” wyrządziło wielką szkodę wydajności w SML / NJ. Jego model oceny fizycznej narusza zbyt wiele założeń...

Biorąc pod uwagę dwa wektory liczb całkowitych o możliwie nierównych długościach, jak mogę określić maksymalny możliwy wynik z akumulacji wybierając maksimum między odpowiadającymi parami liczb między dwoma wektorami z dodatkowymi zerami wstawionymi do krótszego wektora, aby zrekompensować różnicę...

Oto pytanie z książki Dragon (przepraszam za błędy w tłumaczeniu, nie mam pod ręką wersji angielskiej): Jaki język jest generowany przez tę gramatykę? S→aSbS∣bSaS∣ϵS→aSbS∣bSaS∣ϵS \rightarrow a S b S \mid b S a S \mid \epsilon Nie wiem, co mam tutaj robić. Definicja w książce o językach mówi...

Biorąc pod uwagę zadań każde zadanie wymaga czasu czasu.J 1 , J 2 , . . . , J n T i > 0 , T i ∈ NnnnJ1,J2,...,JnJ1,J2,...,JnJ_1,J_2,...,J_nTi>0,Ti∈NTi>0,Ti∈NT_i > 0, T_i \in N Każde zadanie musi być wstępnie przetworzone i przetworzone przez pojedynczą maszynę M, która może obsłużyć tylko...

Niech Czy istnieje maszyna Turinga R, która decyduje (nie mam na myśli rozpoznać) język L ∅ ?L∅={⟨M⟩ ∣ M. jest maszyną Turinga i  L ( M) = ∅ } .L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and...

Lemat pompujący dla zwykłych języków może być użyty do udowodnienia, że ​​niektóre języki nie są regularne, a lemat pompujący dla języków bezkontekstowych (wraz z lematem Ogdena) może być użyty do udowodnienia, że ​​niektóre języki nie są kontekstowe. Czy istnieje determinujący lemat dla...

Jak algorytmicznie wykryłbyś dla każdego zdjęcia, czy słońce świeciło podczas robienia zdjęcia? Przykłady Próbka z tej kamery na szczycie góry: Wyraźnie świeci słońce. W tej innej próbce jest to o wiele mniej oczywiste: Prawdopodobnie można dość łatwo wykryć, czy jest mglisty, próbując...

Zwykłe stwierdzenie o uczciwym problemie cięcia ciasta zakłada, że ​​wszyscy gracze otrzymują swój udział w tym samym czasie. Jednak w wielu przypadkach gracze przybywają stopniowo. Na przykład, możemy podzielić ciasto na n graczy, ale wtedy pojawia się nowy gracz i chce się...

W pierwszym drzewie głębokości znajdują się krawędzie, które definiują drzewo (tj. Krawędzie, które zostały użyte podczas przejścia). Pozostały pewne krawędzie łączące niektóre inne węzły. Jaka jest różnica między krawędzią poprzeczną a przednią? Z wikipedii: Na podstawie tego drzewa łączącego...

Biorąc pod uwagę fakt, że wyliczenie ścieżki - jest problemem # P-zupełnym, czy mogłyby istnieć wydajne metody obliczające (lub przynajmniej przybliżające) średnią długość ścieżki - bez ich wyliczania? Co jeśli ścieżki mogą ponownie odwiedzać wierzchołki?t s tssstttsssttt Pomocne mogą być również...

To może być głupie pytanie. Wydaje się jasne, że FSA, ponieważ jest skończona, może zliczyć tylko liczbę symboli w ciągu wejściowym do liczby ograniczonej liczbą stanów. Ale teraz załóżmy, że wyposażamy FSA w funkcje wyjściowe (np. Drukowanie). Byłoby wówczas bardzo łatwo zbudować maszynę zdolną do...

Istnieją wydajne struktury danych do reprezentowania ustawionych partycji. Te struktury danych charakteryzują się dużą złożonością czasową dla operacji takich jak Union i Find, ale nie są szczególnie efektywne pod względem przestrzeni. Jaki jest oszczędny przestrzennie sposób reprezentowania...

Jak rozumiem, problem przypisania występuje w P, ponieważ węgierski algorytm może go rozwiązać w czasie wielomianowym - O (n 3 ). Rozumiem również, że problem z przypisaniem jest całkowitym problemem programowania liniowego , ale strona Wikipedii stwierdza, że ​​jest to NP-Hard. Dla mnie oznacza...

Ostatnio natknąłem się na ten problem , odmianę wież hanoi . Opis problemu: Rozważ następującą odmianę dobrze znanego problemu Wieże Hanoi: Dostajemy wież i m dysków o rozmiarach 1 , 2 , 3 , … , m ułożonych na niektórych wieżach. Twoim celem jest przeniesienie wszystkich dysków do k- tej...

Czy istnieje automat komórkowy (w 2D), który symuluje siłę między cząsteczkami?1/r1/r1/r Mówiąc dokładniej, chciałbym wiedzieć, czy przy ściśle lokalnych regułach aktualizacji możliwe jest przyciąganie dwóch obiektów (zdefiniowanych w modelu) siłą , gdzie jest odległością dzielącą obiekty. W...

Czy następujący problem NP-jest kompletny? (Zakładam, że tak). Wprowadź: niekierowany wykres, na którym zbiór zboczy może zostać rozłożony na dwa proste cykle rozłączne od krawędzi ( nie są one częścią danych wejściowych).k∈N,G=(V,E)k∈N,G=(V,E)k \in \mathbb{N},G=(V,E) Pytanie: Czy istnieje...

Buduję kategoryzator tekstowy dla krótkich zdań. Oprócz poinformowania użytkownika, że ​​„kategoria wpisanego tekstu to C”, chcę móc wyjaśnić, dlaczego podjąłem tę decyzję, w krótki i zrozumiały sposób. Na przykład nie chcę powiedzieć użytkownikowi: „Umieściłem zdanie w złożonej trójwarstwowej...

Czytam o teorii typów zależnych w książce online The Homotopy Type Theory . W sekcji 1.3 rozdziału Teoria typów wprowadza pojęcie hierarchii wszechświatów : , gdzieU0:U1:U2:⋯U0:U1:U2:⋯\mathcal{U}_0 : \mathcal{U}_1 : \mathcal{U}_2 : \cdots każdy wszechświat jest elementem następnego wszechświata...