Pytania otagowane jako algorithms

Algorytm jest sekwencją dobrze zdefiniowanych kroków, które definiują abstrakcyjne rozwiązanie problemu. Użyj tego tagu, gdy Twój problem dotyczy projektowania i analizy algorytmów.

1
Czy potrafimy znaleźć k najkrótszych ścieżek między wszystkimi parami szybciej niż wielokrotne rozwiązywanie problemu parami?
Chcę produkować kkk najkrótsza droga (kkkbyłoby mniej niż 10) między wszystkimi parami na wykresie. Wykres to (właściwie mapa metra): dodatnio ważony bezkierunkowy rzadki z około 100 węzłami Mój obecny plan ma zastosowanie kkknajkrótsza ścieżka trasy do każdej pary; Teraz szukam bardziej wydajnej alternatywy (prawdopodobnie z programowaniem dynamicznym).
1
Znajdowanie najdłuższego powtarzającego się podsekwencji
Biorąc pod uwagę ciąg sss, Chciałbym znaleźć najdłuższą powtarzającą się (przynajmniej dwukrotnie) podsekwencję. To znaczy, chciałbym znaleźć ciągwww który jest podciągiem (nie musi być ciągły) z sss takie, że w=w′⋅w′w=w′⋅w′w=w' \cdot w' . To jest,wwwto ciąg, którego połówki pojawiają się dwa razy z rzędu. Zauważ, żewww jest podsekwencją sss, ale …
3
Jak rozwiązać problem aranżacyjny w Archive Nationale of France przy użyciu teorii grafów?
Dobry wieczór! Właśnie odbywam staż w Archives Nationales of France i napotkałem sytuację, którą chciałem rozwiązać za pomocą wykresów ... I. Zakurzona sytuacja Chcemy zoptymalizować rozmieszczenie książek w mojej bibliotece zgodnie z ich wysokością, aby zminimalizować koszty archiwizacji. Wysokość i grubość książek są znane. Książki ułożyliśmy już w porządku rosnącymH1,H2,…,HnH1,H2,…,HnH_1,H_2,\dots,H_n(Nie …
1
Jak określić liczbę błędów w algorytmie Welch-Berlekamp?
W algorytmie Welcha-Berlekampa do dekodowania kodów Reeda-Solomona podaje się listę punktów reprezentujących komunikat z błędami na w nieznanych lokalizacjach (i otrzymuje się do algorytmu). Wyjście jest wielomianem przechodzącym przez wszystkie podane punkty z wyjątkiem tych, w których wystąpiły błędy.(zaja,bja)(ai,bja)(a_i, b_i)mimiebjabjab_imimie Metoda polega na rozwiązaniu układu równań liniowych formy bjami(zaja) = …
1
Najcięższy plansza podrzędna
Rozważ następujący problem. Biorąc pod uwagę: Pełny wykres z rzeczywistymi nieujemnymi wagami na krawędziach. Zadanie: znajdź płaski wykres podrzędny o maksymalnej masie. („Maksimum” wśród wszystkich możliwych płaskich wykresów podrzędnych.) Uwaga: Podgraf maksymalnej wagi będzie triangulacją; jeśli cały wykres jest na wierzchołkach, będzie miał krawędzi.nnnm = 3 n - 6m=3)n-6m=3n-6 Pytanie: …
4
Czy unikalność elementu można rozwiązać w deterministycznym czasie liniowym?
Rozważ następujący problem: Dane wejściowe : wyświetla liczb całkowitychX,YX,YX,Y Cel : ustalenie, czy istnieje liczba całkowita xxx która znajduje się na obu listach. Załóżmy, że obie listy X,YX,YX,Y mają rozmiar nnn . Czy dla tego problemu istnieje deterministyczny algorytm czasu liniowego? Innymi słowy, czy możesz rozwiązać ten problem deterministycznie w …
2
Algorytm precyzji pierwiastka kwadratowego?
Czy są znane algorytmy subkwadratowe do obliczania wartości pierwiastka kwadratowego z nliczby całkowitej? Naiwny algorytm byłby podobny def sqrt(x): r = 0 i = x.bit_length() // 2 while i >= 0: inc = (r << (i+1)) + (1 << (i*2)) if inc <= x: x -= inc r += 1 …
1
Jaki jest najbardziej wydajny algorytm i struktura danych do utrzymywania informacji o podłączonych komponentach na wykresie dynamicznym?
Powiedzmy, że mam niedokierowany skończony wykres rzadki i muszę być w stanie efektywnie uruchamiać następujące zapytania: IsConnected(N1,N2)IsConnected(N1,N2)IsConnected(N_1, N_2) - zwraca jeśli istnieje ścieżka między i , w przeciwnym razieTTTN1N1N_1N2N2N_2FFF ConnectedNodes(N)ConnectedNodes(N)ConnectedNodes(N) - zwraca zestaw węzłów, które są osiągalne zNNN Można to łatwo zrobić przez wstępne obliczenie połączonych elementów wykresu. Oba zapytania …
1
Biorąc pod uwagę n ciągów, czy jeden z nich jest podciągiem innego?
Załóżmy, że otrzymaliśmy zbiór ciągów, . Chciałbym wiedzieć, czy którykolwiek z tych ciągów jest podciągiem dowolnego innego ciągu w kolekcji. Innymi słowy, chciałbym algorytm dla następującego zadania:nnnS.1, ... ,S.nS1,…,SnS_1,\dots,S_n Dane wejściowe:S.1, ... ,S.nS1,…,SnS_1,\dots,S_n Wyjście: takie, że jest podłańcuchem i , lub None, jeśli nie takie existja , ji,ji,jS.jaSiS_iS.jotSjS_ji ≠ ji≠ji\ne …
1
Skutecznie znajdując maksymalny GCD parami zestawu liczb naturalnych
Rozważ następujący problem: Niech będzie skończonym podzbiorem liczb naturalnych.S={s1,s2,...sn}S={s1,s2,...sn}S = \{ s_1, s_2, ... s_n \} Niech | gdzie jest największy wspólny dzielnik z iG={G={G = \{ gcd(si,sj)gcd(si,sj)gcd(s_i, s_j)si,sj∈S,si,sj∈S,s_i, s_j \in S, si≠sj}si≠sj} s_i \neq s_j \}gcd(x,y)gcd(x,y)gcd(x,y)xxxyyy Znajdź element maksymalny w .GGG Problem ten można rozwiązać, biorąc największy wspólny dzielnik …
1
Jakie istnieją algorytmy rozwiązywania układów liniowych z liczbami naturalnymi?
Patrzę na następujący problem: Biorąc pod uwagę wymiarowe wektory liczb naturalnych i niektóre wektory wejściowe , czy jest liniową kombinacją z współczynnikami liczb naturalnych?nnnv1,…,vmv1,…,vmv_1, \ldots, v_muuuuuuviviv_i tzn. czy są jakieś gdzie ?t1,…,tm∈Nt1,…,tm∈Nt_1, \ldots, t_m \in \mathbb{N}u=t1v1+⋯+tmvmu=t1v1+⋯+tmvmu = t_1 v_1 + \dots + t_m v_m Oczywiście rzeczywistą wersję tego problemu można …
1
Dlaczego introsort korzysta z heapsortu, a nie z scalania?
W ramach zadania domowego obejmującego implementację introsortu jestem pytany, dlaczego stosuje się heapsort zamiast scalesort (lub inne algorytmy w tym zakresie). O ( n log( n ) )O(nlog⁡(n))O(n\log(n)) Introsort to hybrydowy algorytm sortowania, który zapewnia zarówno szybką średnią wydajność, jak i (asymptotycznie) optymalną wydajność w najgorszym przypadku. Zaczyna się od …
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.