Interesuję się, gdy dowiaduję się więcej o algorytmach i strukturach danych nieobsługiwanych przez pamięć podręczną, ale jest tak wiele dokumentów, że tak naprawdę nie wiem od czego zacząć. Znalazłem oryginalną tezę Prokupa na ten temat, co wydaje się dobrym punktem wyjścia, ale jeśli istnieje...
Mam duży zestaw danych o drzewach i chciałbym je przeszukać, określając treelet (połączony podgrupa). Kwerenda powinna zwrócić wszystkie wystąpienia treeline w zbiorze danych. Czy istnieją wydajne algorytmy do tego celu? Myślałem o czymś takim jak tablice sufiksów, jednak naiwne kodowanie drzew,...
Ponieważ ostatnio uczę podstaw rachunku λ, wdrożyłem prosty ewaluator λ w Common Lisp. Kiedy pytam o normalną formę Y fac 3redukcji w normalnym porządku, zajmuje to 619 kroków, co wydawało się trochę za dużo. Oczywiście, za każdym razem, gdy robiłem podobne redukcje na papierze, nigdy nie...
Czytam więc trochę o opracowaniu, w szczególności algorytmach opartych na dwukolorowym rachunku budowy i jestem trochę zdezorientowany. Nie rozumiem, jaki dokładnie jest cel tegododob jadodobjaCC^{bi}jest. Wydaje się być identyczny zdodododoCCz wyjątkiem tego, że istnieje rozróżnienie między...
Jaka jest średnia liczba publikacji (w tym materiałów konferencyjnych) rocznie dla badaczy z tytułem doktora CS w USA? Jakie są sposoby na znalezienie lub oszacowanie tej
Zastanawiam się, czy istnieją systematyczne badania sum kwadratowych form kwadratowych, podobnych do form kwadratowych, co praktycznie znajduje odzwierciedlenie w rozkładzie wartości własnych (co ma ogromne praktyczne implikacje). Kilka przykładów związanych ze znaczeniem pytania. Analizy...
EDYTOWANO, ABY DODAĆ : Na to pytanie zasadniczo udzielono odpowiedzi; zobacz ten wpis na blogu, aby uzyskać więcej informacji. Dziękujemy wszystkim, którzy opublikowali tutaj komentarze i odpowiedzi. PYTANIE ORYGINALNE Jest to, mam nadzieję, mądrzejsza i lepiej poinformowana wersja pytania,...
Mam skończony zestaw S.SS, funkcja fa: S→ Sf:S→Sf:S\to Soraz całkowite zamówienie
Złożoności Kołmogorowa łańcucha nie można obliczyć. Jednakże, w losowej podgrupy o rozmiarze dwuskładnikowych ciągi o długości , ile, będą miały mniejszą złożoność niż pewnej liczby całkowitej mniej niż (jako funkcja , i
Mam rodzinę problemów z programowaniem liniowym: maksymalizuj c′xdo′xc' x z zastrzeżeniem Ax≤bZAx≤bA x\le b, x≥0x≥0x\ge0. ElementyAZAA, bbb, i cdoc są liczbami całkowitymi nieujemnymi, cdocściśle pozytywne. (xxx powinien być również integralny, ale będę się tym martwić później). W mojej aplikacji...
Zastanawiałem się, jakie zestawy języków są generowane przez ograniczenia wyrażeń regularnych. Załóżmy, że wszystkie ograniczenia mają stały symbol dla każdego elementuΣΣ\Sigmai konkatenacja. Następnie można utworzyć osiem klas poprzez obecność lub brak dopełniacza / negacji, zmiany / unii i...
Wszędzie, gdzie czytam o najrzadszym problemie cięcia, mówi tylko, że wiadomo, że jest to problem NP . Gdzie mogę znaleźć na to dowód? Który znany problem NP -twardości sprowadza się do najrzadszego problemu cięcia? Nie znalazłem żadnego dowodu w książce Vazirani - Algorytmy aproksymacji, która...
Staram się pokazać, że pewien problem jest nie do przyjęcia przez redukcję z zestawu. Moja redukcja przekształca instancję z zestawem naziemnym o rozmiarach i w instancję mojego problemu, w której pewien parametr ma rozmiar . Mogę następnie pokazać, że wystąpienie zestawu okładki, w którym rozmiar...
Wikipedia - mówi SHA-2 SHA-224 jest identyczny z SHA-256, z wyjątkiem tego, że: początkowe wartości zmiennych od h0 do h7 są różne, i wyjście jest konstruowane przez pominięcie h7. RFC3874 - 224-bitowa jednokierunkowa funkcja skrótu: mówi SHA-224 Zastosowanie innej wartości...
(Na moje pierwotne pytanie wciąż nie ma odpowiedzi. Dodałem dalsze wyjaśnienia.) Analizując losowe spacery (na niekierowanych grafach), widząc losowy spacer jako łańcuch Markowa, wymagamy, aby wykres nie był dwustronny, aby obowiązywało podstawowe twierdzenie o łańcuchach Markowa. Co się stanie,...
W problemie Max-Cut szuka się podzbioru S wierzchołków danego prostego niekierowanego wykresu, tak że liczba krawędzi między S a dopełnieniem S jest tak duża, jak to możliwe. Max-Cut jest kompletny APX na wykresach ograniczonego stopnia [PY91], i faktycznie APX-kompletny na wykresach sześciennych...
W przypadku aplikacji uczenia maszynowego moja grupa musi obliczyć odległość euklidesową do tego najbliższego sąsiada w zbiorze dla każdego (dla od 5 do około 100 oraz kilkaset do kilku milionów). Obecnie podejście albo oczywiste z drzewem kd na , które gdy jest wysokie, ajest stosunkowo niski,...
Biorąc podmodular funkcji faff na Ω =X1∪X2)Ω=X1∪X2\Omega=X_1\cup X_2 gdzie X1X1X_1 i X2)X2X_2 są rozłączni i fa( S) =fa1( S∩X1) +fa2)( S∩X2))f(S)=f1(S∩X1)+f2(S∩X2)f(S)=f_1(S\cap X_1)+f_2(S\cap X_2). Tutajfa1f1f_1 i fa2)f2f_2 są podmodularne X1X1X_1 i X2)X2X_2 odpowiednio. Tutaj...
Uczę się algebraicznej teorii parsowania. Moim pierwszym problemem jest zidentyfikowanie przykładów semieralnych, które są specyficzne dla formalnej teorii języka. Oto próba skonstruowania dwóch przykładów. 1 Biorąc pod uwagę gramatykę CNF, elementy semeryzacji są zestawami symboli terminalnych i...
Próbuję dowiedzieć się więcej na temat sprawdzania typu całego programu i systemów wnioskowania o typie, które wykorzystują informacje z witryn wywołań funkcji do obliczania informacji o typie (oprócz standardowego podejścia do używania treści funkcji). Na przykład taki algorytm może użyć wywołania...