Chcesz poprawić ten post? Podaj szczegółowe odpowiedzi na to pytanie, w tym cytaty i wyjaśnienie, dlaczego Twoja odpowiedź jest poprawna. Odpowiedzi bez wystarczającej ilości szczegółów mogą być edytowane lub usuwane. Czytaliśmy o algorytmach dla MST, silnej łączności,...
Czy gramatyka bezkontekstowa może zawierać „martwe stany” z automatu, np G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,? B→CB→CB\to CC→cCC→cCC\to cC will loop forever and never...
Mamy logikę Hoare'a. Dlaczego wciąż jest możliwe, że algorytm ma rację, ale nie ma dowodów na jego poprawność? Załóżmy, że algorytm jest wyrażony w C. Następnie możemy argumentować krok po kroku, że robi to, co powinien. Więc moje pytanie brzmi: Podaj przykład algorytmu, który jest odpowiedni,...
Po wydaniu biblioteki AIGER do obsługi wykresów i inwerterów w pewnym momencie w 2006 r. (Tak mi się wydaje), niektóre solvery z obwodami SAT zostały wydane w latach 2006-2008, a na kilku wyścigach / konkursach SAT były ścieżki AIG. Jednak od tego czasu wydaje się, że skupiono się całkowicie na SMT...
Jestem nowy w teorii języków programowania. Oglądałem kilka wykładów online, w których instruktor twierdził, że funkcją typu polimorficznego forall t: Type, t->tjest tożsamość, ale nie wyjaśniłem dlaczego. Czy ktoś może mi wyjaśnić, dlaczego? Może dowód roszczenia z pierwszych...
Czy maszyna Turinga bez możliwości pisania na pustych komórkach jest mniej wydajna niż standardowy Turing? Myślę, że odpowiedź brzmi tak, ale nie jestem w stanie znaleźć obliczeń, które mogłaby wykonać standardowa maszyna Turinga, ale ta maszyna nie. Jakieś
Czy istnieje funkcja obliczalna taka, że:f:N→Qf:N→Qf:\mathbb{N}\rightarrow \mathbb{Q} Dla wszystkicht∈N:0≤f(t)<Xt∈N:0≤f(t)<Xt\in\mathbb{N}: 0\le f(t) < X limt→∞f(t)=Xlimt→∞f(t)=X\lim\limits_{t\rightarrow\infty} f(t) = X Gdzie XXX jest nieobliczalną liczbą rzeczywistą. Jedyne odniesienie...
Jeśli istnieje algorytm działający w czasie O(f(n))O(f(n))O(f(n)) dla jakiegoś problemu A, a ktoś wymyśli algorytm działający w czasie, , gdzie , czy uważa się to za ulepszenie w stosunku do poprzedniego algorytmu?O(f(n)/g(n))O(f(n)/g(n))O(f(n)/g(n))g(n)=o(f(n))g(n)=o(f(n))g(n) = o(f(n)) Czy ma...
Chcę wiedzieć, czy można rozwiązać następujący problem i jak się dowiedzieć. W każdym problemie, który widzę, mogę powiedzieć „tak” lub „nie”, więc czy większość problemów i algorytmów można rozstrzygać, z wyjątkiem kilku (które podano tutaj )? Wejście: kierowane i skończonych wykres z i , jak...
Słyszałem motto oddziaływanie jest silniejsze niż algorytmów z Peterem Wegner . Podstawą tego pomysłu jest to, że (klasyczna) Maszyna Turinga nie jest w stanie poradzić sobie z interakcją, to znaczy komunikacją (wejście / wyjście) ze światem zewnętrznym / środowiskiem. Jak to może być tak? Jak...
Uczę się samodzielnie Automated Theorem Proving / Solver SMT / Proof Assistants i zamieszczam serię pytań na temat tego procesu, zaczynając tutaj . Ciągle czytam o algorytmie unifikacji . Co to jest i dlaczego jest tak ważne dla silników wnioskowania ? Dlaczego jest tak ważny dla...
Według Wikipedii , dla każdego zwykłego języka istnieją stałe i wielomiany takie, że dla każdego liczby słów o długości w spełnia
Jakie operacje należy wykonać, aby wykonać dowolne obliczenia analogowe ? Czy dodawanie, odejmowanie, mnożenie i dzielenie byłoby wystarczające? Ponadto, czy ktoś dokładnie wie, jakie problemy można rozwiązać za pomocą obliczeń analogowych, ale nie w przypadku
Próbuję zrozumieć związek między NP-Intermediate a NP-Complete. Wiem, że jeśli P! = NP na podstawie twierdzenia Ladnera, istnieje klasa języków w NP, ale nie w P lub w NP-Complete. Każdy problem w NP można zredukować do problemu NP-Complete, jednak nie widziałem żadnych przykładów zmniejszania...
Myślałem asocjacyjną (tj mapie lub słownika) i tabela mieszania były takie same pojęcia, dopóki nie zobaczyłem w Wikipedii tym W przypadku słowników z bardzo małą liczbą powiązań sensowne może być zaimplementowanie słownika przy użyciu listy powiązań, połączonej listy powiązań. ......
Jakie są różnice między wizją komputera a przetwarzaniem obrazu? Na przykład w rozpoznawaniu obiektów, jakie są role wizji komputerowej i przetwarzania
W wielu dyskusjach na temat sterty binarnej zwykle tylko klawisz zmniejszania jest wymieniony jako obsługiwana operacja dla sterty min. Na przykład rozdział 6.1 CLR i ta strona Wikipedii . Dlaczego zwykle nie jest wyświetlany klucz zwiększenia dla min-sterty? Wyobrażam sobie, że można to zrobić w O...
Czy istnieje jakaś ogólna technika dla udowodnienia, że problem NIE jest NP-Complete? Dostałem to pytanie na egzaminie, które poprosiło mnie o wykazanie, czy jakiś problem (patrz poniżej) jest NP-Complete. Nie mogłem wymyślić żadnego prawdziwego rozwiązania, a właśnie udowodniłem, że było w P....
Czy istnieje maszyna Turinga, która zatrzymuje się na wszystkich wejściach, ale z jakiegoś powodu ta właściwość nie jest możliwa do udowodnienia? Zastanawiam się, czy to pytanie zostało zbadane. Uwaga: „nie do udowodnienia” może oznaczać „ograniczony” system dowodowy (który w słabym sensie...
Czy to prawda, że spójność sekwencyjna jest silniejszą właściwością niż spójność pamięci podręcznej? Według Sorin, Daniel J; Hill, Mark D; Wood, David A: A Primer on Memory Consistency and Cache Coherence , Morgan & Claypool, 2011 sekwencyjną spójność można opisać jako (nie formalnie):...