Informatyka

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

2
Mnożenie w
Szukałem tutaj i zauważyłem, że najlepszym środowiskiem uruchomieniowym dla mnożenia dwóch liczb bitowych jest O ( n ⋅ log n ⋅ 2 O ( log ∗ n ) , ale łatwo mogę zauważyć algorytm działający w O ( n ⋅ log nnnnO(n⋅logn⋅2O(log∗n)O(n⋅log⁡n⋅2O(log∗⁡n)O(n\cdot \log n \cdot 2^{O(\log^* n)} .O(n⋅logn)O(n⋅log⁡n)O(n\cdot \log n) …
1
Konstruujesz wszystkie języki bezkontekstowe z zestawu języków podstawowych i właściwości zamknięcia?
Jednym ze sposobów patrzenia na wyrażenia regularne jest konstruktywny dowód na następujący fakt: możliwe jest zbudowanie języków regularnych, zaczynając od małego zestawu języków i łącząc je za pomocą małego, stałego zestawu właściwości zamknięcia. W szczególności, jeśli zaczniemy od pustego języka, języka zawierającego pusty ciąg i języków wszystkich ciągów jednoznakowych, możemy …
2
Metoda pomiaru „podobieństwa” między gramatykami FSA?
Pracuję z algorytmem dopasowywania wzorców, który generuje acykliczny automat stanów skończonych, który akceptuje dany ciąg tekstowy i wszystkie jego podciągi. Algorytm FSA jest uruchamiany na symbolicznej reprezentacji strumienia muzycznego (np. Dane MIDI). Strumień muzyczny został wstępnie przetworzony, aby podzielić każdą piosenkę na nieoznaczone „segmenty”. FSA jest generowany dla każdego z …
1
Dlaczego stosowanie Hyper-Threading może prowadzić do obniżenia wydajności
Przeczytałem go w różnych miejscach, takich jak to , że hiperwątkowość prowadzi do obniżenia wydajności. Nie jestem w stanie zrozumieć, dlaczego ani w jaki sposób hiperwątkowanie prowadzi do degradacji. Dlaczego tak jest, że nawet jeśli Hyper-Threading pozwala systemowi operacyjnemu na wykorzystanie wolnych zasobów, następuje degradacja. Choć testy porównawcze wskazują na …
4
Cięcie równych drążków z różnych drążków
Masz drążków o dowolnej długości, niekoniecznie integralnych.nnn Cięcie niektórych patyków (jedno cięcie tnie jeden patyk, ale możemy ciąć tak często, jak chcemy), chcesz uzyskać takich, aby:k &lt; nk&lt;nk<n Wszystkie te kije mają taką samą długość;kkk Wszystkie kije są co najmniej tak długie, jak wszystkie inne kije.kkk Pamiętaj, że po wykonaniu …
2
Zatrzymanie problemu bez odniesienia
W przypadku problemu zatrzymania jesteśmy zainteresowani, czy istnieje maszyna Turinga T.TT która może stwierdzić, czy dana maszyna Turinga M.MM zatrzymuje się, czy nie na danym wejściu . Zwykle dowód zaczyna zakładać, że taki istnieje. Następnie rozważamy przypadek, w którym ograniczamy do samego , a następnie wyprowadzamy sprzeczność za pomocą wystąpienia …
2
Czy
Jeśli hierarchia zapada się na swój drugi poziom (według twierdzenia Karpa-Liptona). Ale co z N P i C o N P ?RP=NPRP=NP\sf RP = NPNPNP\sf NPcoNPcoNP\sf coNP Starałem się udowodnić, że zawarty jest w N P (drugi kierunek jest trywialne, jeśli R P = N P ), ale bez skutku, …
2
Czy ta klasyczna gra z układankami NP-zupełna?
Istnieje klasyczna gra logiczna, bardzo podobna do krzyżówki, z tą różnicą, że podana jest lista słów, a następnie podana jest kwadratowa tablica złożona z kwadratów jednostkowych, z niektórymi kwadratami zaciemnionymi jak krzyżówka, a na niektórych kwadratach jest już napisany list. Celem jest zapisanie każdego słowa z listy raz i tylko …
2
Relacje równoważności obejmują problem (w teorii grafów)
Relację równoważności na skończonym zestawie wierzchołków można przedstawić za pomocą nieukierunkowanego wykresu, który jest rozłącznym połączeniem klików. Zestaw wierzchołków reprezentuje elementy, a krawędź reprezentuje równoważność dwóch elementów. Jeśli mam wykres i wykresy G 1 , … , G k , mówimy, że G jest objęty G 1 , … , …
4
Odzyskiwanie punktu osadzania z wykresu z krawędziami ważonymi odległością punktu
Załóżmy, że podam ci niekierowany wykres z ważonymi krawędziami i powiem, że każdy węzeł odpowiada punktowi w przestrzeni 3D. Ilekroć pomiędzy dwoma węzłami jest krawędź, ciężar krawędzi jest odległością między punktami. Twoim celem jest zrekonstruowanie względnych pozycji punktów, biorąc pod uwagę tylko dostępne odległości (reprezentowane przez wagi krawędzi). Na przykład, …
2
Kombinacyjna interpretacja rachunku lambda
Według Petera Selinger , Lambda Rachunek jest algebraiczna (PDF). Na początku tego artykułu mówi: Kombinacyjna interpretacja rachunku lambda jest znana jako niedoskonała, ponieważ nie spełnia reguły ξξξ : zgodnie z interpretacją M=NM=NM = N nie oznacza λx.M=λx.Nλx.M=λx.N\lambda x.M = \lambda x.N (Barendregt, 1984). Pytania: Jaki rodzaj równoważności ma tu na …
1
Jak wyglądają klasy złożoności, jeśli zastosujemy redukcje Turinga?
Do rozumowania takich rzeczy, jak kompletność NP, zwykle stosujemy redukcje wielokrotne jeden (tj. Redukcje Karp). Prowadzi to do takich zdjęć: (zgodnie ze standardowymi przypuszczeniami). Jestem pewien, że wszyscy znamy tego rodzaju rzeczy. Jakie otrzymamy zdjęcie, jeśli będziemy pracować z redukcjami Turinga (tj. Redukcjami Cooka)? Jak zmienia się obraz? PNPPNPP^{NP}NPNPNPcoNPcoNPcoNPPNPPNPP^{NP}NPNPNP P⊂PNP⊂PH⊂PSPACEP⊂PNP⊂PH⊂PSPACEP …
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.