Informatyka

Czytam o NPC i jego związku z PSPACE i chcę wiedzieć, czy problemy NPC można rozwiązać w sposób deterministyczny za pomocą algorytmu o najgorszym przypadku wymaganej przestrzeni wielomianowej, ale potencjalnie zajmującego wykładniczy czas (2 ^ P (n), gdzie P jest wielomianem). Co więcej, czy można...

Biorąc pod uwagę ten pseudo-kod portu bąbelkowego: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[j + 1] THEN switch(list,j,j+1) switched := true ENDIF NEXT IF switched = false THEN break ENDIF NEXT Jakie...

Zauważyłem, że w przewidywaniu gałęzi istnieją dwa różne typy stanów. W wykonywaniu superskalarnym, gdzie przewidywanie rozgałęzienia jest bardzo ważne i dotyczy głównie opóźnienia wykonania, a nie opóźnienia pobierania. W potoku instrukcji, gdzie pobieranie jest większym problemem, ponieważ...

Które z następujących wyrażeń jest poprawne? istnieją wystarczające i konieczne warunki dotyczące prawidłowości języka, ale jeszcze ich nie odkryto. Nie ma wystarczających i koniecznych warunków dotyczących prawidłowości języka. Pompowanie lematu jest niezbędnym warunkiem nieregularności...

Rozważ system plików ukierunkowany na niektóre urządzenia osadzone, który robi niewiele więcej niż przechowywanie plików w hierarchicznej strukturze katalogów. W tym systemie plików brakuje wielu operacji, do których możesz być przyzwyczajony w systemach takich jak Unix i Windows (na przykład jego...

Jak można rozstrzygać, czy ma pewną sekwencję cyfr? ππ\pizainspirowało mnie do pytania, czy można obliczyć następującą niewinnie wyglądającą odmianę: fa( n ) = { 10jeśli  n¯ występuje w postaci dziesiętnej  πInaczejf(n)={1if n¯ occurs in the decimal representation of π0otherwisef(n) =...

Przepisanie systemu jest zestaw reguł w postaci . Jeśli zastosujemy tę regułę do łańcucha , zastąpimy dowolny podciąg in podciągiem i odwrotnie.A↔BA↔BA \leftrightarrow BwwwAAAwwwBBB Biorąc pod uwagę początkowy ciąg możemy wyprowadzić w systemie według następujących...

Dozownik napojów wymaga od użytkownika włożenia monety ( do¯c¯\bar c ), a następnie naciśnięcia jednego z trzech przycisków: prosi o filiżankę herbaty , to samo na kawę, i prosi o zwrot pieniędzy (tzn. maszyna zwraca monetę: ). Dozownik można modelować za pomocą następującego procesu CCS :eherbaty...

Algorytm maszyny Turinga w czasie wielomianowym jest uważany za wydajny, jeśli jego czas działania, w najgorszym przypadku, jest ograniczony przez funkcję wielomianu w wielkości wejściowej. Mam świadomość silnej tezy Kościoła-Turinga: Każdy rozsądny model obliczeń może być skutecznie symulowany...

Może się to wiązać z obliczeniową kognitywistyką, ale jestem ciekawy, w jaki sposób proces, po którym następują popularne algorytmy wyszukiwania ścieżek (takie jak A * ), porównuje się z procesem stosowanym przez ludzi w różnych sytuacjach poszukiwania ścieżki (biorąc pod uwagę te same informacje)....

Mam następujący język {0i1j2k∣0≤i≤j≤k}{0i1j2k∣0≤i≤j≤k}\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\} Próbuję ustalić, do której klasy języka Chomsky pasuje. Widzę, jak można to zrobić za pomocą gramatyki kontekstowej, więc wiem, że jest przynajmniej wrażliwa na kontekst. Wydaje się, że nie...

Obecnie uczę się rachunku lambda i zastanawiałem się nad następującymi dwoma różnymi rodzajami pisania terminu lambda. λxy.xyλxy.xy\lambda xy.xy λx.λy.xyλx.λy.xy\lambda x.\lambda y.xy Czy jest jakaś różnica w znaczeniu lub sposobie zastosowania redukcji wersji beta, czy to tylko dwa sposoby...

Jeśli dobrze rozumiem, NFA mają taką samą moc ekspresji jak wyrażenia regularne. Często odczytywanie równoważnych wyrażeń regularnych z NFA jest łatwe: przekładasz cykle na gwiazdy, skrzyżowania jako alternatywy i tak dalej. Ale co zrobić w tym przypadku: [ źródło ] Nakładające się cykle...

Algorytm simpleks chciwie chodzi po rogach wielopola, aby znaleźć optymalne rozwiązanie problemu programowania liniowego. W rezultacie odpowiedź jest zawsze rogiem polytopa. Metody punktowe wewnętrzne chodzą po polytopie. W rezultacie, gdy cała płaszczyzna polytopu jest optymalna (jeśli funkcja...

Jest to zwiastun mojego drugiego, bardziej zaawansowanego pytania o Inspekcję stosu. Inspekcja stosu to mechanizm bezpieczeństwa wprowadzony w JVM w celu obsługi kodu działającego z lokalizacji o różnych poziomach zaufania. To pytanie ma na celu znalezienie prostego opisu jego funkcjonalności....

Mam zadanie domowe, od którego walę głową od jakiegoś czasu i byłbym wdzięczny za wszelkie wskazówki. Chodzi o wybranie znanego problemu, którego kompletność NP jest udowodniona, i skonstruowanie redukcji z tego problemu do następującego problemu, który nazywam DGD (diagnostyka grafu...

Fibonnaci Heap obsługuje następujące operacje: insert(key, data) : dodaje nowy element do struktury danych find-min() : zwraca wskaźnik do elementu z minimalnym kluczem delete-min() : usuwa element z minimalnym kluczem delete(node) : usuwa element wskazany przez node decrease-key(node) :...

To pytanie do pracy domowej z książki Udi Manbera. Każda wskazówka byłaby miła :) Muszę pokazać, że: n ( log3)( n ) )5= O ( n1.2)n(log3⁡(n))5=O(n1.2)n(\log_3(n))^5 = O(n^{1.2}) Próbowałem użyć Twierdzenia 3.1 książki: fa( n )do= O ( afa( n ))f(n)c=O(af(n))f(n)^c = O(a^{f(n)}) (dla , )c...

Główna idea k-Nearest-Neighbor uwzględnia najbliższych punktów i decyduje o klasyfikacji danych większością głosów. Jeśli tak, to nie powinno mieć problemów z danymi o wyższych wymiarach, ponieważ metody takie jak mieszanie wrażliwe na lokalizację mogą skutecznie znaleźć najbliższych...

Pracuję nad językiem genealogicznym ML opartym na wyrażeniach, więc oczywiście wymaga wnioskowania typu> :) Teraz próbuję rozszerzyć oparte na ograniczeniach rozwiązanie problemu wnioskowania typów, oparte na prostej implementacji w EOPL (Friedman i Wand), ale są to eleganckie algebraiczne typy...