W mojej klasie Java uczymy się o złożoności różnych typów kolekcji. Wkrótce będziemy rozmawiać o drzewach binarnych, o których czytałem. Książka stwierdza, że minimalna wysokość drzewa binarnego wynosi , ale nie oferuje dalszych wyjaśnień.log2( n + 1 ) - 1log2)(n+1)-1\log_2(n+1) - 1 Czy ktoś...
Jak udowodnić, że oczekiwana wysokość losowo zbudowanego drzewa wyszukiwania binarnego z węzłami wynosi ? Istnieje dowód we CLRS Wstęp do algorytmów (rozdział 12.4), ale ja go nie rozumiem.nnnO(logn)O(logn)O(\log
Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka...
Naprawdę chciałbym, abyś pomógł mi udowodnić, co następuje. Jeżeli N T i m e ( n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000}) , a następnie P=NPP=NP\mathrm{P}=\mathrm{NP} . Tutaj NTime(n100)NTime(n100)\mathrm{NTime}(n^{100}) jest klasą...
Załóżmy, że mam ukierunkowany wykres z wagami krawędzi narysowanymi z zakresu [1,…,K][1,…,K][1,\dots, K] gdzie KKK jest stałe. Jeśli próbuję znaleźć najkrótszą ścieżkę za pomocą algorytmu Dijkstry , jak mogę zmodyfikować strukturę algorytmu / danych i poprawić złożoność czasu do...
Czy istnieją języki programowania (lub logika), które mogą implementować (lub wyrażać) funkcję tylko i tylko wtedy, gdy jest obliczalną funkcją bijectywną? ff:N→Nf:N→Nf:\mathbb{N}\to
Pochodzi z POV kogoś, kto myśli o zdobyciu tytułu doktora informatyki. Mam problem z podjęciem decyzji, na czym skoncentruję swoje badania, kiedy doktoryzuję się. Zobacz także to pytanie na stronie academia.SE . Myślę więc, że czytanie / bieżące śledzenie prowadzonych badań i publikowanych prac...
Czasem jest oszałamiająca tablica symboli używanych w papierach matematycznych i CS. Jednak wielu zakłada podstawową znajomość, która wydaje się rzadko nauczana w jednym miejscu. Szukam słownika podobnego do następującego, szczególnie z perspektywy CS. Wymienia wszystkie podstawowe symbole...
maximize f(x)subject to Ax=bmaximize f(x)subject to Ax=b\text{maximize } f(\mathbf{x}) \quad\text{subject to } \mathbf{Ax} = \mathbf{b} gdzie f(x)=∑i=1N1+x4i(∑Ni=1x2i)2−−−−−−−−−−−−−⎷,f(x)=∑i=1N1+xi4(∑i=1Nxi2)2,f(\mathbf{x}) =
Potrzebuję pomocy w określeniu funkcji potencjalnej dla stosu maksymalnego, aby wyciąg maksymalny został zakończony w czasie zamortyzowanym . Powinienem dodać, że nie rozumiem potencjalnie tej metody.O ( 1 )O(1)O(1) Wiem, że funkcja wstawiania powinna „płacić” więcej, aby zmniejszyć koszt...
Podczas studiów licencjackich wziąłem kurs na kompilatory, w którym napisaliśmy kompilator, który kompiluje programy źródłowe w zabawnym języku podobnym do języka Java z językiem montażu zabawek (dla którego mieliśmy tłumacza). W projekcie przyjęliśmy pewne założenia dotyczące maszyny docelowej...
Ta strona o algorytmie Knuth-Moriss-Pratt w porównaniu do Boyera-Moore'a opisuje możliwy przypadek, w którym algorytm Boyera-Moore'a cierpi z powodu małej odległości pominięcia, podczas gdy KMP może działać lepiej. Szukam dobrego przykładu (tekst, wzór), który może jasno zademonstrować ten...
Co to są funkcje anonimowe (lambda)? Jaka jest formalna definicja anonimowej funkcji w funkcjonalnym języku programowania? Mówiąc najprościej, kiedy programuję w schemacie / lisp, powiedziałbym, że funkcja anonimowa (lambda) jest funkcją niezwiązaną z identyfikatorem. Czy to wszystko, co możesz...
Rozważ następujący problem, którego instancją wejściową jest prosty wykres i naturalna liczba całkowita k .solGGkkk Czy istnieje zestaw taki, że G - S jest dwustronny i | S | ≤ k ?S.⊆ V.( G )S⊆V(G)S \subseteq V(G)G - SG−SG - S| S.| ≤k|S|≤k|S| \leq k Chciałbym pokazują, że problem ten jest...
Ostatnio natknąłem się na artykuł opisujący technikę parsowania wspomnianą w tytule. Niestety terminologia zastosowana we wspomnianym artykule jest nieco poza moim zrozumieniem, więc starałem się zrozumieć algorytm konstrukcji bardziej intuicyjnie. Wierzę, że mi się udało ( ta prezentacja była...
Maszyny Turinga i nieograniczona gramatyka to dwa różne formalizacje, które definiują języki RE. Niektóre języki RE są rozstrzygalne, ale nie wszystkie są. Możemy zdefiniować rozstrzygalne języki za pomocą maszyn Turinga, mówiąc, że dany język jest rozstrzygalny, jeśli istnieje TM dla języka,...
Jest to problem z sesji treningowej Polskiego Konkursu Programowania Uczelnianego 2012 . Chociaż mogłem znaleźć rozwiązania dla głównego konkursu, nie mogę nigdzie znaleźć rozwiązania tego problemu. Problem polega na tym: biorąc pod uwagę zbiór NNN wyraźnych liczb całkowitych dodatnich nie...
Uczę się klasyfikacji SVM i napotykam problem. Nie jestem pewien, czy ten dylemat ma na to terminologię. Załóżmy, że chcielibyśmy sklasyfikować pacjenta według SVM na podstawie próbek zdrowych osób (obu płci) i osób z rakiem wątroby (obu płci). Jeśli oznaczymy osoby zdrowe jako próbki klasy 1, a...
Z punktu widzenia zachowania asymptotycznego, co jest uważane za „wydajny” algorytm? Jaki jest standard / powód rysowania linii w tym punkcie? Osobiście uważałbym, że wszystko, co naiwnie nazwałbym „sub-wielomianem”, takie jakfa( n ) = o (n2))f(n)=o(n2)f(n) = o(n^2) Jak na przykład n1 +...
Nie mogę owinąć głowy, jak działa SR Latch. Pozornie podłączasz linię wejściową z R, a drugą z S i powinieneś uzyskać wyniki w i .QQQQ′Q′Q' Jednak zarówno R, jak i S wymagają danych wejściowych z danych wyjściowych drugiej strony, a dane wyjściowe drugiej strony wymagają danych wejściowych z...