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.

3
Złożoność przestrzeni rozpoznawania palindromów Watsona-Cricka
Mam następujący problem algorytmiczny: Określ przestrzeń Turinga złożoności rozpoznawania ciągów DNA, które są palindromami Watsona-Cricka. Palindromy Watsona-Cricka to ciągi, których odwróconym dopełnieniem jest ciąg oryginalny. Dopełnieniem jest zdefiniowany litery mądry inspirowany DNA: A jest dopełnieniem T, a C jest dopełnieniem G. prosty przykład dla WC-palindrom jest ACGT. Wymyśliłem dwa sposoby …
3
Błąd w użyciu notacji asymptotycznej
Usiłuję zrozumieć, co jest nie tak z następującym dowodem kolejnego wystąpienia T(n)=2T(⌊n2⌋)+nT(n)=2T(⌊n2⌋)+n T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n)T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n) T(n) \leq 2\left(c\left\lfloor\frac{n}{2}\right\rfloor\right)+n \leq cn+n = n(c+1) =O(n) Dokumentacja mówi, że jest błędna z powodu hipotezy indukcyjnej, że T(n)≤cnT(n)≤cn T(n) \leq cn Czego mi brakuje?
1
Biorąc pod uwagę ciąg i CFG, jakie znaki mogą podążać za ciągiem (w sentymentalnych formach CFG)?
Niech ΣΣ\Sigma będzie zbiorem terminali, a NNN zbiorem nieterminalnych symboli gramatyki bez kontekstu GGG. Powiedzieć, że posiada ciąg a∈(Σ∪N)+a∈(Σ∪N)+a \in (\Sigma \cup N)^+ taki, że w którym i są zdaniowymi formy .x , y ∈ ( Σ ∪ N ) ∗ S ( G ) Gxay∈S(G)xay∈S(G)x a y \in \mathcal{S}(G)x,y∈(Σ∪N)∗x,y∈(Σ∪N)∗x,y\in …
5
Konwersja digrafu na niekierowany wykres w odwracalny sposób
Szukam algorytmu do konwersji digrafu (grafu kierunkowego) na graf niekierowany w sposób odwracalny, tzn. Digraf powinien być odtwarzalny, jeśli otrzymamy wykres niekierowany. Rozumiem, że przyjdzie to kosztem niekierowanego wykresu mającego więcej wierzchołków, ale nie mam nic przeciwko. Czy ktoś wie jak to zrobić lub może zasugerować jakieś referencje? Z góry …
1
Jak zmniejszyć liczbę skrzyżowanych krawędzi na schemacie?
Pracuję nad edytorem diagramów. Diagramy przedstawiają kształty 2D ( węzły ) połączone ze złączami ( krawędziami ). Chciałbym dodać operację, która, biorąc pod uwagę wybór węzłów, „rozplątuje” je: zmienia ich położenie, jeśli to możliwe, aby zmniejszyć liczbę przecinających się krawędzi (i jest w porządku, jeśli krawędzie będą musiały być rysowane …
5
Co to jest wydajny algorytm?
Z punktu widzenia zachowania asymptotycznego, co jest uważane za „wydajny” algorytm? Jaki jest standard / powód rysowania linii w tym punkcie? Osobiście uważałbym, że wszystko, co naiwnie nazwałbym „sub-wielomianem”, takie jakfa( n ) = o (n2))f(n)=o(n2)f(n) = o(n^2) Jak na przykład n1 + ϵn1+ϵn^{1+\epsilon} byłby wydajny i wszystko, co jest …
1
Jak zbudować podwójnie połączoną listę krawędzi, biorąc pod uwagę zestaw segmentów linii?
Dla danego płaskiego wykresu osadzonego w płaszczyźnie, zdefiniowanego przez zestaw segmentów liniowych , każdy segment jest reprezentowany przez punkty końcowe . Skonstruuj strukturę danych DCEL dla podziału planarnego, opisz algorytm, udowodnij jego poprawność i pokaż złożoność.G(V,E)G(V,E)G(V,E)E={e1,...,em}E={e1,...,em}E= \left \{ e_1,...,e_m \right \} eieie_i{Li,Ri}{Li,Ri}\left \{ L_i,R_i \right \} Zgodnie z tym opisem …
1
Jak zmaksymalizować
Widzę wiele problemów algorytmicznych, które zawsze sprowadzają się do czegoś o długości: Masz tablicę liczb całkowitychh[1..n]≥0h[1..n]≥0h[1..n]\geq 0, musisz znaleźć i,ji,ji,j takie, które maksymalizuje (h[j]−h[i])(j−i)(h[j]−h[i])(j−i)(h[j]-h[i])(j-i) w O(n)O(n)O(n) czas. Oczywiście O(n2)O(n2)O(n^2) rozwiązaniem czasowym jest rozważenie wszystkich par, jednak czy jest jakiś sposób, aby zmaksymalizować wyrażenie O(n)O(n)O(n) nie wiedząc nic więcej o właściwościach …
1
Czy istnieje skuteczny algorytm do określania, czy wykres ma nietrywialny automorfizm?
Pracuję nad problemem związanym z kwadratami łacińskimi i chcę metody, która zasadniczo sprowadza się do problemu decyzyjnego: Dane wejściowe : skończony, prosty wykres G. Dane wyjściowe : YESjeśli G ma nietrywialny automorfizm, w NOprzeciwnym razie. W związku z tym... Pytanie : Czy istnieje skuteczny algorytm do określania, czy wykres ma …
2
Znajdź optymalne zamówienie
Natknąłem się na ten problem i staram się znaleźć sposób, aby go rozwiązać. Jakiekolwiek propozycje będą mile widziane! Załóżmy, że mamy matrycę {−1,0,1}n × k{−1,0,1}n × k\{-1, 0, 1\}^{n\ \times\ k} , na przykład, ⎡⎣⎢⎢⎢⎢⎢⎢1−10−11001−101010000010−11−11−1⎤⎦⎥⎥⎥⎥⎥⎥[1010−1−100010110−1−1−10111000−1]\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 …
2
Liczenie wysp w macierzach boolowskich
Biorąc pod uwagę n×mn×mn \times m Macierz boolowska XX\mathrm X, pozwolić 000 pozycje reprezentują morze i 111wpisy reprezentują ziemię. Zdefiniuj wyspę jako sąsiadującą pionowo lub poziomo (ale nie po przekątnej)111 wpisy. Pierwotne pytanie polegało na zliczeniu liczby wysp w danej matrycy. Autor opisał rozwiązanie rekurencyjne (O(nm)O(nm)\mathcal{O}(nm) pamięć). Ale bezskutecznie próbowałem …
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.