Jeśli mam gramatykę typu 3, można ją przedstawić na automacie wypychania (bez wykonywania żadnych operacji na stosie), dzięki czemu mogę reprezentować wyrażenia regularne przy użyciu języków bezkontekstowych. Ale czy mogę wiedzieć, czy gramatyka typu 3 to , , itd. Bez konstruowania jakichkolwiek...
Niech będzie stałą funkcją konstruowaną w czasie.fff Klasyczny uniwersalny wynik symulacji dla TM (Hennie i Stearns, 1966) stwierdza, że istnieje TM z dwiema taśmami, takaUUU opis TM i⟨M⟩⟨M⟩\langle M \rangle ciąg wejściowy ,xxx uruchamia kroki i zwraca odpowiedź na . I może być dowolną...
Studiowałem te trzy i poniżej przedstawiam swoje wnioski. Czy ktoś mógłby mi powiedzieć, czy dobrze je zrozumiałem, czy nie? Dziękuję Ci. Dijkstra algorytm jest używany tylko wtedy, gdy masz jedno źródło i chcesz wiedzieć najmniejszą ścieżkę z jednego węzła do drugiego, ale nie w przypadkach...
Rozumiem, że użycie DFS „tak jak jest” nie znajdzie najkrótszej ścieżki na nieważonym wykresie. Ale dlaczego poprawianie DFS, aby umożliwić mu znajdowanie najkrótszych ścieżek na nieważonych wykresach, jest tak beznadziejną perspektywą? Wszystkie teksty na ten temat po prostu stwierdzają, że nie...
Nie jestem pewien, czy w teorii komputerowej używa się zwrotów „nieskończony” język lub „skończony” język. Myślę, że źródłem problemu jest to, że język taki jak jest nieskończony w tym sensie, że może wygenerować nieskończoną (ale policzalną) liczbę łańcuchów. Jednak nadal może być rozpoznany...
Zastanawiam się, czy to w ogóle możliwe, ponieważ . Dlatego PDA, który potrafi odróżnić słowo od reszty równie dobrze może je zaakceptować , co wydaje mi się sprzeczne. w ∈ { a n b n c n ∣ n ≥ 0 } { a ∗ b ∗ c ∗ }{ anbndon∣ n ≥ 0 } ∉ C F L{zanbndon∣n≥0}∉dofaL.\{a^n b^n c^n \mid n \geq 0\} \not\in...
W tym pytaniu rozważamy tylko maszyny Turinga, które zatrzymują się na wszystkich wejściach. Jeśli to przez oznaczamy maszynę Turinga, której kod tok∈Nk∈Nk \in \mathbb{N}TkTkT_kkkk . Rozważ następującą funkcję s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y) = \min\{k \mid...
Ostatnio bardzo się zainteresowałem zrozumieniem i sprawdzeniem aspektów (funkcjonalnych) języków programowania. Jednak gdy zagłębiam się głębiej, rzeczy takie jak rachunek , teoria kategorii i semantyka denotacyjna są nieco trudne do odczytania bez odpowiedniego wyjaśnienia.λλ\lambda Czytam SICP...
Mam kilka obiektów o priorytecie, które są typu złożonego i są tylko częściowo uporządkowane . Muszę wybierać obiekty w kolejności tego priorytetu (tzn. Za każdym razem uzyskiwać minimalny przedmiot). Ale zamiast arbitralnie realizować zamówienie, wolałbym, aby kolejka była stabilna w takim sensie,...
Mówimy, że język jest gęsty, jeśli istnieje wielomian taki, że dla wszystkichInnymi słowy, dla dowolnej długości istnieje tylko wielomianowo wiele słów o długości , które nie są wJ⊆Σ∗jot⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|jotdo∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N..n \in...
Użyłem FSM w projektach cyfrowych układów sekwencyjnych. Ale nie znam Finata Automata. Czy ktoś może mi pomóc w zrozumieniu „podstawowej” różnicy między nimi?
Częstym pytaniem w rozmowie kwalifikacyjnej jest podanie algorytmu określającego, czy dane drzewo binarne ma zrównoważoną wysokość (definicja drzewa AVL). Zastanawiałem się, czy możemy zrobić coś podobnego z czerwono-czarnymi drzewami. Biorąc pod uwagę dowolne bezbarwne drzewo binarne (z...
Podano wykres płaski G=(V,E)G=(V,E)G=(V,E) i niech oznacza jego osadzenie w płaszczyźnie st, każda krawędź ma długość . Mam ponadto zestaw punktów, w których każdy punkt jest zawarty w . Ponadto, dla dowolnego punktu w istnieje z odległością geodezyjną do co najwyżej jeden. (Odległość jest mierzona...
Dlaczego w pierwszej kolejności musimy przerzucać jądro w trybie splotu 2D? Jaka jest z tego korzyść? Dlaczego więc nie możemy pozostawić tego nieprzypiętego? http://www.songho.ca/dsp/convolution/convolution2d_example.html Wejście jądro wynik „Najpierw odwróć jądro, które jest zacienionym...
Rozważ następujące pytanie Google Code Jam w rundzie 1C : Wielki Mur Chiński zaczyna się od nieskończonej linii, której wysokość we wszystkich lokalizacjach wynosi .000 Pewną liczbę pokoleń , N ≤ 1000 , atakują murze ściany według następujących parametrów - początkowego dnia, D , wytrzymałość...
Chciałbym zbudować internetowy system uczenia maszynowego online, w którym użytkownicy mogą stale dodawać sklasyfikowane próbki i aktualizować model online. Chciałbym użyć perceptronu lub podobnego algorytmu uczenia się online. Jednak użytkownicy mogą popełniać błędy i wstawiać nieistotne...
Niedawno dowiedziałem się o istnieniu tej hierarchicznej pamięci czasowej (HTM) . Przeczytałem już dokument Hierarchical Temporal Memory: Concepts, Theory and Terminology (autorstwa Jeffa Hawkinsa i Dileepa George'a), który wydaje się raczej łatwy do zrozumienia, ale jedną czerwoną flagą jest to,...
Używając A * (lub innego algorytmu znajdowania najlepszej ścieżki), mówimy, że zastosowana heurystyka powinna być dopuszczalna , to znaczy nigdy nie powinna przeceniać faktycznej długości ścieżki rozwiązania (lub ruchów). W jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie?...
Dowiedziałem się, że procesor graficzny ma coś, co nazywa się łączeniem pamięci. Po przeczytaniu tego nie byłem jasny na ten temat. Czy ma to jakikolwiek związek z równoległością poziomu pamięci. Szukałem w Google, ale nie byłem w stanie uzyskać zadowalającej odpowiedzi. Byłoby pomocne, gdyby...
Mówi się, że przecięcie języka L bez kontekstu z językiem zwykłym M jest zawsze wolne od kontekstu. Zrozumiałem dowód na konstrukcję wielu produktów, ale wciąż nie rozumiem, dlaczego nie zawiera kontekstu, ale nie jest regularny. Język generowany przez takie skrzyżowanie ma ciągi znaków, które są...