Informatyka

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

1
Współczynnik rozstrzygalnych problemów
Rozważ problemy decyzyjne sformułowane w jakimś „rozsądnym” języku formalnym. Powiedzmy, że wzory w arytmetyce Peano wyższego rzędu z jedną wolną zmienną jako ramą odniesienia, ale równie interesują mnie inne modele obliczeń: równania diofantyczne, problemy słowne z przepisywania reguł za pomocą maszyn Turinga itp. Odpowiedź wyrażona w dowolnym klasyczna formalizacja byłaby …
1
Równoważność definicji złożoności Kołmogorowa
Istnieje wiele sposobów definiowania złożoności Kołmogorowa i zwykle wszystkie te definicje są równoważne do stałej addytywnej. To znaczy, jeśli K1K1K_1 i K2K2K_2 są funkcjami złożoności Kołmogorowa (zdefiniowanymi za pomocą różnych języków lub modeli), wówczas istnieje stała ccc taka, że ​​dla każdego łańcucha xxx , |K1(x)−K2(x)|&lt;c|K1(x)−K2(x)|&lt;c|K_1(x) - K_2(x)| < c . …
5
Skuteczna kompresja nieoznakowanych drzew
Rozważ nieoznakowane, ukorzenione drzewa binarne. Możemy skompresować takich drzew: gdy istnieją wskaźniki do poddrzew i T ' z T = T ' (ustne = jak równość strukturalne), możemy zapisać (wlog) T i zastąpić wszystkie wskaźniki do T ' z wskazówki dla T . Zobacz odpowiedź uli na przykład.T.TTT.′T′T'T.= T′T=T′T = …
2
Czy drzewa cięte łączem są kiedykolwiek wykorzystywane w praktyce do obliczeń maksymalnego przepływu lub innych zastosowań?
Wiele algorytmów maksymalnego przepływu, które zwykle widzę zaimplementowanych, algorytm Dinica, push push i inne, mogą mieć asymptotyczny koszt czasu ulepszony dzięki zastosowaniu dynamicznych drzew (znanych również jako drzewa cięte łączem). Wciśnij etykietę w trybie lub O ( V 3 ) lub O ( V 2 √)O ( V2)mi)O(V.2)mi)O(V^2E)O ( V3))O(V.3))O(V^3)normalnie, …
7
Dlaczego reprezentacja zmiennoprzecinkowa używa bitu znaku zamiast uzupełnienia 2 do wskazania liczb ujemnych
Rozważmy reprezentację punktu stałego, którą można uznać za zdegenerowany przypadek liczby zmiennoprzecinkowej. Całkowicie możliwe jest użycie uzupełnienia 2 dla liczb ujemnych. Ale dlaczego bit znaku jest potrzebny do liczb zmiennoprzecinkowych, czy bity mantysy nie powinny używać uzupełnień 2? Również dlaczego bity wykładnikowe używają odchylenia zamiast reprezentacji wielkości ze znakiem (podobnej …
1
Optymalny algorytm do znalezienia obwodu rzadkiego wykresu?
Zastanawiam się, jak znaleźć obwód rzadkiego nieukierunkowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.| mi| =O ( | V|)|mi|=O(|V.|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy …
4
Jakie wątki ogólnie się dzielą?
To jest ogólne pytanie. A jeśli ktoś chce sprecyzować tę implementację, wolę rzeczy związane z Uniksem. Ale najpierw trzeba znać następujące problemy w ogólności: Czytam, że pojedynczy proces może mieć wiele wątków. Wiele wątków tego samego procesu dzieli się między nimi. Chcę wiedzieć, co dzielą, a co nie. Biorąc pod …
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.