Pytania otagowane jako ds.algorithms

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

5
Jaka jest maksymalna liczba trwałych małżeństw w przypadku problemu stabilnego małżeństwa?
Problem stabilnego małżeństwa: http://en.wikipedia.org/wiki/Stable_marriage_problem Zdaję sobie sprawę, że w przypadku SMP możliwe jest wiele innych stabilnych małżeństw, z wyjątkiem algorytmu Gale-Shapleya. Jeśli jednak otrzymamy tylko , liczbę mężczyzn / kobiet, zadajemy następujące pytanie: Czy możemy stworzyć listę preferencji, która daje maksymalną liczbę trwałych małżeństw? Jaka jest górna granica takiej liczby?nnn
4
Jaki jest najszybszy sposób sprawdzenia włączenia zestawu?
Biorąc pod uwagę podzbiorów z .nnnS1,…,SnS1,…,SnS_1,\ldots,S_n{1,…,d}{1,…,d}\{1,\ldots,d\} Sprawdź, czy istnieją zestawy z . (Jeśli tak, znajdź przykład, jeśli nie, po prostu powiedz „nie”)Si,SjSi,SjS_i,S_jSi⊊SjSi⊊SjS_i \subsetneq S_j Trywialne rozwiązanie tego problemu polega na przejściu wszystkich par zestawów i sprawdza włączenie pary w czasie , więc całkowity czas działania wynosi . Czy ten problem …
1
Złożoność przestrzenna algorytmu Coppersmitha – Winograda
Algorytm Coppersmitha – Winograda jest asymptotycznie najszybszym znanym algorytmem do mnożenia dwóch macierzy kwadratowych. Czas działania ich algorytmu to który jest najlepiej znany do tej pory. Jaka jest złożoność przestrzeni tego algorytmu? Czy to jest w ?n×nn×nn \times nO(n2.376)O(n2.376)O(n^{2.376})Θ(n2)Θ(n2)\Theta(n^2)
8
Obliczanie odległości Levenshteina szybko
Biorąc pod uwagę ogromną bazę dozwolonych słów (posortowane alfabetycznie) i słowo, znajdź słowo z bazy danych, która jest najbliższa podanemu słowu pod względem odległości Levenshteina. Naiwnym podejściem jest oczywiście po prostu obliczenie odległości levenshteina między danym słowem a wszystkimi słowami w słowniku (możemy przeprowadzić wyszukiwanie binarne w bazie danych przed …
2
Jeśli techniki uczenia maszynowego będą się ciągle poprawiać, jaka jest rola algorytmiki w przyszłości?
Spójrzmy w przyszłość za 30 lat. Bądźmy optymistami i załóżmy, że obszary związane z uczeniem maszynowym rozwijają się tak szybko, jak to, co widzieliśmy w ciągu ostatnich 10 lat. Byłoby świetnie, ale jaka byłaby rola tradycyjnej algorytmiki w takiej przyszłości? Tutaj przez „tradycyjną algorytmię” odnoszę się do zwykłego procesu, który …
1
Decydowanie o pustce przecięcia zwykłych języków w czasie subkwadratowym
Niech będą dwoma zwykłymi językami podanymi przez NFA M_1 jako dane wejściowe.M 1 , M 2L.1, L2)L1,L2L_1,L_2M.1, M2)M1,M2M_1,M_2 Załóżmy, że chcielibyśmy sprawdzić, czy . Można to wyraźnie zrobić za pomocą algorytmu kwadratowego, który oblicza automat produktu , , ale zastanawiałem się, czy wiadomo coś bardziej wydajnego.M 1 , M 2L.1∩ …
5
Algorytmy aproksymacji dla maksymalnego niezależnego zestawu na specjalnych klasach wykresów
Wiemy, że maksymalny niezależny zestaw (MIS) jest trudny do przybliżenia przy współczynniku dla dowolnego ϵ > 0, chyba że P = NP. Jakie są specjalne klasy wykresów, dla których znane są lepsze algorytmy aproksymacyjne?n1−ϵn1−ϵn^{1-\epsilon}ϵ>0ϵ>0\epsilon > 0 Jakie są wykresy, dla których znane są algorytmy wielomianowe? Wiem, że dla idealnych wykresów …
1
Algorytmy przestrzeni logów na wykresach z ograniczoną szerokością drzewa
Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Trudno jest obliczyć szerokość drzewa. Najbardziej znany algorytm aproksymacyjny osiąga współczynnik .O ( log n----√)O(logn)O(\sqrt{{\log}n}) Twierdzenie Courcelle'a stwierdza, że dowolną właściwość grafów definiowalną w monadycznej logice drugiego rzędu (MSO2) można rozstrzygać w czasie liniowym na dowolnej klasie wykresów o ograniczonej szerokości …
6
Rodziny wykresów z wielomianowymi algorytmami czasowymi do obliczania liczby chromatycznej
Post zaktualizowany 31 sierpnia : dodałem podsumowanie aktualnych odpowiedzi poniżej oryginalnego pytania. Dzięki za wszystkie interesujące odpowiedzi! Oczywiście każdy może nadal publikować wszelkie nowe ustalenia. Dla których rodzin grafów istnieje algorytm wielomianowy do obliczania liczby chromatycznej ?χ(G)χ(G)\chi(G) Problem można rozwiązać w czasie wielomianowym, gdy (wykresy dwudzielne). Na ogół, gdy χ …
1
Dokładnie płaski przepływ elektryczny
Rozważmy sieć elektryczną zamodelowaną jako płaski wykres G, gdzie każda krawędź reprezentuje rezystor 1 Ω. Jak szybko możemy obliczyć dokładną efektywną rezystancję między dwoma wierzchołkami w G? Równolegle, jak szybko możemy obliczyć dokładny prąd płynący wzdłuż każdej krawędzi, jeśli podłączymy baterię 1 V do dwóch wierzchołków w G? Znane prawa …
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.