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
Znalezienie dokładnych rozwiązań narożnych dla programowania liniowego przy użyciu metod punktów wewnętrznych
Algorytm simpleks chciwie chodzi po rogach wielopola, aby znaleźć optymalne rozwiązanie problemu programowania liniowego. W rezultacie odpowiedź jest zawsze rogiem polytopa. Metody punktowe wewnętrzne chodzą po polytopie. W rezultacie, gdy cała płaszczyzna polytopu jest optymalna (jeśli funkcja celu jest dokładnie równoległa do płaszczyzny), możemy uzyskać rozwiązanie w środku tej płaszczyzny. …
3
Jak przekonwertować NFA z nakładającymi się cyklami na wyrażenie regularne?
Jeśli dobrze rozumiem, NFA mają taką samą moc ekspresji jak wyrażenia regularne. Często odczytywanie równoważnych wyrażeń regularnych z NFA jest łatwe: przekładasz cykle na gwiazdy, skrzyżowania jako alternatywy i tak dalej. Ale co zrobić w tym przypadku: [ źródło ] Nakładające się cykle utrudniają zobaczenie, co akceptuje ten automat (pod …
1
Czy istnieje podububowy algorytm dla następującego problemu?
Biorąc pod uwagę symetryczną rzeczywistą macierz , czy istnieje algorytm, który oblicza sumę ponad wszystkimi 1 \ leq i &lt;j &lt;k \ leq n ze złożonością czasową lepszą niż O (n ^ 3) ?n×nn×nn \times nA=(aij)A=(aij)A=(a_{ij})∑i,j,kmax(aij,aik,ajk)∑i,j,kmax(aij,aik,ajk)\sum_{i,j,k}\max(a_{ij},a_{ik},a_{jk})1≤i&lt;j&lt;k≤n1≤i&lt;j&lt;k≤n1\leq i<j<k\leq nO(n3)O(n3)O(n^3)
2
Najmniej powszechny niepodzielnik
SSSdddSSS∀x∈S, d∤x∀x∈S, d∤x\forall x \in S,\ d \nmid x Oznacz n=|S|n=|S|n = |S|i C=max(S)C=max(S)C = \max(S) . Rozważ funkcję F(x)=F(x)=F(x) = najmniejsza liczba pierwsza niepodzieląca xxx . Łatwo zauważyć, że F(x)≤logxF(x)≤log⁡xF(x) \leq \log x . I przez zestaw SSS , niech F(S)=F(S)=F(S) = najmniej Prime że nie dzieli każdy z …
1
Czy wszystkie znane algorytmy rozwiązywania problemów NP-zupełnych są konstruktywne?
Czy są znane algorytmy, które poprawnie wypisują odpowiedź „tak” dla problemu NP-complete bez pośredniego generowania certyfikatu? Rozumiem, że łatwo jest przekształcić wyrocznię spełniającą w znajdującą satysfakcjonujące zadanie: po prostu iteruj po zmiennych, za każdym razem pytając wyrocznię spełniającą o rozwiązanie związku tej zmiennej z pierwotnym problemem. Ale czy takie opakowanie …
3
Różnica między krawędziami poprzecznymi i przednimi w DFT
W pierwszym drzewie głębokości znajdują się krawędzie, które definiują drzewo (tj. Krawędzie, które zostały użyte podczas przejścia). Pozostały pewne krawędzie łączące niektóre inne węzły. Jaka jest różnica między krawędzią poprzeczną a przednią? Z wikipedii: Na podstawie tego drzewa łączącego krawędzie oryginalnego wykresu można podzielić na trzy klasy: krawędzie przednie, które …
5
Częstotliwość wyrazów z uporządkowaniem w złożoności O (n)
Podczas wywiadu na stanowisko programisty Java zapytano mnie: Napisz funkcję, która przyjmuje dwa parametry: ciąg znaków reprezentujący dokument tekstowy i liczba całkowita podająca liczbę elementów do zwrócenia. Zaimplementuj funkcję tak, aby zwracała listę ciągów uporządkowanych według częstotliwości słów, najczęściej występujących jako pierwsze słowo. Twoje rozwiązanie powinno działać w czasie gdzie …
1
Co obliczył tajemniczy mały program Turinga na komputerze w Manchesterze?
Czytam artykuł Turinga „Maszyny obliczeniowe i inteligencja” ( https://www.csee.umbc.edu/courses/471/papers/turing.pdf ) i znalazłem fragment, w którym mówi: Na komputerze w Manchesterze utworzyłem mały program wykorzystujący tylko 1000 jednostek pamięci, przy czym maszyna dostarczona z jedną szesnastocyfrową liczbą odpowiada drugą w ciągu dwóch sekund. Przeciwstawiłbym się każdemu, kto mógłby wyciągnąć z tych …
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.