Pytania otagowane jako ds.algorithms

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

1
Obliczanie maks. Zestawów wolnych od H
Na wykresie niezależny zestaw jest podzbiorem wierzchołków, który nie zawiera krawędzi jako indukowanego podsgrafu. Problem znajdowania największych niezależnych zestawów na wykresie jest fundamentalnym zagadnieniem algorytmicznym i trudnym. Rozważmy bardziej ogólne pytanie dotyczące znalezienia (wielkości) największego zestawu wolnego od H na wykresie, gdzie wolny od H oznacza, że ​​nie indukuje on …
1
Jaki jest najtrudniejszy przykład problemu grupowego izomorfizmu?
Mówi się, że dwie grupy (G,⋅)(G,⋅)(G,\cdot) i (H,×)(H,×)(H, \times) są izomorficzne, jeśli istnieje homomorfizm od GGG do HHH który jest bijectywny. Problem z izomorfizmem grupowym jest następujący: biorąc pod uwagę dwie grupy, sprawdź, czy są izomorficzne, czy nie. Istnieją różne sposoby wprowadzania grupy, dwa najczęściej używane są przez tabelę Cayleya …
2
Problemy bez znanej przewagi kwantowej
Zastanawiałem się, jaka jest lista obecnych naturalnych problemów obliczeniowych, dla których nie ma znanej przewagi złożoności przy użyciu komputera kwantowego. Na początek, myślę, że obliczenie odległości edycji jest tym, dla którego najszybszy znany algorytm kwantowy wydaje się być najszybszym znanym klasycznym. Mówiąc bardziej wstępnie, sugerowałbym również sortowanie jako kolejny problem, …
1
Znalezienie podwójnego wykresu
Według książki Topological Graph Theory autorstwa Grossa i Tuckera, biorąc pod uwagę komórkowe osadzenie wykresu na powierzchni (przez „powierzchnię” rozumiem tutaj kulę z pewnymi uchwytami , a poniżej odnosi się do kuli o dokładnie uchwyty), można zdefiniować podwójny multigraf, traktując twarze osadzonego wykresu jako wierzchołki i dodając krawędź między dwoma …
4
Algorytmy aproksymacyjne stosowane w algorytmach dokładnych
Algorytmy aproksymacyjne mogą dawać wynik do pewnego stałego współczynnika. Jest to nieco mniej satysfakcjonujące niż dokładne algorytmy. Jednak stałe czynniki są ignorowane w złożoności czasowej. Zastanawiam się więc, czy następująca sztuczka jest możliwa lub została zastosowana, aby rozwiązać jakiś problem :B ∘ Ab∘ZAB \circ A Użyj algorytmu aproksymacyjnego rozwiązującego problem …
1
Sortowanie ze średnią porównań
Czy istnieje algorytm sortowania oparty na porównaniu, który wykorzystuje średnie porównania ?lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) Istnienie algorytmu porównania najgorszego przypadku jest otwartym problemem, ale średni przypadek wystarcza dla algorytmu losowego z oczekiwanym porównania dla każdego wkładu. Znaczenie polega na tym, że są to porównania o (n) z optymalnych, marnując średnio tylko o (1) …
2
Złożoność homogenizacji łańcucha
Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i …
1
Czy jest rozstrzygalne, czy długość wyjściowa przetwornika jest ograniczona długością wejściową?
Rozważane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff .[ T ] y x x [ T ] yT.TT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pytanie: Czy można rozstrzygnąć następujący problem: Biorąc pod uwagę: Przetwornik …
1
Czy możemy skonstruować k-mądrą niezależną permutację na [n], używając tylko stałego czasu i przestrzeni?
Niech k>0k>0k>0 będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą nnn , chcemy skonstruować permutację σ∈Snσ∈Sn\sigma \in S_n tak aby: Konstrukcja wykorzystuje stały czas i przestrzeń (tj. Wstępne przetwarzanie zajmuje stały czas i przestrzeń). Możemy użyć randomizacji. Biorąc pod uwagę i∈[n]i∈[n]i\in[n] , σ(i)σ(i)\sigma(i) można obliczyć w stałym czasie i przestrzeni. …
1
Minimalny rozkład równomierny
Biorąc pod uwagę, że dwa wielościany i , i są jeśli istnieją skończone zestawy wielościanów i takie, że i są zgodne dla wszystkich , i . Wiadomo, że jeżeli i są wielokąty o jednakowej powierzchni, takie equidecomposition zawsze występuje i że nie posiada w ogólności dla większych wymiarów . Q …
1
Liczby całkowite wielomianu
Jakiego algorytmu możemy użyć do znalezienia wszystkich pierwiastków całkowitych wielomianu o współczynnikach całkowitych?fa( x )f(x)f(x) Zauważyłem, że Sage może znaleźć pierwiastki w ciągu kilku sekund, nawet jeśli wszystkie współczynniki są bardzo duże. Jak to zrobić?fa( x )f(x)f(x)
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.