W „ Poradzie dla początkującego studenta ” Manuela Bluma : LEONID LEVIN wierzy, jak to robię, niezależnie od odpowiedzi na P = NP? problem, to nie będzie tak, jak myślisz, że powinno być. Podał też wspaniałe przykłady. Po pierwsze, podał FACTORING ALGORITHM, który jest optymalnie optymalny, aż...
Szukam implementacji algorytmu do obliczania szerokości ścieżki wykresu. Dobrze wiadomo, że obliczenie szerokości ścieżki jest równoważne z obliczeniem numeru wyszukiwania węzła, numeru separacji wierzchołków lub grubości przedziału wykresu. Algorytm nie musi być bardzo szybki; Chcę uruchomić go na...
Popularny algorytm DEFLATE wykorzystuje kodowanie Huffmana na Lempel-Ziv. Ogólnie rzecz biorąc, jeśli mamy losowe źródło danych (= 1 bit entropii / bit), żadne kodowanie, w tym Huffman, prawdopodobnie nie skompresuje go średnio. Gdyby Lempel-Ziv był „idealny” (do którego zbliża się większość klas...
Rozgałęzienie i powiązanie to skuteczna heurystyka dla problemów wyszukiwania, a Wikipedia wymienia wiele trudnych problemów, w których zastosowano rozgałęzienie i powiązanie. Jednak nie udało mi się znaleźć referencji sugerujących, że jest to więcej niż „jedna metoda” rozwiązania tych...
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...
Rozdział 1 książki Metoda probabilistyczna autorstwa Alona i Spencera wymienia następujący problem: Biorąc pod uwagę wykres , zdecyduj, czy jego łączność brzegowa wynosi co najmniej czy nie.GGGn/2n/2n/2 Autor wspomina o istnieniu przez Matula algorytmu i ulepsza go do...
Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie pomocą procesorów O ( m + n ) .O(logn)O(logn)O({\log}n)O(m+n)O(m+n)O(m+n) Jaki jest najbardziej znany algorytm równoległy dla łączności st w ukierunkowanych grafach płaskich? Podaj czas działania,...
W tym artykule Kempe-Kleinberg-Tardos autorzy proponują zachłanne algorytmy oparte na funkcjach submodularnych w celu określenia najbardziej wpływowych węzłów na wykresie, z zastosowaniem do sieci społecznościowych.kkk Zasadniczo algorytm wygląda następująco: S=empty setS=empty setS = {\rm...
Zetknąłem się z tym problemem w dziedzinie fizyki dość dalekiej od informatyki, ale wydaje się, że jest to pytanie, które było badane w CS, więc pomyślałem, że spróbuję szczęścia, zadając to tutaj. Wyobraź sobie, że otrzymałeś zestaw punktów oraz listę niektórych odległości między punktami d i j ....
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ą...
Jest dobrze znane, że dla każdego matroid M.MM żadna funkcja ciężaru www , nie wychodzi algorytm GreedyBasis (M, w )GreedyBasis(M,w)\mbox{GreedyBasis}(M,w) , która zwraca na podstawę maksymalny ciężar MMM . Czy zatem odwrotny kierunek jest również prawdą? Oznacza to, że jeśli istnieje jakiś chciwy...
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...
Jeden z moich znajomych pyta mnie o następujący problem z planowaniem na drzewie. Uważam, że jest bardzo czysty i interesujący. Czy jest na to jakieś odniesienie? Problem: Istnieje drzewo , każda krawędź ma symetryczny koszt podróży 1 . Dla każdego wierzchołka v I nie jest to zadanie, które musi...
W 1973 r. Weiner przedstawił pierwszą konstrukcję drzewek z przyrostkami. Algorytm został uproszczony w 1976 r. Przez McCreighta, aw 1995 r. Przez Ukkonen. Niemniej jednak uważam, że algorytm Ukkonen jest stosunkowo zaangażowany koncepcyjnie. Czy istnieją uproszczenia algorytmu Ukkonen od 1995...
Mam problem algebraiczny związany z wektorami w dziedzinie GF (2). Niech będą wektorami wymiaru , a . Znaleźć wielomianowej algorytm czasową znajdzie (0,1)-wektor tego samego wymiaru tak, że nie jest sumą każdy wektory między . Dodawanie wektorów odbywa się ponad polem GF (2), które ma dwa elementy...
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ż...
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 ) + f( A ∩ B ) .f(A)+f(B)≥f(A∪B)+f(A∩B). f(A) + f(B) \geq f(A \cup B) + f(A \cap B). Silniejszą właściwością jest Biorąc C =...
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...
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...
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...