Biorąc pod uwagę tylko alfabet , ciągi, które można podać jako dane wejściowe do maszyn Turinga, pochodzą ze zbioru Σ ∗ . Ale czy ma sens, aby dane wejściowe były nieskończonym ciągiem binarnym? Na przykład, jeśli maszyna Turinga akceptuje wszystkie ciągi zaczynające się od 0, to czy ciąg binarny...
To pytanie zostało zainspirowane komentarzem na StackOverflow . Oprócz znajomości problemów NP-zupełnych z książki Garey Johnson i wielu innych; czy istnieje ogólna zasada, aby wiedzieć, czy problem wygląda jak NP-zupełny? Nie szukam czegoś rygorystycznego, ale czegoś, co działa w większości...
Nieformalne oświadczenie o problemie: Biorąc pod uwagę ciąg znaków, np. ACCABBABACCABBABACCABBAB , chcemy pokolorować niektóre litery na czerwono, a niektóre na niebiesko (a niektóre wcale), tak że czytanie tylko czerwonych liter od lewej do prawej daje taki sam wynik jak czytanie tylko niebieskie...
Czy następujący kontekst językowy jest bezpłatny? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Jak wskazał sdcvvc, słowo w tym języku można również opisać jako...
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Stworzyłem prosty leksymetr i analizator wyrażeń regularnych, aby pobrać wyrażenie regularne i wygenerować jego drzewo...
Zakładając, że żądania pamięci podręcznej L1 i L2 powodują błąd, czy procesor się zatrzymuje do momentu uzyskania dostępu do pamięci głównej? Słyszałem o pomyśle przejścia na inny wątek, jeśli tak, to co jest używane do obudzenia zablokowanej
Uwaga: chociaż umiem programować, jestem całkiem początkującym w teorii CS. Zgodnie z tą odpowiedzią Kompletność Turinga jest abstrakcyjną koncepcją obliczalności. Jeśli język jest kompletny Turinga, jest on w stanie wykonać dowolne obliczenia, które może wykonać każdy inny kompletny język...
Istnieje wiele technik, aby udowodnić, że język nie jest pozbawiony kontekstu, ale jak udowodnić, że język jest pozbawiony kontekstu? Jakie są techniki, aby to udowodnić? Oczywiście jednym ze sposobów jest wykazanie gramatyki bezkontekstowej dla tego języka. Czy istnieją jakieś systematyczne...
Większość z nas zna zgodność między logiką kombinacyjną a rachunkiem lambda . Ale nigdy nie widziałem (może nie spojrzałem wystarczająco głęboko) odpowiednika „typowanych kombinatorów”, odpowiadającego po prostu typowanemu rachunku lambda. Czy coś takiego istnieje? Gdzie można znaleźć informacje na...
Czy zadaniem oprogramowania (systemu operacyjnego) jest wykrywanie przepełnienia stosu, czy też przepełnienie stosu jest wykrywane sprzętowo, powodując wyjątek w
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Wiadomo, że każdy problem optymalizacji / wyszukiwania ma równoważny problem decyzyjny. Na przykład...
Uczę się języka programowania Haskell i staram się owinąć głowę, jaka jest różnica między a typea a kind. Jak rozumiem, a kind is a type of type. Na przykład a ford is a type of cari a car is a kind of vehicle. Czy to dobry sposób, aby o tym pomyśleć? Ponieważ sposób, w jaki mój mózg jest...
Kiedy są jakieś (względnie) podstawowe przypadki (myślę, że student pierwszego roku CS na studiach), kiedy zamiast pętli można by użyć rekurencji?
Wiem, że algorytm Euclida jest najlepszym algorytmem do uzyskania GCD (wielkiego wspólnego dzielnika) listy dodatnich liczb całkowitych. Ale w praktyce możesz kodować ten algorytm na różne sposoby. (W moim przypadku zdecydowałem się na Javę, ale C / C ++ może być inną opcją). Potrzebuję użyć...
Słyszałem kilka razy, że dla wystarczająco małych wartości n, O (n) można myśleć / traktować tak, jakby to był O (1). Przykład : Motywacja do tego jest oparta na błędnym założeniu, że O (1) jest zawsze lepsze niż O (lg n), zawsze jest lepsze niż O (n). Asymptotyczna kolejność operacji jest...
Jednym z hiperparametrów dla sieci LSTM jest temperatura. Co to
Mój problem polega na tym, jak mogę udowodnić, że gramatyka jest jednoznaczna? Mam następującą gramatykę: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if }...
Dość proste jest zrozumienie, dlaczego problem zatrzymania jest nierozstrzygalny w przypadku nieczystych programów (tj. Tych, które mają operacje we / wy i / lub stany zależne od stanu globalnego maszyny); ale intuicyjnie wydaje się, że zatrzymanie czystego programu na idealnym komputerze byłoby...
Szukam algorytmu do dystrybucji wartości z listy, aby powstała lista była jak najbardziej „zrównoważona” lub „równomiernie rozłożona” (w cudzysłowie, ponieważ nie jestem pewien, czy są to najlepsze sposoby na opisanie jej ... później przedstawię sposób pomiaru, czy wynik jest lepszy niż inny). Tak...
Masz jedną monetę. Możesz go obrócić tyle razy, ile chcesz. Chcesz wygenerować losową liczbę taką, że gdzie .a ≤ r < b r , a , b ∈rrrza≤r<ba≤r<ba \leq r < br , a , b ∈ Z+r,a,b∈Z+r,a,b\in \mathbb{Z}^+ Rozkład liczb powinien być jednolity. Łatwo jest, jeśli :b - a = 2nb−a=2nb -a = 2^n r...