Pytania otagowane jako ds.algorithms

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

5
Aplikacje kombinatoryki addytywnej w projektowaniu algorytmów
Czytam ankiety Trevisana i Lovetta dotyczące zastosowań dodatku kombinatorycznego w TCS. Większość tych aplikacji ma złożoność obliczeniową , np. Niższe granice. Zastanawiam się, czy kombinatoryka addytywna znalazła również zastosowania w projektowaniu algorytmów . Motywacja mojego pytania jest następująca: chociaż związek między kombinatoryką addytywną a złożonością wydaje się dość naturalny, jestem …
1
Optymalne losowe sortowanie porównania
Więc wszyscy znamy dolną granicę drzewa na podstawie najgorszego przypadku porównań wykonanych przez (deterministyczny) algorytm sortowania porównań. Nie dotyczy losowego sortowania porównań (jeśli mierzymy oczekiwane porównania dla danych wejściowych w najgorszym przypadku). Na przykład, dla , dolna granica deterministyczna wynosi pięć porównań, ale algorytm randomizowany (losowo permutuje dane wejściowe, a …
2
Jak nazywa się ten wariant problemu z ustawieniem pokrycia zestawu?
Wejściowego, to świat i rodzina podzbiorów , powiedzmy, . Zakładamy, że w podzbiory może obejmować , czyli .UUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Przyrostowe sekwencja Pokrycie jest ciągiem podzbiorów w , powiedzmy, , który spełniafaF{\cal F}ZA= { E1, E2), … , E| ZA|}A={E1,E2,…,E|A|}{\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\} 1) ,∀ E∈ A, …
3
Jak iterować po wektorach w kolejności prawdopodobieństwa na małej przestrzeni
Rozważmy wymiarowy wektor gdzie . Dla każdego wiemy i załóżmy, że są niezależne. Wykorzystując te prawdopodobieństwa, czy istnieje skuteczny sposób na iterację binarnych wektorów wymiarowych w kolejności od najbardziej prawdopodobnego do najmniej prawdopodobnego (z dowolnymi wyborami wiązań) z wykorzystaniem przestrzeni podliniowej w wielkości wyjściowej? v v i ∈ { 0 …
1
Minimalizowanie resztkowych automatów skończonych
Automaty szczątkowego stanu skończonego (RFSA, zdefiniowane w [DLT02]) to NFA, które mają kilka fajnych cech wspólnych z DFA. W szczególności zawsze istnieje kanoniczny minimalny rozmiar RFSA dla każdego zwykłego języka, a język rozpoznawany przez każdy stan w RFSA jest resztkowy, podobnie jak w DFA. Jednakże, podczas gdy minimalne stany DFA …
3
Podgraf zawierający wszystkie węzły i krawędzie, które są częścią prostych ścieżek st o ograniczonej długości na niekierowanym wykresie
Całkiem podobne do mojego wcześniejszego pytania . Tym razem jednak wykres nie jest przekierowany. Dany Nieukierunkowane wykres solGG bez wielu krawędzie lub pętli Źródło wierzchołek sss , Docelowy wierzchołek ttt , Maksymalna długość ścieżki lll , Szukam sol′G′G' - podgraf solGG który zawiera dowolny wierzchołek i dowolną krawędź w solGG …
2
Mały wykres z odstępem między liczbą chromatyczną a liczbą chromatyczną wektorową?
Szukam małego wykresu GGG którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, χv(G)&lt;χ(G)χv(G)&lt;χ(G)\chi_v(G)<\chi(G) . ( GGG zawiera wektor chromatycznej liczba qqq , jeśli istnieje zadanie x:V→Rdx:V→Rdx\colon V \rightarrow \mathbf R^d , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, ⟨x(v),x(w)⟩≤−1/(q−1)⟨x(v),x(w)⟩≤−1/(q−1)\langle x(v), x(w)\rangle \leq -1/(q-1) …
1
Stabilność numeryczna metody Simplex
Algorytm simpleksowy jest często traktowany albo w ramach rzeczywistej arytmetyki, albo w świecie dyskretnym z dokładnymi obliczeniami. Wydaje się jednak, że jest najczęściej wdrażany za pomocą arytmetyki zmiennoprzecinkowej. Prowadzi to do pytania, czy algorytm simpleks należy traktować jako algorytm numeryczny, w szczególności w jaki sposób błędy zaokrąglenia wpływają na obliczenia. …
1
Minimalne elementy monotonicznego predykatu nad zestawem mocy
Rozważ monotoniczny predykat PPP nad zestawem mocy 2|n|2|n|2^{|n|}(uporządkowane przez włączenie). Przez „monotoniczny” rozumiem: ∀x,y∈2|n|∀x,y∈2|n|\forall x, y \in 2^{|n|}tak, że x ⊂ yx⊂yx \subset y , jeśli P.( x )P(x)P(x) to P.( y)P(y)P(y) . Szukam algorytmu, aby znaleźć wszystkie minimalne elementy P.PP , tj. x ∈ 2| n |x∈2|n|x \in 2^{|n|}takie, …
1
Pytanie o liniowe rozszerzenia zamówień częściowych
Jeśli otrzymujesz zbiór zamówień częściowych, sortowanie topologiczne powie ci, czy istnieje rozszerzenie zbioru do zamówienia całkowitego (w tym przypadku rozszerzenie jest zamówieniem całkowitym zgodnym z każdym z zamówień częściowych). Natknąłem się na odmianę: Naprawić zestaw . Dostajesz sekwencje σ 1 , … σ k elementów narysowanych z V bez powtórzeń …
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 ?
3
Sortowanie sekwencji „tonicznych”
Mam nadzieję, że ktoś wie o tym, więc nie muszę czytać literatury ... Rozważ ciąg liczb . Pomyśl o sekwencji jako interwałach . Oczywiście, oryginalna sekwencja jest bitoniczna, jeśli jakikolwiek punkt na prawdziwej linii dźgnie co najwyżej 2 interwały. Będziemy odnosić się do sekwencji, w której punkt dźgnie w większości …
2
Podziel tekst równomiernie na określoną liczbę wierszy
Istnieje liniowy algorytm czasowy umożliwiający równomierne dzielenie tekstu na linie o maksymalnej szerokości. Wykorzystuje SMAWK (lub Knuth &amp; Plass), a „równomiernie” oznacza: http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness Czy istnieje algorytm lub wklęsła funkcja kosztu dla algorytmu, powyżej której wziąłby pod uwagę liczbę wierszy, w których chciałbym rozbić tekst, zamiast maksymalnej szerokości linii? Również w …
2
Przybliżone zabarwienie wykresu z obiecaną górną granicą na maksymalnym niezależnym zestawie
W mojej pracy powstaje następujący problem: Czy istnieje znany algorytm, który aproksymuje liczbę chromatyczną wykresu bez niezależnego zestawu rzędów 65? (Więc alfa (G) &lt;= 64 jest znane, a | V | / 64 jest trywialną dolną, | V | trywialną górną granicą. Ale czy istnieją lepiej udowodnione przybliżenia w tych …
2
Złożoność testowania członkostwa dla skończonych grup abelowych
Rozważ następujący problem testowania członkostwa w podgrupie abelian . Wejścia: Skończona grupa abelowa G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} o dowolnie dużych didid_i . Wytwarzające osadzone {h1,…,hn}{h1,…,hn}\lbrace h_1,\ldots,h_n\rbrace podgrupy H⊂GH⊂GH\subset G . Element b∈Gb∈Gb\in G . Wyjście: „tak”, jeżeli b∈Hb∈Hb\in H i „nie” w innym miejscu. Pytanie: Czy ten problem można skutecznie rozwiązać na klasycznym …
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.