Informatyka

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

2
Wydajna struktura danych mapy obsługująca przybliżone wyszukiwanie
Szukam struktury danych, która obsługuje efektywne przybliżone wyszukiwanie kluczy (np. Odległość Levenshteina dla ciągów znaków), zwracając możliwie najbliższe dopasowanie dla klucza wejściowego. Najlepszą strukturą danych, jaką do tej pory znalazłem, są drzewa Burkhard-Keller , ale zastanawiałem się, czy istnieją inne / lepsze struktury danych do tego celu. Edycja: Więcej szczegółów …
1
Dlaczego algorytm rotacji drzewa splay uwzględnia zarówno węzeł nadrzędny, jak i dziadek?
Nie do końca rozumiem, dlaczego rotacja w strukturze danych drzewa splay uwzględnia nie tylko element nadrzędny węzła oceniającego, ale także dziadka (operacja zygzak i zig-zig). Dlaczego następujące elementy nie działają: Gdy wstawiamy na przykład nowy węzeł do drzewa, sprawdzamy, czy wstawiamy do lewego lub prawego poddrzewa. Jeśli wstawimy w lewo, …
5
Dlaczego nie jest to nierozstrzygalny problem w NP?
Najwyraźniej nie ma żadnych nierozstrzygalnych problemów w NP. Jednak według Wikipedii : NP jest zbiorem wszystkich problemów decyzyjnych, dla których przypadki, w których odpowiedź brzmi „tak”, mają […] dowody, które są] weryfikowalne w czasie wielomianowym przez deterministyczną maszynę Turinga. [...] Mówi się, że problem występuje w NP wtedy i tylko …
11
Czy przypadkowość von Neumanna w cytacie z grzechu nie ma już zastosowania?
Jakiś facet powiedział: Każdy, kto próbuje generować losowe liczby za pomocą deterministycznych środków, oczywiście żyje w stanie grzechu. To zawsze oznacza, że ​​nie można wygenerować prawdziwych liczb losowych za pomocą samego komputera. Powiedział też, że gdy komputery były równoważnej wielkości pojedynczego mikroprocesora Intel 8080 (~ 6000 zaworów). Komputery stały się …
2
Czy są jakieś problemy, które są łatwe do obliczenia, ale trudne do zweryfikowania?
Zakładając, że P NP, problemy z kompletnością NP są „trudne do rozwiązania, ale mają odpowiedzi, które można łatwo sprawdzić”. Czy ma sens rozważenie czegoś przeciwnego, to znaczy problemów, dla których łatwo jest poprawnie obliczyć prawidłową odpowiedź, ale trudno jest zweryfikować dowolne rzekome rozwiązanie?≠≠\neq Myślę, że taki problem oznaczałby albo: Wykładniczo …
3
Których algorytmów nie można zrównoleglać?
Czy istnieje jakiś algorytm, który jest bardzo trudny do zrównoleglenia lub badania są nadal aktywne? Chciałem wiedzieć o każdym algorytmie lub polu badań w obliczeniach równoległych. Wszystko, czego szukałem, ma „równoległą” implementację. Po prostu chcę zrobić trochę badań na dowolnym niezbadanym równoległym polu obliczeniowym.
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.