Pytania otagowane jako ds.algorithms

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

2
Znalezienie największego zestawu punktów o ograniczonej średnicy
Biorąc pod uwagę punkty w i odległość znajduję największy podzbiór tych punktów, tak że odległość euklidesowa nie jest większa niż .p1, … , Snp1,…,pnp_1,\ldots,p_nRreRre\mathbb{R}^{d}llllll Jaka jest złożoność tego problemu? Na wykresie nad punktami, które mają krawędź, ilekroć odległość dwóch punktów wynosi co najwyżej , problem jest równoznaczny ze znalezieniem maksymalnej …
1
Złożoność decydowania, czy rodzina jest rodziną Sperner
Otrzymujemy rodzinę składającą się z m podzbiorów {1, ..., n}. Czy można znaleźć nietrywialną dolną granicę złożoności decydowania, czy F jest rodziną Spernerów? Trywialna dolna granica to O ( n m ) i mocno podejrzewam, że nie jest ciasna.FF\mathcal{F}mmmFF\mathcal{F}O(nm)O(nm)O(n m) Przypomnij sobie, że zestaw jest rodziną Spernerów, jeśli dla X …
1
Czy możemy zdecydować, czy stały ma unikalny termin?
Załóżmy, że otrzymujemy macierz n przez n, M, z wpisami liczb całkowitych. Czy możemy zdecydować w P, czy istnieje permutacjaσσ\sigma taka, że ​​dla wszystkich permutacji mamy ?π≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Õ Mi π( i )ΠM.jaσ(ja)≠ΠM.jaπ(ja)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Uwagi Oczywiście można wymienić produkt na sumę, problem pozostaje ten …
2
Twarde instancje do testowania izomorfizmu grafów
Czy przypadek bardzo regularnych grafów jest najtrudniejszy do testowania GI? gdzie „najtrudniejszy” jest używany w pewnym sensie „zdrowego rozsądku” lub „średnio”, że tak powiem. Wolfram MathWorld wspomina o niektórych „patologicznie trudnych grafach”. Czym oni są? Mój przykładowy zestaw 25 par wykresów: http://funkybee.narod.ru/graphs.htm Testowałem wiele innych, ale wszystkie tego samego rodzaju …
1
2FA złożoność stanu k-Clique?
W prostej formie: Można dwukierunkowa skończony automat rozpoznaje vvv wykresy -Vertex które zawierają trójkąt z o(v3)o(v3)o(v^3) stany? Detale Zainteresowania są tu vvv wykresy -Vertex kodowane przy użyciu sekwencji krawędzi, każda krawędź jest para różnych wierzchołki {0,1,…,v−1}{0,1,…,v−1}\{0,1,\dots,v-1\} . Załóżmy, że (Mv)(Mv)(M_v) jest ciągiem dwukierunkowy automaty skończone (deterministyczny lub niedeterministyczny), tak że …
2
Co wiadomo o tym wariancie TSP?
To pytanie zostało wcześniej opublikowane w Computer Science Stack Exchange tutaj . Wyobraź sobie, że jesteś odnoszącym sukcesy podróżnym sprzedawcą z klientami w całym kraju. Aby przyspieszyć wysyłkę, opracowałeś flotę dronów jednorazowego użytku o efektywnym zasięgu 50 kilometrów. Dzięki tej innowacji zamiast podróżować do każdego miasta w celu dostarczenia towarów, …
1
Równoważność kontroli wykonalności i optymalizacji dla systemów liniowych
Jednym ze sposobów wykazania, że ​​sprawdzenie wykonalności liniowego układu nierówności jest tak trudne, jak programowanie liniowe, jest zmniejszenie za pomocą metody elipsoidalnej. Jeszcze łatwiejszym sposobem jest odgadnięcie optymalnego rozwiązania i wprowadzenie go jako ograniczenia poprzez wyszukiwanie binarne. Obie te redukcje są wielomianowe, ale nie silnie wielomianowe (tzn. Zależą od liczby …
4
Najgorsza liczba pytań potrzebna do nauczenia się monotonicznego orzeczenia nad zestawem
Rozważmy skończoną posetę ponad elementów, a nieznany monotoniczny predykat nad (tj. Dla dowolnego , , jeśli i to ) . Mogę ocenić , podając jeden węzeł i sprawdzając, czy utrzymuje, czy nie. Moim celem jest określenie dokładnie zestawu węzłów tak, że P (x) utrzymuje, przy użyciu jak najmniejszej liczby ocen …
3
Algorytm losowego ustawiania czasu w linijce w czasie
Czy istnieje algorytm tasowania karabinu liniowego w czasie? Jest to algorytm, który niektóre szczególnie sprawne ręce są w stanie wykonać: równomierne dzielenie tablicy wejściowej o równej wielkości, a następnie przeplatanie elementów dwóch połówek. Mathworld ma krótką stronę na temat losowania karabinów . W szczególności interesuje mnie odmiana przetasowania, która przekształca …
5
Przykłady pedanterii w TCS
Larry Wasserman ma niedawny post, w którym mówi o „policji p-value”. Robi interesujący punkt (wszystkie moje podkreślenia) (przesłankę kursywą, którą dodałem, a jego odpowiedź poniżej): Najczęstszą skargą jest to, że fizycy i dziennikarze nieprawidłowo wyjaśniają znaczenie wartości p. Na przykład, jeśli wartość p wynosi 0,000001, zobaczymy takie stwierdzenia, jak: „istnieje …
2
Godne uwagi przykłady idei pierwiastka kwadratowego w analizie złożoności
Istnieje wiele algorytmów i struktur danych, które wykorzystują ideę, że otrzymuje minimalną wartość przy k = \ sqrt n . Typowe przykłady to k = √max{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n algorytm gigantycznego kroku dziecka do obliczania logarytmu dyskretnego w O(n−−√)O(n)O(\sqrt n) , statyczne zliczanie zakresu ortogonalnego 2D w czasie O(n−−√)O(n)O(\sqrt n) …
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.