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.

5
Dlaczego osoby o niskiej sprawności mają szansę przeżyć do następnego pokolenia?
Obecnie czytam i obserwuję algorytm genetyczny i uważam go za bardzo interesujący (nie miałem okazji go studiować, gdy byłem na uniwersytecie). Rozumiem, że mutacje oparte są na prawdopodobieństwie (losowość jest źródłem ewolucji), ale nie rozumiem, dlaczego przetrwanie. Z tego, co rozumiem, osoba która ma sprawność fizyczną tak jak dla innej …
3
Pobieranie najkrótszej ścieżki dynamicznego wykresu
Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki podczas wykonywania programu. Próbuję znaleźć skuteczny algorytm do aktualizowania najkrótszych …
2
Wydajny algorytm do „sumowania” zestawu sum
Biorąc pod uwagę zbiór wielu liczb naturalnych X, rozważ zestaw wszystkich możliwych sum: sums(X)={∑i∈Ai|A⊆X}sums(X)={∑i∈Ai|A⊆X}\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\} Na przykład podczas gdy .sumy ( { 1 , 1 } ) = { 0 , 1 , 2 }sums({1,5})={0,1,5,6}sums({1,5})={0,1,5,6}\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}sums({1,1})={0,1,2}sums({1,1})={0,1,2}\textrm{sums}(\left\{1,1\right\}) = …
1
Sortowanie jako program liniowy
Zaskakująca liczba problemów ma dość naturalne ograniczenia w programowaniu liniowym (LP). Przykłady, takie jak przepływy sieciowe, dopasowanie dwustronne, gry o sumie zerowej, najkrótsze ścieżki, forma regresji liniowej, a nawet ocena obwodu, patrz rozdział 7 w [1]! Ponieważ ocena obwodu ogranicza się do programowania liniowego, każdy problem w musi mieć sformułowanie …
1
Jak udowodnić poprawność algorytmu losowego?
Mam dwa sposoby tworzenia listy przedmiotów w losowej kolejności i chciałbym ustalić, czy są one równie uczciwe (obiektywne). Pierwszą metodą, której używam, jest skonstruowanie całej listy elementów, a następnie wykonanie losowania (powiedzmy losowanie Fisher-Yates). Druga metoda jest raczej metodą iteracyjną, która utrzymuje losowość listy przy każdym wstawieniu. W pseudokodzie funkcja …
1
Rozróżnij procedurę decyzyjną w porównaniu do solvera SMT vs provera twierdzeń vs solvera z ograniczeniami
Te terminologie mylą mnie. Jak rozumiem Solver SAT: decyduje o spełnianiu logiki zdań (za pomocą DPLL lub wyszukiwania lokalnego). Procedura decyzyjna to procedura decydująca o spełnieniu pewnej rozstrzygalnej teorii pierwszego rzędu. Solver SMT to solver SAT + procedura decyzyjna. Przysłowie twierdzące wskazuje na coś takiego jak logika dynamiczna, np. Narzędzie …
2
Jeśli mogę rozwiązać Sudoku, czy mogę rozwiązać problem Traveling Salesman (TSP)? Jeśli tak to jak?
Powiedzmy, że istnieje program taki, że jeśli podasz częściowo wypełnione Sudoku o dowolnym rozmiarze, otrzymasz odpowiednie wypełnione Sudoku. Czy możesz potraktować ten program jako czarną skrzynkę i użyć go do rozwiązania TSP? Mam na myśli, czy istnieje sposób na przedstawienie problemu TSP jako częściowo wypełnionego Sudoku, więc jeśli dam ci …
1
Złożoność przyjmowania mod
To wydaje się pytaniem, które powinno mieć łatwą odpowiedź, ale nie mam ostatecznego: nnna,pa,pa, pamodpamodpa\bmod p Jedynie podzielenie przez będzie wymagać czasu , gdzie jest złożoność mnożenia. Ale czy można wykonać nieco szybciej?aaappp O(M(n))O(M(n))O(M(n))M(n)M(n)M(n)modmod\bmod
2
Zbiorowy problem z rachunkiem
Przy stole jest nnn ludzi. iii th osoba musi zapłacić pipip_i dolarów. Niektórzy ludzie nie mają odpowiednich rachunków, aby zapłacić dokładnie , dlatego opracowali następujący algorytm.pipip_i Po pierwsze, wszyscy kładą na stole część swoich pieniędzy. Następnie każda osoba odbiera nadpłacone pieniądze. Rachunki mają ustalony zestaw nominałów (nie stanowi części danych …
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.