Pytania otagowane jako ds.algorithms

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

8
Inne rodzaje analizy czasu pracy oprócz najgorszego przypadku, średniego przypadku itp.?
Oto kilka sposobów analizy czasu działania algorytmu: 1) Analiza najgorszego przypadku: czas działania w najgorszym przypadku. 2) Analiza średnich przypadków: oczekiwany czas działania w przypadkowej instancji. 3) Amortyzowana analiza: średni czas działania w najgorszej sekwencji przypadków. 4) Wygładzona analiza: oczekiwany czas działania w najgorszym przypadkowo zaburzonym wystąpieniu. 5) Analiza przypadków …
9
Redukcje z książki.
Jest to zgodne z „ Algorytmami z książki ”. Chociaż redukcje są również algorytmami, pomyślałem, że wątpliwe jest, aby pomyśleć o redukcji w odpowiedzi na pytanie o algorytmy z książki. Stąd osobne zapytanie! Wszelkie redukcje są mile widziane. Zacznę od bardzo prostej redukcji od osłony wierzchołków do multikutów na gwiazdach. …
7
Dlaczego CNF jest używany do SAT, a nie DNF?
Nie do końca rozumiem, dlaczego prawie wszystkie solwery SAT używają CNF zamiast DNF. Wydaje mi się, że rozwiązywanie SAT jest łatwiejsze przy użyciu DNF. W końcu musisz tylko przejrzeć zestaw implantów i sprawdzić, czy jeden z nich nie zawiera zarówno zmiennej, jak i jej negacji. W przypadku CNF nie ma …
6
Analogi wykrywania skompresowanego
x∈Rnx∈Rnx \in \mathbb{R}^nA x A R n R ≪ n A k∥x∥0&lt;k‖x‖0&lt;k\|x\|_0 < kAxAxAxAAARRRnnnR≪nR≪nR \ll nAAAkkk- rzadkie z tak małym jak . Mogę nie mieć najlepiej znanych parametrów, ale to jest ogólny pomysł.R O ( k n o ( 1 ) )xxxRRRO(kno(1))O(kno(1))O(k n^{o(1)}) Moje pytanie brzmi: czy istnieją podobne zjawiska …
3
Uogólniając „sztuczkę środkową” do wyższych wymiarów?
W przypadku algorytmów losowych przyjmujących rzeczywiste wartości „sztuczka medianowa” jest prostym sposobem zmniejszenia prawdopodobieństwa niepowodzenia do dowolnego progu , kosztem tylko wielokrotności narzut. Mianowicie, jeśli wyjście mieści się w „dobrym zakresie” z prawdopodobieństwem (co najmniej) , to uruchamianie niezależnych kopii i przyjmując medianę swoich wyników spowoduje, że wartość spadnie do …
4
Problemy, które w praktyce można rozwiązać w sposób sprzeczny z intuicją?
Niedawno przeszedłem przez bolesną zabawę polegającą na nieformalnym wyjaśnianiu koncepcji złożoności obliczeniowej młodemu utalentowanemu samoukiem, programistowi, który nigdy wcześniej nie odbył formalnego kursu algorytmów ani złożoności. Nic dziwnego, że wiele pojęć początkowo wydawało się dziwnych, ale miało sens w niektórych przykładach (PTIME, trudność, niezliczalność) , podczas gdy inne wydają się …
1
Czy P jest równe przecięciu wszystkich wielobiegunowych klas czasowych?
Nazwijmy funkcję wielobiegunową, jeśli dla każdego c&gt; 0 .f(n)f(n)f(n) c &gt; 0limn→∞nc/f(n)=0limn→∞nc/f(n)=0\lim_{n\rightarrow\infty} n^c/f(n)=0c&gt;0c&gt;0c>0 Oczywiste jest, że dla każdego języka L∈PL∈PL\in {\mathsf P} utrzymuje, że L∈DTIME(f(n))L∈DTIME(f(n))L\in {\mathsf {DTIME}}(f(n)) dla każdego superminomalnego ograniczenia czasowego f(n)f(n)f(n) . Zastanawiam się, czy odwrotność tego stwierdzenia jest również prawdą? To znaczy, jeśli znamy L∈DTIME(f(n))L∈DTIME(f(n))L\in {\mathsf {DTIME}}(f(n)) …
1
Jak blisko liniowego mnożenia, dodawania i porównywania (na liczbach całkowitych)?
Nawiązując do artykułu KW Regana „Połącz gwiazdy” , na końcu wspomina, że ​​wciąż otwartym problemem jest znalezienie reprezentacji liczb całkowitych, tak że operacje dodawania, mnożenia i porównywania można obliczać w czasie liniowym: Czy istnieje reprezentacja liczb całkowitych, aby dodawanie, mnożenie i porównywanie były wykonalne w czasie liniowym? Zasadniczo, czy istnieje …
2
Odróżnienie elementu w czasie O (n)?
Wszyscy wiemy, że odróżnienia elementów w modelu opartym na porównaniu nie można zrobić w czasie . Jednak na słownej pamięci RAM można osiągnąć lepiej.o ( n logn )o(nlog⁡n)o(n\log n) Oczywiście, jeśli przyjmie się istnienie idealnej funkcji skrótu, którą można obliczyć w czasie liniowym, otrzymamy liniowy algorytm czasu dla odróżnienia elementu: …
1
Przybliżony 1d TSP z porównaniami liniowymi?
Jednowymiarowy problem ścieżki sprzedawcy podróży jest oczywiście tym samym, co sortowanie, a zatem można go rozwiązać dokładnie przez porównanie w czasie , ale sformułowano go w taki sposób, aby przybliżenie, a także dokładne rozwiązanie ma sens. W modelu obliczeń, w którym dane wejściowe są liczbami rzeczywistymi i możliwe jest zaokrąglanie …
5
Teoretyczne zastosowania algorytmów aproksymacyjnych
Ostatnio zacząłem szukać algorytmów aproksymacyjnych dla problemów trudnych dla NP i zastanawiałem się nad teoretycznymi przyczynami ich badania. (To pytanie nie ma być zapalne - jestem po prostu ciekawy). Z badań algorytmów aproksymacyjnych wynikła pewna naprawdę piękna teoria - związek między twierdzeniem PCP a twardością aproksymacji, hipoteza UGC, algorytm aproksymacji …
3
Przybliżona suma posortowanej listy
Ostatnio pracowałem nad problemem obliczania przybliżonej sumy listy posortowanych liczb nieujemnych. Dla każdego ustalonego opracowano schemat aproksymacji czasu , który daje przybliżenie dla sumy. Artykuł opublikowano na stronie http://arxiv.org/abs/1112.0520 , który nie został jeszcze sfinalizowany.O ( log n ) ( 1 + ϵ )ϵ&gt;0ϵ&gt;0\epsilon>0O(logn)O(log⁡n)O(\log n)(1+ϵ)(1+ϵ)(1+\epsilon) Szukałem istniejących prac dotyczących tego …
2
Skuteczne znajdowanie 5-cykli na rzadkim wykresie.
(crossposted z MathOverflow) Cześć, Czytałem ten wątek: /mathpro/16393/finding-a-cycle-of-fixed-length Chcę znaleźć 5-cykl na wykresie. Tak naprawdę to, czego naprawdę chcę, to najkrótszy nieparzysty cykl o długości co najmniej 5, ale może to trochę poza tym. Dla moich celów, traktuję i to samo w analizie złożoności. nmmmnnn Czy w takim przypadku możemy …
3
Jak szybko możemy rozwiązać całkowicie nieimodularny program liniowy liczb całkowitych?
(Jest to kontynuacja tego pytania i odpowiedzi ). Mam następujący całkowicie nieimodularny (TU) całkowity program liniowy (ILP). Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych x i j jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całkowite:ℓ , m , n1, n2), …
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.