Informatyka

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

2
Ustaw podobieństwo - Oblicz indeks Jaccard bez kwadratowej złożoności
Mam grupę n zestawów, dla których muszę obliczyć wartość „unikatowości” lub „podobieństwa”. Jako odpowiedni wskaźnik zdecydowałem się na indeks Jaccard . Niestety indeks Jaccard działa tylko na dwóch zestawach na raz. Aby obliczyć podobieństwo między wszystkimi zbiorami, będzie to wymagało w kolejności n 2 obliczeń Jaccard.nnnn2)n2)n^2 (Jeśli to pomaga, wynosi …
2
Klasyfikacja algorytmów losowych
Z Wikipedii na temat algorytmów losowych Należy rozróżnić algorytmy, które wykorzystują losowe dane wejściowe w celu zmniejszenia oczekiwanego czasu działania lub zużycia pamięci, ale zawsze kończą się poprawnym wynikiem w ograniczonym czasie, a algorytmy probabilistyczne , które w zależności od losowych danych wejściowych mają szansę wygenerowania niepoprawnego wyniku (algorytmy Monte …
2
Co to jest parser IELR (1)?
Próbuję nauczyć się używania żubra. Bizon manpage (1) mówi o bizonie: Wygeneruj deterministyczny analizator składni LR lub uogólniony analizator składni LR (GLR), korzystając z tabel analizatora składni LALR (1), IELR (1) lub kanonicznej LR (1). Co to jest parser IELR? Wszystkie istotne artykuły, które znalazłem w sieci WWW, są płatne.
3
Wydajna struktura danych obsługująca wstawianie, usuwanie i większość częstotliwości
Załóżmy, że mamy zestaw a każdy element jest parą danych i kluczy. Chcemy struktury danych, która obsługiwałaby następujące operacje:DDDDDD Wstaw do ,(d,k)(d,k)(d,k)DDD Usuń członka , (nie trzeba szukać, aby znaleźć , np. wskazuje na członka w ),eeeeeeeeeDDD MostFrequent, który zwraca element członkowski dzięki czemu jest jednym z najczęstszych kluczy w …
2
Kilka pytań na temat obliczeń równoległych i klasy NC
Mam wiele powiązanych pytań dotyczących tych dwóch tematów. Po pierwsze, większość tekstów złożoności tylko tuszować klasę . Czy istnieje dobry zasób, który bardziej szczegółowo omawia badania? Na przykład coś, co omawia wszystkie moje pytania poniżej. Ponadto, jestem przy założeniu, że N C nadal widzi ilość godziwą badań ze względu na …
1
Liczenie par inwersji
Klasyczne zastosowanie dzielenia i podbijania polega na rozwiązaniu następującego problemu: Biorąc pod uwagę tablicę różnych, porównywalnych elementów, policz liczbę par inwersji w tablicy: pary ( i , j ) takie, że a [ i ] > a [ j ] i i < j .a [ 1 … n ]za[1…n]a[1\dots …
4
Czy każdy algorytm czasu liniowego jest algorytmem przesyłania strumieniowego?
Powyżej na to pytanie o liczeniu inwersji , ja znalazłem papier , który okazuje się dolną granicę przestrzeni złożoności dla wszystkich (dokładne) algorytmy strumieniowe . Twierdziłem, że to ograniczenie obejmuje wszystkie liniowe algorytmy czasowe. Jest to nieco odważne, ponieważ ogólnie algorytm czasu liniowego może skakać do woli (dostęp losowy), czego …
1
W przypadku maszyny Turinga , w jaki sposób zestaw maszyn które są „krótsze” niż i które akceptują ten sam język, jest rozstrzygalny?
Zastanawiam się, jak to się stało, że język jest w następujący .RR\mathrm R L.M.1= { ⟨M2)⟩∣∣M.2) jest TM, a L ( M1) = L ( M2)) , A | ⟨ M1⟩ | > | ⟨ M2)⟩ | }L.M.1={⟨M.2)⟩|M.2) jest TM, i L.(M.1)=L.(M.2)), i |⟨M.1⟩|>|⟨M.2)⟩|}L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a …
1
Kiedy
Zgodnie z artykułem Wikipedii , L w oznacza „skanowanie od lewej do prawej”, a „R” oznacza „pochodzenie od prawej”. Jednak w oryginalnym artykule Knutha na temat gramatyki definiuje (na stronie 610) jako język, który jest „możliwy do przetłumaczenia z lewej na prawą za pomocą związanego ”.L R ( k )L.R(k)LR(k)L …
2
Czy jest rozstrzygalne, czy TM osiągnie jakąś pozycję na taśmie?
Mam te pytania ze starego egzaminu, który próbuję rozwiązać. Dla każdego problemu wejście jest kodowanie pewnej maszyny Turingowi .MMM Dla liczby całkowitej i następujących trzech problemów:c>1c>1c>1 Czy to prawda, że ​​dla każdego wejścia , M nie przechodzi przez pozycję podczas pracy na ?xxx|x|+c|x|+c|x|+cxxx Czy to prawda, że ​​dla każdego wejścia …
2
Kompromis czasowo-przestrzenny dla problemu brakującego elementu
Oto dobrze znany problem. Biorąc pod uwagę tablicę A[1…n]A[1…n]A[1\dots n] dodatnich liczb całkowitych, wyprowadzaj najmniejszą dodatnią liczbę całkowitą spoza tablicy. Problem można rozwiązać w przestrzeni i czasie O(n)O(n)O(n) : przeczytaj tablicę, śledź w przestrzeni O(n)O(n)O(n) czy wystąpiło 1,2,…,n+11,2,…,n+11,2,\dots,n+1 poszukaj najmniejszego elementu. Zauważyłem, że możesz wymieniać przestrzeń na czas. Jeśli masz …
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.