Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

2
Tasowanie tokenów na wykresie za pomocą lokalnych zamian
Niech będzie nieregularnym połączonym wykresem, którego stopień jest ograniczony. Załóżmy, że każdy węzeł zawiera unikalny token.G = ( V, E)G=(V,E)G= (V, E) Chcę równomiernie tasować tokeny między wykresami, używając tylko lokalnych zamian (tj. Wymiany tokenów między dwoma sąsiadującymi węzłami)? Czy znana jest dolna granica tego problemu? Jedyny pomysł, jaki miałem, …
1
Uogólnianie FFT
Czy dzielenie i podbijanie FFT może być automatycznie uogólnione na inne transformacje (z Transform, ćwierkanie itp.) Automatycznie? Czy istnieje algorytm, który przyjmuje opis transformacji (nie wiem, jakie informacje byłyby potrzebne) i może wygenerować szybką funkcję podobną do FFT?
1
Oceń obwód logiczny na partii podobnych danych wejściowych
Załóżmy, że mam obwód boolowski CCC która oblicza jakąś funkcję f:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}. Załóżmy, że obwód składa się z AND, OR i NOT bramek z wachlarzem i wachlowaniem co najwyżej 2. Pozwolić x∈{0,1}nx∈{0,1}nx \in \{0,1\}^nbyć danym wkładem. DanyCCC i xxx, Chcę ocenić CCC na nnn dane wejściowe, które różnią się …
1
Dlaczego komplementarność jest ważna?
Komplementarny luz (CS) jest powszechnie nauczany, gdy mówi się o dualności. Ustanawia ładny związek między pierwotnym a podwójnym ograniczeniem / zmiennymi z matematycznego punktu widzenia. Dwa główne powody stosowania CS (zgodnie z nauczaniem na kursach dla absolwentów i podręcznikach): Aby sprawdzić optymalność LP Aby pomóc rozwiązać problem podwójny Biorąc pod …
1
Ukryte stałe w złożoności algorytmów
W przypadku wielu problemów algorytm o największej złożoności asymptotycznej ma bardzo duży stały współczynnik, który jest ukryty przez dużą notację O. Dzieje się tak w przypadku mnożenia macierzy, mnożenia liczb całkowitych (w szczególności najnowszego algorytmu mnożenia liczb całkowitych O (n log n) Harveya i van der Hoevena), sieci sortowania o …
2
Kontrprzykład do algorytmów maksymalnego przepływu z irracjonalnymi wagami?
Wiadomo, że Ford-Fulkerson lub Edmonds-Karp z heurystyczną grubą rurą (dwa algorytmy dla maksymalnego przepływu) nie muszą się zatrzymywać, jeśli niektóre ciężary są nieracjonalne. W rzeczywistości mogą nawet zbierać się na niewłaściwej wartości! Jednak wszystkie przykłady, które mogłem znaleźć w literaturze [odnośniki poniżej oraz odnośniki w nich] wykorzystują tylko jedną wartość …
1
Zrozumienie wydajności solverów QFBV SMT
Solwery SMT, takie jak Z3 lub Boolector, wykorzystują złożony zestaw heurystyk do rozwiązywania problemów. Jednak bardzo utrudnia to przewidywanie wydajności takiego rozwiązania. Moje pytanie brzmi zatem: Pytanie Czy istnieje sposób na zrozumienie lub uzyskanie wglądu w wydajność solvera SMT dla konkretnego w teorii bitwektorów bez kwantyfikatora (QFBV)? Obejmuje to także …
5
Czy sieci neuronowe można wykorzystać do opracowania algorytmów?
Po coraz większych sukcesach sieci neuronowych w grach planszowych wydaje się, że następnym celem, który wyznaczyliśmy, może być coś bardziej przydatnego niż pokonanie ludzi w Starcraft. Dokładniej, zastanawiałem się, czy Czy sieci neuronowe można przeszkolić do rozwiązywania klasycznych problemów algorytmicznych? Mam na myśli, że na przykład sieć otrzyma wykres wejściowy …
1
Jak wybiera się pierścień wewnętrzny w algorytmie Schönhage – Strassen?
Próbowałem zaimplementować algorytm mnożenia liczb całkowitych Schönhage-Strassen, ale natknąłem się na przeszkodę w kroku rekurencyjnym. I mają wartość o bitów i Aby obliczyć . Początkowo myślałem, że pomysł takiego, że , podziel na kawałki każdy za pomocą bitów, zastosuj splot SSA podczas pracy modulo , pierścień z bitami pojemności na …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.