Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

4
NFA z wykładniczą liczbą stanów po rozpoznaniu
Jak zbudować przykład DFA, który ma stanów, w których równoważny NFA ma n stanów. Oczywiście zestaw stanów DFA powinien zawierać wszystkie podzestawy zestawu stanów NFA, ale nie wiem jak zacząć. Jakieś sugestie, żeby postawić mnie na właściwej drodze?2n2n2^nnnn
2
Jaka jest złożoność obliczania współczynnika korelacji rang Spearmana?
Byłem studiowania Współczynnik korelacji rang Spearmana ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2−−−−−−−−−−−−−−−−−−−√ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} . dla dwóch list i . Jaka jest złożoność algorytmu?x1,…,xnx1,…,xnx_1, \dots, x_ny1,…,yny1,…,yny_1, \dots, y_n Skoro algorytm powinien po prostu obliczać odejmowań, to czy można być ?nnnO(n)O(n)O(n)
2
Robi
Czy z dostępem Oracle do większy niż ? Rozumiem, że to tylko maszyna Turinga, która może wysyłać zapytania do innej maszyny , jeśli tak, to może symulować ? Czy coś jest nie tak z tym argumentem?NPNPNPNPNPNPNPNPNPNPNPNPNPNP^ {NP}NPNPNPNPNPNPNPNPNPNPNP^{NP}
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 …
4
Czy maszyna Turinga (TM) może zdecydować, czy problem zatrzymania dotyczy wszystkich baz TM?
Na tej stronie istnieje wiele wariantów pytania, czy bazy TM mogą zadecydować o problemie zatrzymania, czy dla wszystkich innych baz TM lub niektórych podzbiorów. To pytanie jest nieco inne. Pytanie, czy problem zatrzymania dotyczy wszystkich baz TM może zostać rozstrzygnięty przez TM. Uważam, że odpowiedź brzmi „nie” i chcę sprawdzić …
2
Czy istnieje kod binarny o długości 6, rozmiarze 32 i odległości 2?
Problem polega na udowodnieniu lub obaleniu istnienia , st, ; ; . ( oznacza odległość uderzenia)doCC| c | =6,∀c∈C|c|=6,∀c∈C|c| = 6,\forall c\in C| do| =32|C|=32|C| = 32re(doja,dojot) ≥ 2 , 1 ≤ i &lt; j ≤ 32d(ci,cj)≥2,1≤i&lt;j≤32d(c_i,c_j)\geq2,1\leq i<j\leq32redd Próbowałem skonstruować satysfakcjonujący kod. Najlepsze, co mogę uzyskać, to pozwolić , połączenie …
6
Czy istnieją odmiany regularnych środowisk uruchomieniowych notacji Big-O-Notation?
Istnieje wiele Notacji, takich jak lub i tak dalej. Zastanawiałem się, czy w rzeczywistości istnieją odmiany takich jak lub , czy też są matematycznie niepoprawne.OOOO(n)O(n)O(n)O(n2)O(n2)O(n^2)O(2n2)O(2n2)O(2n^2)O(logn2)O(log⁡n2)O(\log n^2) A może słuszne byłoby stwierdzenie, że można poprawić do ? Nie mogę i nie muszę jeszcze wymyślać środowisk uruchomieniowych i nie muszę niczego poprawiać, …
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 …
4
Problem ograniczonego zatrzymania jest rozstrzygalny. Dlaczego ten konflikt z twierdzeniem Rice'a?
Jedno stwierdzenie twierdzenia Rice'a znajduje się na stronie 35 „Złożoności obliczeniowej: nowoczesne podejście” (Arora-Barak): Funkcja częściowa od do to funkcja, która niekoniecznie jest zdefiniowana na wszystkich jej wejściach. Mówimy, że TM oblicza funkcję cząstkową jeżeli dla każdego na którym zdefiniowano , i dla każdego na którym nie zdefiniowano przechodzi w …
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.