W językach programowania zamknięcia są popularną i często pożądaną funkcją. Wikipedia mówi (moje podkreślenie): W informatyce zamknięcie (...) jest funkcją wraz ze środowiskiem odniesienia dla zmiennych nielokalnych tej funkcji. Zamknięcie umożliwia funkcji dostęp do zmiennych poza jej...
Problemu zatrzymania nie można rozwiązać w ogólnym przypadku. Można wymyślić zdefiniowane reguły, które ograniczają dozwolone dane wejściowe i czy problem zatrzymania można rozwiązać w tym szczególnym przypadku? Na przykład wydaje się prawdopodobne, że język, który nie dopuszcza na przykład pętli,...
Od odpowiedzi do (Kiedy) jest wyszukiwanie tablicy skrótów O (1)? , Rozumiem, że tabele skrótów mają O(1)O(1)O(1)zachowanie w najgorszym przypadku ) , przynajmniej zamortyzowane, gdy dane spełniają określone warunki statystyczne, i istnieją techniki, które pomagają rozszerzyć te warunki. Jednak z...
Mówiąc najprościej, gdyby zbudować kwantowe urządzenie obliczeniowe o mocy, powiedzmy, 20 kubitów, czy takiego komputera można by użyć do tego, aby jakikolwiek współczesny algorytm mieszający był bezużyteczny? Czy byłoby możliwe wykorzystanie mocy obliczeń kwantowych w tradycyjnej aplikacji...
Egzystencjalna teoria Real jest w PSPACE , ale nie wiem, czy to jest PSPACE zupełnych . Jeśli uważam, że tak nie jest, jak mogę to udowodnić? Mówiąc bardziej ogólnie, biorąc pod uwagę problem z pewną klasą złożoności X , jak mogę pokazać, że nie jest to X-Complete ? Na przykład X może oznaczać NP...
Kombinatoryka odgrywa ważną rolę w informatyce. Często stosujemy metody kombinatoryczne zarówno w analizie, jak i projektowaniu w algorytmach. Na przykład jedna metoda znajdowania zestawu okładek kkk -vertex na wykresie może po prostu sprawdzić wszystkie możliwe podzbiory . Podczas gdy funkcje...
Jak wynika z mojego poprzedniego pytania , bawiłem się hipotezą Riemanna jako zagadnieniem matematyki rekreacyjnej. W trakcie tego procesu doszłam do dość interesującego nawrotu i jestem ciekawa jego nazwy, jej redukcji i podatności na rozwiązywanie luki między liczbami pierwszymi. Krótko mówiąc,...
Czy problemy typu „obecność na imprezie” można rozwiązać w Prologu? Na przykład: Łopian Muldoon i Carlotta Pinkstone powiedzieli, że przybędą, jeśli przyjdzie Albus Dumbledore. Albus Dumbledore i Daisy Dodderidge powiedzieli, że przybędą, jeśli przyjdzie Carlotta Pinkstone. Albus Dumbledore,...
Jak sprawdzisz, czy dwa algorytmy (powiedzmy: Sortuj i Naiwne) zwracają ten sam wynik dla dowolnego wejścia, gdy zestaw wszystkich danych wejściowych jest nieskończony? Aktualizacja: Dziękuję Ben za opisanie, w jaki sposób niemożliwe jest algorytmiczne wykonanie tego przypadku w ogólnym przypadku....
Zacząłem czytać coraz więcej prac naukowych dotyczących języków. Uważam to za bardzo interesujące i dobry sposób, aby dowiedzieć się więcej o programowaniu w ogóle. Zazwyczaj jednak pojawia się sekcja, z którą zawsze się zmagam (na przykład część trzecia tego ), ponieważ brakuje mi teoretycznego...
Podręczniki wszędzie założyć, że Bounded post Korespondencja Problem jest NP-zupełny (nie więcej niż NN.N indeksy dozwolony z powtórzeń). Nigdzie jednak nie pokazano prostej (jak w czymś, co student może zrozumieć) wielomianowej redukcji czasu z innego problemu pełnego NP. Jednak każda redukcja, o...
Wikipedia to określa Mówi się, że algorytm ma czas wielomianowy, jeśli jego czas działania jest ograniczony górną granicą przez wyrażenie wielomianowe wielkości wejściowej dla algorytmu, tj. dla pewnej stałej k.T.( n ) = O ( nk)T.(n)=O(nk)T(n) = O(n^k) Algorytm działa w silnie wielomianowym...
W książce algorytmy randomizowane , Motwani i Raghavan otworzyć zapoznaniu się z opisem ich funkcji RandQS - randomizowane Quicksort - przy czym czop, służy do podziału zbioru na dwie części, jest wybierana losowo. Przez jakiś czas dręczyłem nad tym (co prawda trochę słabe) mózgi, ale nie byłem w...
Biorąc pod uwagę regularny język , łatwo jest udowodnić, że istnieje stała N, taka jak σ ∈ L , z | σ | ≥ N istnieją łańcuchy α , β i γ takie, że | α β | ≤ N i | β | ≠ ϵ i dla wszystkich k jest to α β k γ ∈ LLLLNNNσ∈Lσ∈L\sigma \in L|σ|≥N|σ|≥N\lvert \sigma \rvert \ge...
Biorąc pod uwagę macierzy . Niech macierz odwrotna do będzie (to znaczy, ). Załóżmy, że jeden element w został zmieniony (powiedzmy na ). Celem jest znalezienie po tej zmianie. Czy istnieje metoda znalezienia tego celu, który jest bardziej wydajny niż ponowne obliczenie macierzy odwrotnej od zera.A...
Ostatnio studiowałem samemu Maksymalizację oczekiwań i w tym czasie zdobyłem kilka prostych przykładów: Od tutaj : Istnieją trzy monety c0c0c_0 , i z , i odpowiednie prawdopodobieństwa do lądowania na głowie, kiedy rzucił. Rzuć . Jeśli wynikiem jest Głowa, rzuć trzy razy, w przeciwnym razie rzuć...
Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy a i b i zwraca prawdziwy iff a < b ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące...
Jeśli mam trudny problem, jednym ze standardowych sposobów jest wyrażenie go jako instancji SAT i próby uruchomienia na nim solvera SAT. Innym standardowym podejściem jest wyrażenie go jako problemu satysfakcji z ograniczeń i próba użycia solvera CSP. Obaj czują się nieco niejasno pod względem...
Interesuje mnie niewielki wariant układania płytek, układanka „układanka”: każda krawędź (kwadratowej) płytki jest oznaczona symbolem z , a dwie płytki można umieścić obok siebie do siebie iff symbol na przeciwległej krawędzi jednego kafelka to k, a symbol na przeciwległej krawędzi drugiego kafelka...
Znam kilkanaście języków programowania, które w pewien sposób mają wyjątki, ale doszedłem do wniosku, że mam dwie „patologiczne” tendencje. Wydaje się, że nie ma wspólnego wzorca lub hierarchii wyjątków. Każdy język w zasadzie rozwija własną wersję, a jeśli wyjątki staną się standardem, wówczas...