Właściwości i zastosowania struktur danych, takie jak dolne granice przestrzeni lub złożoność czasowa wstawiania i usuwania obiektów.
Od czasu książki Chrisa Okasakiego z 1998 r. „Czysto funkcjonalne struktury danych”, nie widziałem zbyt wielu nowych ekscytujących czysto funkcjonalnych struktur danych; Mogę wymienić tylko kilka: IntMap (również wynaleziony przez Okasaki w 1998 r., Ale nieobecny w tej książce) Drzewa palcowe (i...
Paul Erdos mówił o „Księdze”, w której Bóg przechowuje najbardziej elegancki dowód każdego twierdzenia matematycznego. To nawet zainspirowało książkę (która, jak sądzę, jest teraz w czwartym wydaniu): Dowody z książki . Gdyby Bóg miał podobną książkę na temat algorytmów, jaki według ciebie...
Jakie są algorytmy legalnej użyteczności, które są po prostu zbyt skomplikowane, aby je zaimplementować? Wyjaśnię: nie szukam algorytmów takich jak obecny asymptotyczny algorytm optymalnego mnożenia macierzy (Coppersmith-Winograd), który jest rozsądny do wdrożenia, ale ma stałą, która czyni go...
tło Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i...
Istnieją dwa sposoby analizy wydajności algorytmu nałożyć asymptotyczną górną granicę czasu działania, oraz aby go uruchomić i zebrać dane eksperymentalne. Zastanawiam się, czy są znane przypadki, w których istnieje znaczna różnica między (1) a (2). Rozumiem przez to, że albo (a) dane...
To pytanie jest inspirowane innym pytaniem o to, co nowego w PFDS od publikacji książki Okasaki w 1998 roku . Zacznę od dwóch pytań, które mam: Czy istnieje czysto funkcjonalna struktura danych, która zbliża się do prędkości tabel mieszania? Prób jeszcze tam nie ma. Czy istnieją czysto...
Szukam źródła ogromnych zestawów danych do przetestowania implementacji algorytmu grafowego. Proszę również podać informacje o typie / rozkładzie (np. Skierowane / nieukierowane, proste / nie proste, ważone / nieważone) wykresów w źródle, jeśli są one
Ciekawe, czy istnieje sposób przechowywania skrótu zbioru liczb całkowitych, który ma następujące właściwości, najlepiej: Wykorzystuje spację O (1) Można go zaktualizować, aby odzwierciedlał wstawianie lub usuwanie w czasie O (1) Dwie identyczne kolekcje (tj. Kolekcje, które mają te same elementy...
Większość dobrze znanych algorytmów jest pierwszego rzędu, w tym sensie, że ich dane wejściowe i wyjściowe są danymi „prostymi”. Niektóre są drugiego rzędu w trywialny sposób, na przykład sortowanie, tablice skrótów lub funkcje mapowania i składania: są one parametryzowane przez funkcję, ale tak...
Tak więc filtry Bloom są całkiem fajne - są zestawami, które obsługują sprawdzanie członkostwa bez fałszywych negatywów, ale z niewielką szansą na fałszywy pozytyw. Ostatnio jednak chciałem mieć „filtr Blooma”, który gwarantuje coś przeciwnego: żadnych fałszywych alarmów, ale potencjalnie...
Czy istnieje struktura danych, która pobiera nieuporządkowaną tablicę elementów, wykonuje wstępne przetwarzanie w i odpowiada na zapytania: czy na liście jest jakiś element , każde zapytanie w najgorszym czasie ?nnnO(n)O(n)O(n)xxxO(logn)O(logn)O(\log n) Naprawdę uważam, że nie ma, dlatego mile...
Mam pewne doświadczenie w obliczeniach naukowych i intensywnie korzystałem z drzewek kd do aplikacji BSP (partycjonowanie przestrzeni binarnej). Niedawno zapoznałem się raczej z oktatami, podobną strukturą danych do partycjonowania trójwymiarowych przestrzeni euklidesowych, ale taką, która działa w...
Czy istnieje struktura danych kolejki priorytetowej, która obsługuje następujące operacje? Wstaw (x, p) : dodaj nowy rekord x z priorytetem p StableExtractMin () : Zwraca i usuwa rekord z minimalnym priorytetem, zrywając powiązania według kolejności wstawiania . Zatem po Insert (a, 1), Insert...
Załóżmy, że mam poset „S” i monotoniczny predykat „P” na S. Chcę znaleźć jeden lub wszystkie maksymalne elementy S spełniające P. EDIT : Jestem zainteresowany minimalizując liczbę ocen P . Jakie algorytmy istnieją dla tego problemu i jakich właściwości i dodatkowych operacji wymagają na S? Co z...
Nie udało mi się znaleźć tej struktury danych, ale nie jestem ekspertem w tej dziedzinie. Struktura implementuje zestaw i jest w zasadzie szeregiem porównywalnych elementów z niezmiennikiem. Niezmiennikiem jest to (zdefiniowane rekurencyjnie): Tablica o długości 1 jest tablicą scalającą. Tablica...
Muszę obliczyć medianę biegu: Dane wejściowe: , , wektor .nnnkkk(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Wyjście: wektor (y1,y2,…,yn−k+1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1}) , gdzie yiyiy_i jest medianą (xi,xi+1,…,xi+k−1)(xi,xi+1,…,xi+k−1)(x_i, x_{i+1}, \dotsc, x_{i+k-1})...
Czy istnieje naturalny równoległy analog do czerwono-czarnych drzew o podobnych lub nawet niezbyt gorszych właściwościach do aktualizacji, przy jednoczesnym zapewnieniu odpowiedniej wydajności pracy? Mówiąc bardziej ogólnie, co możemy zrobić dla wyszukiwania równoległego z aktualizacjami?...
Szukam książki o zaawansowanych strukturach danych, która wykracza poza to, co jest zawarte w standardowych podręcznikach, takich jak Cormen, Leiserson, Rivest i „Wprowadzenie do algorytmów” Steina. Książka, która może być wykorzystana do nauczania kursów na poziomie zaawansowanym na temat...
Co wiadomo na temat struktur danych, które mogą utrzymywać sekwencję elementów podlegających następującym dwóm operacjom? Naciśnij (x): dodaj x na końcu sekwencji i zwróć identyfikator jej pozycji w sekwencji Wyodrębnij (S): biorąc pod uwagę nieuporządkowany zestaw identyfikatorów, usuń elementy...
x∈Rnx∈Rnx \in \mathbb{R}^nA x A R n R ≪ n A k∥x∥0<k‖x‖0<k\|x\|_0 < kAxAxAxAAARRRnnnR≪nR≪nR \ll nAAAkkk- rzadkie z tak małym jak . Mogę nie mieć najlepiej znanych parametrów, ale to jest ogólny pomysł.R O ( k n o ( 1 ) )xxxRRRO(kno(1))O(kno(1))O(k n^{o(1)}) Moje pytanie brzmi: czy istnieją...