Teoretyczne informatyka ds.algorithms

1

Czy jest coś znanego na temat następującego problemu? Czy to w ogóle ma sens? Jak to jest nazywane? Czy jest to banalnie równoważne z jakimś innym problemem? Jaka jest złożoność czasu? Biorąc pod uwagę nieukierowany (ogólny / płaski / ograniczony / itd.) Wykres G = (V, E), znajdź maksymalny podzbiór …

14 ds.algorithms graph-theory

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

2

Istnienie płaskiego zabezpieczenia odległości?

Niech G będzie n-węzłem niekierowanym grafem, a niech T będzie podzbiorem węzłów V (G) zwanym zaciskami . Zabezpieczenie odległości (G, T) jest wykresem H spełniającym tę właściwość reH.( u , v ) = dsol( u , v )reH.(u,v)=resol(u,v)d_H(u,v) = d_G(u,v) dla wszystkich węzłów u, v w T. (Należy zauważyć, że …

14 ds.algorithms reference-request graph-algorithms planar-graphs

2

Kompromis czasoprzestrzenny i najlepszy algorytm

Rozważmy język taki jak:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) i tak L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Innymi słowy, najszybsza maszyna oblicza L w czasie O ( f ( n ) ), a najbardziej wydajna pod względem przestrzeni maszyna M ' oblicza L , używając przestrzeni O ( g ( n …

14 cc.complexity-theory ds.algorithms open-problem space-time-tradeoff

2

Algorytm sortowania par liczb

Zadałem już to pytanie przy przepełnieniu stosu , ale może lepiej pasuje do tej witryny. Problemem jest: Mam N par liczb całkowitych bez znaku. Muszę je posortować. Wektor końcowy par należy posortować nie malejąco według pierwszej liczby w każdej parze i nieskończenie według drugiej liczby w każdej parze. Każda para …

14 ds.algorithms sorting

2

Uzasadnienie metody węgierskiej (Kuhn-Munkres)

Napisałem implementację algorytmu Kuhna-Munkresa dla problemu dwustronnego idealnego dopasowania minimalnej wagi w oparciu o notatki z wykładu, które znalazłem tu i tam w Internecie. Działa naprawdę dobrze, nawet na tysiącach wierzchołków. I zgadzam się, że teoria jest naprawdę piękna. A jednak wciąż zastanawiam się, dlaczego musiałem tak bardzo się starać. …

14 ds.algorithms graph-theory linear-programming simplex

2

Optymalny algorytm znajdowania obwodu rzadkiego wykresu?

Zastanawiam się, jak znaleźć obwód rzadkiego niekierowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy w , to znajdę obwód …

14 ds.algorithms graph-theory open-problem

2

Liczba minut wykresu bez użycia algorytmu Kargera

Wiemy, że algorytm wycinania Kargera można wykorzystać do udowodnienia (w niekonstruktywny sposób), że maksymalna liczba możliwych skrótów może mieć wykres ( n2))(n2))n \choose 2 . Zastanawiałem się, czy moglibyśmy w jakiś sposób udowodnić tę tożsamość, podając bijectywny (raczej iniekcyjny) dowód z zestawu skrótów do innego zestawu liczności ( n2))(n2))n \choose …

14 ds.algorithms graph-theory co.combinatorics graph-algorithms max-flow-min-cut

1

Dowody poprawności klasycznych Paxos i Fast Paxos

Czytam artykuł „Fast Paxos” autorstwa Leslie Lamport i utknąłem z dowodami poprawności zarówno klasycznych Paxos, jak i Fast Paxos. Aby zachować spójność, wartość wybrana przez koordynatora w fazie 2 a w rundzie i powinna spełniaćvvv2 a2a2ajaii Dla dowolnej rundy j < i żadna wartość inna niż v nie była lub …

13 ds.algorithms dc.distributed-comp proofs

1

Czy suma podzbioru DAG jest przybliżona?

Dana jest skierowany acykliczny wykres o numer przypisany do każdego wierzchołka ( g : V → N ), i docelową liczbą T ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} Problem sumy podzbioru DAG (może występować pod inną nazwą, odniesienie będzie wielki) pyta, czy istnieją wierzchołki , tak że Σ V I g …

13 ds.algorithms graph-theory graph-algorithms approximation-algorithms subset-sum

2

Edytuj odległość za pomocą operacji przesuwania

Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne? Definicje: Chciałbym znaleźć minimalną odległość edycji, gdzie dozwolone operacje to: „tanie” operacje: dodaj / zmień / …

13 ds.algorithms reference-request parameterized-complexity string-matching edit-distance

1

Dokładne algorytmy dla niewypukłego programowania kwadratowego

To pytanie dotyczy kwadratowych problemów programistycznych z ograniczeniami pudełkowymi (box-QP), tj. Problemów optymalizacyjnych formularza minimalizuj zastrzeżeniem x ∈ [ 0 , 1 ] n .fa( x ) = xT.A x + cT.xf(x)=xTAx+cTxf(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}x ∈[0,1 ]nx∈[0,1]n\mathbf{x} \in [0,1]^n Gdyby było pozytywnie półokreślone, wtedy wszystko byłoby …

13 ds.algorithms optimization exp-time-algorithms

1

Pojemność jednoznacznie rozwiązanej układanki (USP)

W swoim kluczowym artykule Teoretyczne algorytmy grupowania macierzy Cohn, Kleinberg, Szegedy i Umans przedstawiają koncepcję unikatowej układanki (zdefiniowanej poniżej) i zdolności USP. Twierdzą oni, że Coppersmith i Winograd, w ich własnym papierze przełomowy Mnożenie macierzy poprzez ciąg arytmetyczny , „pośrednio” udowodnić, że zdolność USP jest 3/22/33/22/33/2^{2/3} . Twierdzenie to zostało …

13 ds.algorithms co.combinatorics algebraic-complexity matrix-product

2

Wzmocnienia submodularności

Ustawiona funkcja jest monotoniczna podmodularna, jeśli dla wszystkich A , B , f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) .faffA , BA,BA,Bfa( A ) + f( B ) ≥ f( A ∪ B ) …

13 ds.algorithms approximation-algorithms submodularity

4

Pochodzenie terminów „wydajne” i „wykonalne” obliczenia / algorytmy

Chciałbym wiedzieć o historii tych dwóch terminów: „ skuteczny ”, „ wykonalny ”. Kto zastosował je po raz pierwszy w obliczeniach / algorytmach? (w nowoczesnym znaczeniu tych terminów, tj. XX wieku). Jak stały się głównym nurtem? Jak te dwa terminy zaczęły być używane jako synonimy? Wiem, że Cobham użył terminu …

13 cc.complexity-theory ds.algorithms ho.history-overview

Pytania otagowane jako ds.algorithms