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.

4
Czy są jakieś algorytmy kompresji oparte na PI?
Wiemy, że π jest nieskończone i całkiem prawdopodobne, że zawiera każdy możliwy skończony ciąg cyfr ( sekwencja rozłączna ). Ostatnio widziałem prototyp πfs, który zakłada, że ​​każdy plik, który utworzyłeś (lub ktokolwiek inny) lub utworzysz, już tam jest, więc jest to kwestia wyodrębnienia go. Istnieje również piFile, który może konwertować …
2
Problem izomorfizmu grafów dla grafów znakowanych
W przypadku grafów nieznakowanych problemem izomorfizmu grafów można zająć się szeregiem algorytmów, które działają bardzo dobrze w praktyce. Oznacza to, że chociaż najgorszy przypadek czasu działania jest wykładniczy, zwykle ma on czas działania wielomianowego. Miałem nadzieję, że sytuacja jest podobna w przypadku wykresów oznaczonych. Jednak naprawdę ciężko mi znaleźć jakiekolwiek …
3
Zrozumienie algorytmu problemu ze stacją benzynową
W przypadku problemu ze stacją benzynową podajemy miast i drogi między nimi. Każda droga ma długość, a każde miasto określa cenę paliwa. Jedna jednostka drogi kosztuje jedną jednostkę paliwa. Naszym celem jest przejście ze źródła do miejsca docelowego w najtańszy możliwy sposób. Nasz czołg jest ograniczony pewną wartością.{ 0 , …
1
Złożoność znalezienia macierzy pseudoinwersyjnej
Ile operacji arytmetycznych jest wymaganych do znalezienia pseudo-odwrotnej macierzy Moore'a i Penrose'a o dowolnym polu? Jeśli macierz jest odwracalna i ma złożoną wartość, to jest to tylko odwrotność. Znalezienie odwrotności zajmuje czas , gdzie jest stałą mnożenia macierzy. Jest to Twierdzenie 28.2 we Wstępie do Algorytmów 3. edycja.ωO(nω)O(nω)O(n^\omega)ωω\omega Jeśli macierz …
1
Jak szybko możemy zdecydować, czy dany DFA jest minimalny?
Minimalizowanie deterministycznych automatów skończonych (DFA) to problem, który został dokładnie przestudiowany w literaturze, i zaproponowano kilka algorytmów w celu rozwiązania następującego problemu: Biorąc pod uwagę DFA , oblicz odpowiednią minimalną DFA akceptującą ten sam język, co \ mathscr {A} . Większość tych algorytmów działa w czasie wielomianowym.ZAA\mathscr{A}ZAA\mathscr{A} Zastanawiam się jednak, …
3
Algorytm dopasowywania liczb przy minimalnej liczbie ruchów
Jest to rodzaj pytania do edycji i jest bardzo łatwe. Jestem po prostu dość martwy w tym temacie i jak dotąd nie mogę tego rozgryźć. Biorąc pod uwagę szereg liczb, np [3, 1, 1, 1] Jak najskuteczniej przekształcić wszystkie liczby w tę samą liczbę przy minimalnej liczbie „ruchów”? Przez „przeniesienie” …
1
Wariant problemu plecakowego
Jak podchodziłbyś do problemu plecaka w sytuacji dynamicznego programowania, gdybyś musiał teraz ograniczyć liczbę przedmiotów w plecaku o stałe ppp ? Jest to ten sam problem (maksymalna waga WWW , każdy przedmiot ma wartość vvv i ciężar www ), ale można dodać tylko ppp przedmiotów do plecaka i oczywiście trzeba …
3
Czy istnieją algorytmy potęgowania równoległego macierzy, które są bardziej wydajne niż mnożenie sekwencyjne?
Wymagane jest znalezienie mocy (dodatniej liczby całkowitej) macierzy liczb rzeczywistych. Istnieje wiele wydajnych algorytmów mnożenia macierzy (np. Niektóre algorytmy równoległe to Cannon, DNS ), ale czy istnieją algorytmy, które są przeznaczone właśnie do znalezienia mocy macierzy i które są bardziej wydajne niż sekwencyjne wykonywanie mnożenia macierzy? Szczególnie interesują mnie algorytmy …
1
Struktura danych dla mapy w odstępach czasu
Niech będzie liczbą całkowitą, a oznacza zbiór wszystkich liczb całkowitych. Niech oznacza przedział liczb całkowitych .nnnZZ\mathbb{Z}[a,b][a,b][a,b]{a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} Szukam struktury danych do reprezentowania mapy . Chcę, aby struktura danych obsługiwała następujące operacje:f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} get(i)get(i)\text{get}(i) should return f(i)f(i)f(i). set([a,b],y)set([a,b],y)\text{set}([a,b],y) should update fff so that f(a)=f(a+1)=⋯=f(b)=yf(a)=f(a+1)=⋯=f(b)=yf(a)=f(a+1)=\cdots=f(b)=y, i.e., update fff to a new map …
2
Porównanie algorytmu Aho-Corasicka z algorytmem Rabina-Karpa
Pracuję nad algorytmami wyszukiwania ciągów, które obsługują wyszukiwanie wielu wzorców. Znalazłem dwa algorytmy, które wydają się najsilniejszymi kandydatami pod względem czasu działania, a mianowicie Aho-Corasick i Rabin-Karp . Nie udało mi się jednak znaleźć kompleksowego porównania między dwoma algorytmami. Który algorytm jest bardziej wydajny? Który z nich jest bardziej odpowiedni …
1
Algorytm sprawdzający, czy język jest prawidłowy
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest prawidłowy? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak L={anbn:n∈N}L={anbn:n∈N}L=\{a^n b^n : n \in \mathbb{N}\}), sprawdź, czy język jest prawidłowy, czy nie. Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich …
1
Średnia długość ścieżek st (prostych) na skierowanym wykresie
Biorąc pod uwagę fakt, że wyliczenie ścieżki - jest problemem # P-zupełnym, czy mogłyby istnieć wydajne metody obliczające (lub przynajmniej przybliżające) średnią długość ścieżki - bez ich wyliczania? Co jeśli ścieżki mogą ponownie odwiedzać wierzchołki?t s tssstttsssttt Pomocne mogą być również odpowiednie wyniki na specjalnych wykresach.
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.