Teoretyczne informatyka ds.data-structures

3

Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”? Na przykład: czy można dodać funkcjonalność SplitSplitSplit i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe ?JoinJoinJoinO(1)O(1)\mathcal{O}(1) Lub: czy można zaimplementować uporządkowany zestaw z kluczami całkowitymi i …

14 ds.data-structures big-list lower-bounds time-complexity

2

Czysto funkcjonalny odpowiednik B-Tree?

Badam pomysł napisania DBMS w czysto funkcjonalny sposób. Tradycyjna struktura danych używana do indeksowania to B-Tree. Chciałbym poznać jakiś czysto funkcjonalny odpowiednik B-Tree, który zostałby zoptymalizowany w celu zminimalizowania dostępu do dysku. Dzięki.

14 ds.data-structures functional-programming db.databases

3

Asocjacyjne mieszanie skrótów

Rozważ mało pojedynczo połączoną listę w czysto funkcjonalnym otoczeniu. Jego pochwały śpiewano ze szczytów górskich i nadal będą śpiewane. Zajmę się tutaj jedną z wielu jego mocnych stron i pytaniem, w jaki sposób można ją rozszerzyć na szerszą klasę czysto funkcjonalnych sekwencji opartych na drzewach. Problem jest następujący: Chcesz przetestować …

14 ds.data-structures cr.crypto-security functional-programming hash-function

4

Podzakres drzewa czerwonego i czarnego

Próbując naprawić błąd w bibliotece, bezskutecznie szukałem artykułów na temat znajdowania podzakresów na czerwonych i czarnych drzewach. Zastanawiam się nad rozwiązaniem wykorzystującym zamki błyskawiczne i czymś podobnym do zwykłej operacji dołączania stosowanej w algorytmach usuwania niezmiennych struktur danych, ale wciąż zastanawiam się, czy istnieje lepsze podejście, którego nie udało mi …

14 ds.data-structures tree

2

Listy różnic w programowaniu funkcjonalnym

Pytanie Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki? oraz epicka odpowiedź jbapple, wspomniana przy użyciu list różnic w programowaniu funkcjonalnym (w przeciwieństwie do programowania logicznego), co mnie ostatnio interesowało. To doprowadziło mnie do znalezienia implementacji listy różnic dla Haskell. Mam dwa pytania (wybacz mi / popraw, jeśli …

14 reference-request ds.data-structures pl.programming-languages functional-programming logic-programming

1

Ile niezależności jest potrzebne do oddzielnego łączenia?

Jeśli kulek zostanie rozmieszczonych losowo w koszach równomiernie, w najbardziej obciążonym pojemniku znajdują się kulki z dużym prawdopodobieństwem. W „The Power of Simple Tabulation Hashing” Pătraşcu i Thorup wspominają, że „Chernoff-Hoeffding ogranicza się do aplikacji o ograniczonej niezależności” ( lustro ) pokazuje, że to ograniczenie populacji najbardziej obciążonego pojemnika utrzymuje …

13 ds.data-structures randomness hash-function independence

2

Struktura danych dla aktualizacji interwałów i zapytań o liczbę zer

Szukam struktury danych, która utrzymywałaby tablicę liczb całkowitych o rozmiarze , i pozwalała na następujące operacje w czasie .tttnnnO(logn)O(log⁡n)O(\log n) increase(a,b)increase(a,b)\text{increase}(a,b) , który zwiększa .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b] decrease(a,b)decrease(a,b)\text{decrease}(a,b) , co zmniejsza .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b] support()support()\text{support}() , która zwraca liczbę indeksów takich, że .iiit[i]≠0t[i]≠0t[i]\neq 0 Obiecujesz, że każde połączenie do zmniejszenia można dopasować do poprzedniego …

13 ds.data-structures cg.comp-geom

4

Odniesienie do podstawowego twierdzenia o rotacji drzew

Mówi się, że dwa drzewa wyszukiwania binarnego są liniowo równoważne, jeśli zgadzają się w swoich wędrówkach w kolejności. Poniższe twierdzenie wyjaśnia, dlaczego rotacje drzew są tak fundamentalne: Niech A i B będą binarnymi drzewami wyszukiwania. Zatem A i B są liniowo równoważne wtedy i tylko wtedy, gdy są połączone sekwencją …

13 reference-request ds.data-structures

2

Struktura danych do dynamicznej alokacji pamięci

Pomyśl o modelu sondy komórkowej. Czy istnieje struktura danych, która może przydzielić ciągłe fragmenty pamięci o dowolnej długości (jak np. Malloc w C) i zwolnić je, unikając segmentacji pamięci, i wykonuje każdą operację w najgorszym przypadku deterministycznym czasie O (log n), gdzie n jest całkowity rozmiar pamięci? Unikając segmentacji pamięci …

12 ds.data-structures memory

1

Kolejka liczb całkowitych priorytetowych z zależnym od dystrybucji deleteMin

Czy w kolejce liczb całkowitych priorytetowych, która używa słów spacji z następującymi operacjami, wszystko w najgorszym przypadku i bez dostępu do losowości:O(n)O(n)O(n) createEmptyQueuew dla pewnej stałej c .O(lgcU)O(lgcU)O(lg^c U)ccc insertw .O(1)O(1)O(1) deleteMinO(δmin)O(δmin)O(\delta_{\min})δminδmin\delta_{\min} Ponadto, gdy klucz zostanie poddany a , wszystkie dalsze wstawki mają .kkkdeleteMin>k>k> k Powiązana praca: „Szybkie lokalne wyszukiwania …

12 ds.data-structures

1

Minimalne elementy monotonicznego predykatu nad zestawem mocy

Rozważ monotoniczny predykat PPP nad zestawem mocy 2|n|2|n|2^{|n|}(uporządkowane przez włączenie). Przez „monotoniczny” rozumiem: ∀x,y∈2|n|∀x,y∈2|n|\forall x, y \in 2^{|n|}tak, że x ⊂ yx⊂yx \subset y , jeśli P.( x )P(x)P(x) to P.( y)P(y)P(y) . Szukam algorytmu, aby znaleźć wszystkie minimalne elementy P.PP , tj. x ∈ 2| n |x∈2|n|x \in 2^{|n|}takie, …

12 ds.algorithms ds.data-structures partial-order order-theory search-problem

6

Obliczanie przybliżonej populacji filtra Blooma

Biorąc pod uwagę filtr Blooma o rozmiarze N-bitów i funkcjach skrótu K, w których ustawionych jest M-bitów (gdzie M <= N) filtra. Czy jest możliwe przybliżenie liczby elementów wstawionych do filtra Bloom? Prosty przykład Zastanawiam się nad poniższym przykładem, zakładając BF 100 bitów i 5 funkcji skrótu, w których ustawiono …

12 ds.data-structures pr.probability

2

Odwracanie listy przy użyciu dwóch kolejek

To pytanie jest inspirowane istniejącym pytaniem, czy stos można symulować przy użyciu dwóch kolejek w zamortyzowanym czasie na operację stosu. Odpowiedź wydaje się nieznana. Oto bardziej szczegółowe pytanie, odpowiadające specjalnemu przypadkowi, w którym najpierw wykonywane są wszystkie operacje PUSH, a następnie wszystkie operacje POP. Jak skutecznie można odwrócić listę N …

12 ds.algorithms ds.data-structures lower-bounds time-complexity sorting

2

Proste zrównoważone drzewa z concat O (1)?

W czysto funkcjonalnych najgorszych przypadkach sortowanych list o stałym czasie, Brodal i in. prezentuj czysto funkcjonalne zrównoważone drzewa z konkatenatem O (1) i wstawiaj, usuwaj i znajduj O (lg n). Struktura danych jest nieco skomplikowana. Czy istnieje prostsze zrównoważone drzewo wyszukiwania z konkatenacją O (1), funkcjonalne czy nie?

12 functional-programming ds.data-structures

2

Zabawa z odwrotnym Ackermannem

Odwrotna funkcja Ackermanna występuje często podczas analizy algorytmów. Świetna prezentacja tego jest tutaj: http://www.gabrielnivasch.org/fun/inverse-ackermann . i [Notacja: [x] oznacza, że zaokrąglamy w górę x do najbliższej liczby całkowitej, podczas gdy log ∗ omówiono tutaj iterowaną funkcję dziennika: http://en.wikipedia.org/wiki/Iterated_logarithm ]α1(n)=[n/2]α1(n)=[n/2]\alpha_1(n) = [n/2] α2(n)=[log2n]α2(n)=[log2⁡n]\alpha_2(n) = [\log_2 n] α3(n)=log∗nα3(n)=log∗⁡n\alpha_3(n) = \log^* n ......... …

11 ds.algorithms ds.data-structures bounds

Pytania otagowane jako ds.data-structures