Teoretyczne informatyka ds.data-structures

1

Czy kiedykolwiek zaimplementowano drzewa partycji? Mówię tutaj o drzewach partycji z geometrii obliczeniowej. Najwcześniejsze (prawie) optymalne wersje były spowodowane przez Matouseka i innych, a ostatnio Timothy Chan: https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf To dla mnie szaleństwo, że nigdy nie zostały zaimplementowane, ale Google nie wykrył żadnych implementacji, o których nikt wcześniej nie donosił.

11 ds.data-structures implementation computational-geometry

4

Najkrótsza liczba edycji przechodzi między dwoma słowami

Szukam struktury danych i algorytmu do obliczenia minimalnej liczby zmian wymaganych do przekształcenia jednego słowa w drugie, biorąc pod uwagę dwa słowa jako dane wejściowe, gdzie jedynymi dozwolonymi zmianami są dodaj literę na jednym z krańców (na przykład AB -> ABC), powielać i konkatenować całe słowo (na przykład ABC -> …

11 graph-algorithms ds.data-structures edit-distance

3

Znajdź najkrótszą parą odległość punktów w o (n log n)?

Studenci, których nadzoruję, otrzymali następujące ćwiczenie: Biorąc pod uwagę punktów na płaszczyźnie, opracuj algorytm, który znajdzie parę punktów, których odległość jest minimalna wśród wszystkich par punktów. Algorytm powinien działać w czasie .o ( N 2 )nnno(n2)o(n2)o(n^2) Istnieje (stosunkowo) prosty algorytm dzielenia i zdobywania, który rozwiązuje zadanie w czasie .Θ(nlogn)Θ(nlog⁡n)\Theta(n \log …

11 ds.data-structures cg.comp-geom

1

Optymalne przetwarzanie wstępne dla niektórych rodzajów zapytań

Załóżmy, że mamy półgrupę z elementami . Naszym celem jest obliczanie produktów .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j W swoim artykule „Optymalne przetwarzanie wstępne dla odpowiedzi na zapytania produktów on-line” Alon i Schieber udowadniają, że możemy odpowiedzieć na każde takie zapytanie w co najwyżej krokach (gdzie jest odwrotną funkcją Ackermanna), używając …

11 cc.complexity-theory graph-theory ds.data-structures

2

Ustaw strukturę danych w celu wydajnego powtarzania wstawień

Szukam struktury danych zajmującej mało miejsca, która przechowuje zestawy (bez powtórzeń) elementów wordize i obsługuje szybkie wstawianie (amortyzowane O (1)). Przez „oszczędny przestrzennie” rozumiem idealnie, słów do przechowywania n elementów.n + o ( n )n+o(n)n + o(n)nnn Bycie zestawem jest ważną częścią pytania: jeśli każdy element zostanie dodany, razy wykorzystana …

11 ds.data-structures

2

Struktura danych, która umożliwia wydajne wyszukiwanie w oparciu o znaczniki

Szukam wysoce wydajnej struktury danych do przechowywania danych podobnych do poniższych. Identyfikatory Zamówienie 1 Zamówienie 2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 Muszę być w stanie kwerendy tej struktury w taki sposób, że daje mi listę wszystkich identyfikatorów zawierających …

11 ds.data-structures application-of-theory db.databases

1

Zdecydowanie zrównoważone deterministyczne listy pominięć

W sekcji 2.2 Cache-niepomny B-drzew , stanowczo Weight Balanced wyszukiwania Drzewa są zdefiniowane jako: Dla niektórych stałych , każdy węzeł na wysokości ma potomków .dddvvvhhhΘ(dh)Θ(dh)\Theta(d^h) Oni twierdzą: Drzewa wyszukiwania spełniające właściwości 1 i 2 obejmują zrównoważone pod względem masy drzewa B, deterministyczne listy pominięć i listy pominięć w oczekiwanym znaczeniu. …

11 ds.data-structures skip-lists

2

Jakiś szybki algorytm problemu z ustawieniem łuku zwrotnego przy minimalnych kosztach?

Na ukierunkowanym wykresie , F ⊂ E , jeśli G ∖ F jest DAG (ukierunkowany wykres acykliczny), F nazywa się zestawem łuku zwrotnego. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Jeżeli każda krawędź jest powiązana z wagą , problem z zestawem łukowym sprzężenia zwrotnego przy minimalnym koszcie polega na znalezieniu F takiej, że W …

11 ds.data-structures graph-theory np-hardness approximation-algorithms

2

Granice kompromisowe dla liczenia zakresu półprzestrzeni

Jaki jest obecnie najlepszy sposób wykonywania zapytań zliczających zakres półprzestrzeni na zbiorze punktów wymiarowych, wyrażony w formie kompromisu czas / przestrzeń. Zgodnie z przełomowym referatem Matouseka z 1993 r. (Twierdzenie 6.2, Wyszukiwanie zasięgu za pomocą wydajnych wycinków hierarchicznych), możemy wykonać zliczanie zasięgu dla zapytań, które są przecięciem półprzestrzeni , dla …

10 reference-request ds.data-structures cg.comp-geom

1

Odcisk palca dla zestawów dynamicznych

Czy istnieje w-bitowa struktura danych słowo-RAM z czasem O (1) na operację dla następującego problemu ?: Utrzymanie zestawu w-bitowych nieujemnych liczb całkowitych, które obsługują operacje add (x): dodaj x do zestawu remove (x): usuń x z zestawu odcisk palca (): zwraca odcisk palca zestawu. Ten w-bitowy odcisk palca ma właściwość …

10 ds.data-structures

4

Koszty wykonania ok. szukaj najbliższego sąsiada w pomijanym quadtree

UWAGA : Pytanie zostało ponownie sformułowane w moich odpowiedziach: Zakładając, że możemy znaleźć najniższych przodków rodzeństwa w czasie , czy ANN można naprawdę wykonać w ?O ( 1 )O(1)O(1)O ( logn )O(log⁡n)O(\log n) Czworoboki są wydajnymi wskaźnikami przestrzennymi. Mam łamigłówkę z implementacją wyszukiwania najbliższego sąsiada w skompresowanej strukturze quadtree, jak …

10 ds.algorithms ds.data-structures range-searching near-neighbors

6

Struktura danych dla zbiorów drzew.

Próby pozwalają na efektywne przechowywanie list elementów. Prefiksy są wspólne, więc zajmuje mało miejsca. Szukam podobnego sposobu skutecznego przechowywania drzew. Chciałbym móc sprawdzać członkostwo i dodawać elementy, wiedząc, czy dane drzewo jest poddrzewem niektórych przechowywanych drzew, czy też istnieje drzewo przechowywane, które jest poddrzewem danego drzewa. Zazwyczaj przechowywałem około 500 …

10 ds.data-structures tree model-checking

2

Ograniczenia kolekcji bez zamków?

David Rodríguez - dribeas napisał w komentarzu do StackOverflow, że „Nie wszystkie kolekcje można zaimplementować bez blokad”. Nie jestem pewien, czy to prawda, i tak nie mogę znaleźć dowodu. To stwierdzenie nie jest zbyt precyzyjne, ale pozwól mi spróbować sformułować je w nieco bardziej formalny sposób: Dla każdego typu kolekcji …

10 ds.data-structures pl.programming-languages dc.distributed-comp concurrency

2

Jak wybrać funkcjonalną strukturę danych słownika?

Przeczytałem trochę o następujących strukturach danych: Bagwell's Ideal Hash Próby Dynamiczne tabele skrótów Larsona Czerwono-czarne drzewa Drzewa Patricia ... i jestem pewien, że jest tam wielu innych. Niewiele widziałem na temat tego, do czego każdy jest bardziej odpowiedni, ani dlaczego wybieram siebie nawzajem. Oto kilka pytań w tym zakresie: O …

10 ds.data-structures functional-programming tree hash-function

2

Szybkie kodowanie wektorów zrównoważonych

Łatwo zauważyć, że dla dowolnego istnieje odwzorowanie 1-1 z {0,1} na {0,1} takie, że dla dowolnego wektor jest „zbalansowany”, tzn. ma równą liczbę 1 i 0. Czy jest możliwe zdefiniowanie takiego , aby przy danym można było skutecznie obliczyć ?F n n + O ( log n ) x F …

10 ds.algorithms ds.data-structures encoding

Pytania otagowane jako ds.data-structures