Teoretyczne informatyka ds.data-structures

2

Czy w jednej tablicy można zaimplementować trzy stosy z czasem push / pop O (1)?

Dwa stosy można skutecznie zaimplementować za pomocą jednej tablicy o stałym rozmiarze: stos nr 1 zaczyna się od lewego końca i rośnie w prawo, a stos nr 2 zaczyna się od prawego końca i rośnie w lewo. Czy to samo jest możliwe dla trzech stosów? Mówiąc dokładniej, czy możliwe jest …

9 ds.data-structures lower-bounds

2

Wybierz dwie liczby, które sumują się do , używając sublinearnego czasu zapytania

Oto problem najbliższego sąsiada. Biorąc pod uwagę liczby rzeczywiste (bardzo duże !), Plus cel rzeczywisty , znajdź i których SUMA jest najbliższe . Umożliwiamy rozsądne wstępne przetwarzanie / indeksowanie (do ), ale w czasie zapytania (dane ) wynik powinien zostać zwrócony bardzo szybko (np. czas).za1, ... ,zana1,…,ana_1, \ldots, a_nnnnpppzajaaia_izajotaja_jpppza1, ... …

9 ds.algorithms cg.comp-geom ds.data-structures

1

Heapsort: Heaps = ~ Quicksort: BSTs = ~ Mergesort: ___?

Proszę wybaczyć zwięzłość tytułu, mogłem poświęcić jasność na ołtarzu zwięzłości. Widać, że wstawienie elementów tablicy do binarnego drzewa wyszukiwania i ich ponowne odczytanie wymaga (przy wstawianiu) takich samych porównań, jak uruchomienie Quicksort na tej tablicy. Sekwencja osi przestawnych używanych przez Quicksort to sekwencja wstawek do drzewa wyszukiwania binarnego. Jest to …

9 ds.algorithms ds.data-structures sorting

2

Prawie uniwersalny skrót znaków w i sublinearnej przestrzeni

Oto dwie rodziny funkcji skrótu na ciągach :x⃗ =⟨x0x1x2…xm⟩x→=⟨x0x1x2…xm⟩\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle Dla prime i , dla \ in \ mathbb {Z} _p . Dietzfelbinger i in. pokazane w „Wielomianowe funkcje skrótu są niezawodne”, że \ forall x \ neq y, P_a (h ^ 1_a …

9 ds.data-structures randomness hash-function

2

Algorytm wyszukiwania podzbioru

Załóżmy, że mam listę XX\cal X podzbiorów {1,...,n}{1,...,n}\{1, ..., n\}. W razie potrzeby mogę wykonać wstępne przetwarzanie na tej liście. Po tym wstępnym przetwarzaniu otrzymuję kolejny zestawA⊆{1,...,n}A⊆{1,...,n}A \subseteq \{1, ..., n \}. Chcę zidentyfikować żadnych zestawów z .B∈XB∈XB \in \mathcal XB⊆AB⊆AB \subseteq A Oczywisty algorytm (bez wstępnego przetwarzania) wymaga czasu …

9 ds.algorithms ds.data-structures

2

Wydajne algorytmy przeszukiwania kolekcji drzew

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ż łańcuchy (przez ustaloną kolejność ich węzłów) nie będą …

9 graph-algorithms ds.data-structures tree graph-isomorphism string-search

2

Czy istnieje struktura danych umożliwiająca szybkie manipulowanie listami i zapytania dotyczące zamówień?

Mamy zestaw, LLL, list elementów z zestawu N= { 1 , 2 , 3 , . . . ,n}N={1,2,3,...,n}N = \{ 1, 2, 3, ..., n \}. Każdy element zNNN pojawia się na jednej liście w LLL. Szukam struktury danych, która może wykonać następujące aktualizacje: c o n c at(x,y)concat(x,y)concat(x, …

9 ds.algorithms graph-algorithms ds.data-structures

1

Decyzja, czy ciąg znaków zastępczych jest całkowicie dopasowany do innego ciągu znaków zastępczych w zestawie

Oto problem, który dręczy mnie od dłuższego czasu. Powiedzmy, że łańcuch jest sekwencją 1 i 0, a łańcuch wieloznaczny to sekwencja 1, 0 i? S. Wszystkie ciągi znaków i symbole wieloznaczne mają tę samą długość. Są to standardowe symbole wieloznaczne UNIX; 10 ?? 1 pasuje do 10011, 10111 itd. - …

9 ds.algorithms ds.data-structures approximation-algorithms string-matching string-search

2

Jaka jest optymalna struktura danych dla drzewa map.

Szukam struktury danych, która jest w zasadzie drzewem map, w których mapa w każdym węźle zawiera nowe elementy, a także elementy w mapie jego węzła nadrzędnego. Przez mapę rozumiem tutaj mapę programowania z kluczami i wartościami, taką jak mapa w STL lub dict w python. Na przykład może istnieć węzeł …

9 ds.data-structures tree hash-function

Pytania otagowane jako ds.data-structures