Teoretyczne informatyka implementation

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

4

Czy prowadzone są obecnie badania nad wdrożeniem ekstraktorów losowości?

Czy przeprowadzono badania nad implementacją konstrukcji ekstraktorów losowości? Wydaje się, że proofy ekstraktora wykorzystują Big-Oh, pozostawiając możliwość dużych, ukrytych stałych, czyniąc implementacje programowe potencjalnie nierealnymi. Trochę kontekstu: jestem zainteresowany wykorzystaniem ekstraktorów losowości jako szybkiego źródła (prawdopodobnie?) Liczb losowych do użycia w symulacjach Monte Carlo. My (grupa ETHZ Computational Physics) stronnicze …

20 reference-request cr.crypto-security randomness implementation application-of-theory

1

Dobra biblioteka do testowania, czy nieletni istnieje na wykresie?

Chciałbym wiedzieć, czy są jakieś bezpłatne biblioteki wykresów do testowania, czy na danym wykresie istnieje określony zestaw nieletnich?

18 graph-algorithms implementation graph-minor

5

Najlepsza książka na temat implementacji metody Simplex?

Interesuje mnie implementacja SM dla zadania LP, jednak słyszałem o możliwych pułapkach: książka Cormena mówi, że możliwe jest posiadanie danych wejściowych, które sprawią, że naiwna implementacja zachowa się w wykładniczym czasie. Słyszałem również, że naiwna implementacja może zapętlać dane. Czy istnieje książka / artykuł / źródło wyjaśniające niuanse praktycznego wdrażania …

14 ds.algorithms linear-programming software implementation simplex

3

Wdrożony kod do obliczania szerokości ścieżki (= numer wyszukiwania węzła, numer separacji wierzchołków, grubość przedziału)

Szukam implementacji algorytmu do obliczania szerokości ścieżki wykresu. Dobrze wiadomo, że obliczenie szerokości ścieżki jest równoważne z obliczeniem numeru wyszukiwania węzła, numeru separacji wierzchołków lub grubości przedziału wykresu. Algorytm nie musi być bardzo szybki; Chcę uruchomić go na wykresach o maksymalnie 20 wierzchołkach. Wymagam od algorytmu dokładnego obliczenia szerokości ścieżki, …

13 ds.algorithms reference-request graph-algorithms implementation

1

Implementacja Wilfa-Zeilbergera i powiązanych metod

Książka A = B autorstwa Petkovseka, Wilfa i Zeilbergera opisuje algorytmy do obliczania różnych sum dwumianów. AFAIK, algorytmy te są wciąż ulepszane przez różnych autorów. Czy wiesz, gdzie możemy znaleźć najbardziej aktualne implementacje tych algorytmów? A czy wiesz, czy istnieją implementacje w niektórych darmowych programach, takich jak Sage ?

12 ds.algorithms co.combinatorics implementation

2

Szybki rzadki produkt typu boolean z możliwym przetwarzaniem wstępnym

Jakie są najbardziej efektywne algorytmy mnożenia dwóch bardzo rzadkich macierzy boolowskich (powiedzmy, N = 200, a jest tylko około 100-200 niezerowych elementów)? W rzeczywistości mam tę zaletę, że kiedy mnożę A przez B, B są predefiniowane i mogę na nich dowolnie skomplikowane przetwarzanie wstępne. Wiem też, że wyniki produktów są …

12 ds.algorithms matrix-product sparse-matrix boolean-matrix implementation

1

Wdrożenie drzew partycji?

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

3

Implementacja surrealistycznych liczb do gier

Conway ma bardzo ładną konstrukcję o surrealistycznych liczbach. Są to „liczby”, które zawierają zarówno liczby rzeczywiste, jak i liczby porządkowe, są całkowicie uporządkowane i mają wszystkie właściwości pola (z wyjątkiem, że nie tworzą zbioru, ale klasę). Zobacz na przykład ten plik pdf lub Wikipedię w celu wprowadzenia. Można je jeszcze …

11 reference-request gt.game-theory implementation board-games combinatorial-game-theory

1

Potężne algorytmy, które są zbyt trudne do wdrożenia - jak się upewnić, że mają rację?

Odnoszę się tutaj do pytania: potężne algorytmy zbyt złożone, aby je zaimplementować . Jeśli algorytm jest potężny, ale zbyt skomplikowany, aby go wdrożyć, skąd możesz mieć pewność, że algorytm jest poprawny? Bez implementacji nie będzie można przetestować algorytmu w scenariuszu ze świata rzeczywistego, a tak złożony algorytm może zawierać błędy, …

9 ds.algorithms implementation

Pytania otagowane jako implementation