Teoretyczne informatyka ds.data-structures

6

Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki?

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 ich uogólnienie na monoidy) Istnieje również kilka interesujących …

563 reference-request big-list ds.data-structures functional-programming

30

Algorytmy z książki.

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 algorytm byłby kandydatem (kandydatami)? Jeśli to możliwe, proszę …

358 ds.algorithms soft-question ds.data-structures big-list

9

Potężne algorytmy zbyt skomplikowane do wdrożenia

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 bezużytecznym w praktyce. Szukam algorytmów, które mogłyby mieć praktyczną wartość, ale są …

67 ds.algorithms ds.data-structures big-list implementation

10

Jeden stos, dwie kolejki

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 powiedział, że zapomniał dowodu i …

59 ds.algorithms ds.data-structures open-problem time-complexity

13

Dla jakich algorytmów istnieje duża luka między analizą teoretyczną a rzeczywistością?

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 eksperymentalne sugerują silniejszą asymptozę, albo (b) istnieją algorytmy …

52 ds.algorithms big-list ds.data-structures

2

Jakie są nierozstrzygnięte pytania dotyczące czysto funkcjonalnych struktur danych?

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 funkcjonalne drzewa palcowe …

51 big-list ds.data-structures functional-programming

4

Czy istnieje funkcja skrótu dla zbioru liczb całkowitych (tj. Wielu), która ma dobre gwarancje teoretyczne?

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 o tych samych wielokrotnościach) zawsze powinny mieć skrót do tej …

36 ds.algorithms ds.data-structures hash-function

9

Dane do testowania algorytmów grafowych

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 znane.

36 ds.algorithms graph-theory ds.data-structures data-sets

6

Zestaw probabilistyczny bez fałszywych trafień?

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 fałszywych negatywów. Moja motywacja jest prosta: biorąc pod uwagę ogromny strumień …

35 ds.data-structures

8

Algorytmy wyższego rzędu

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 naprawdę nie robią z nią nic ciekawego …

35 ds.algorithms functional-programming ds.data-structures pl.programming-languages

3

Struktura danych oparta na porównaniu do znajdowania pozycji

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(log⁡n)O(\log n) Naprawdę uważam, że nie ma, dlatego mile widziany jest również dowód, że nie ma.

34 ds.data-structures sorting

4

Dlaczego ktoś miałby używać Octree zamiast drzewa KD?

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 ustalonych regularnych odstępach czasu, z tego, co zbieram. Trochę badań dotyczących niezależności wydaje …

32 ds.data-structures tree

6

Czy jest stabilna kupa?

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 (b, 2), Insert (c, 1), Insert (d, …

32 ds.data-structures

5

Uogólnienia wyszukiwania binarnego dla zestawów?

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 ważnymi przypadkami specjalnymi, …

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

2

Marzyłem o strukturze danych, czy ona istnieje?

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 o długości 2 ^ n (dla n> 0) jest tablicą …

27 ds.data-structures

Pytania otagowane jako ds.data-structures