Informatyka

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

3
Obliczanie funkcji zajętego bobra
Funkcja maksymalnych przesunięć bobra zajętego, , ma znane wartości dla n ≤ 4 . Czy istnieje jakiś podstawowy, strukturalny powód, dla którego jest nie do pomyślenia, abyśmy kiedykolwiek znaleźli S ( n ) dla n > 4 ? Czym tak różni się n = 4 niż n = 5 ? …
3
P, NP i specjalistyczne maszyny Turinga
Jestem w pewnym sensie nowy, ale bardzo zainteresowany dziedziną obliczeń i teorii złożoności, i chcę wyjaśnić moje rozumienie, w jaki sposób klasyfikować problemy i jak silnie problemy odnoszą się do maszyny używanej do ich rozwiązywania. Moje zrozumienie Standardowa maszyna Turinga - maszyna Turinga, która ma skończony alfabet, skończoną liczbę stanów …
4
Algorytmy obliczające, jeśli liczba jest wielokrotnością liczby 3
Wykonując rachunek psychiczny, możesz: Biorąc pod uwagę liczbę całkowitą k, zsumuj wszystkie cyfry (w podstawie 10), a jeśli wynikiem jest wielokrotność 3, to k jest wielokrotnością 3. Czy znasz algorytm działający podobnie, ale działający na cyfrach binarnych (bitach)? Najpierw zastanawiałem się nad użyciem gotowych funkcji mojego języka konwertujących liczbę całkowitą …
13 algorithms 
4
Przejściowa redukcja DAG
Szukam algorytmu O (V + E) do znajdowania redukcji przechodnich przy danym DAG. To oznacza usunięcie jak największej liczby krawędzi, abyś mógł dosięgnąć v od ciebie, dla dowolnych v iu nadal możesz sięgnąć po usunięciu krawędzi. Jeśli jest to standardowy problem, proszę wskazać mi jakieś rozwiązanie modelowe.
13 algorithms  graphs  dag 
1
co to jest semantyka?
Istnieje wiele popularnych języków. Ale informatycy mówią nam, że aby zrozumieć zachowanie programów w tych językach, zdecydowanie i jednoznacznie spieramy się na zachowanie programu (np. Udowodnić ich tożsamość), musimy przetłumaczyć je na inny, dobrze zrozumiały język. Nazywają taki język „semantyką”. Autorzy proponują jedną z wielu semantyki. Wyjaśniają znaczenie ich konstrukcji …
1
Czy istnieje struktura danych dla semilattices podobna do struktury danych drzewa?
Jeśli uważamy drzewo za częściowo uporządkowany zbiór, staje się to szczególnym przypadkiem złączenia-semilattice. W przypadku semilattice złączenia chcemy być w stanie efektywnie obliczyć (unikatową) górną granicę dwóch elementów (mniej więcej). W przypadku drzewa, strukturą danych, która to umożliwiłaby, byłoby przechowywanie dla każdego elementu w odpowiednim węźle wskaźnika do elementu nadrzędnego …
1
Wygładzanie w modelu Naive Bayes
Naiwny predyktor Bayesa dokonuje swoich przewidywań, używając tej formuły: P.( Y= y| X= x ) = α P( Y= y) ∏jaP.( Xja= xja| Y= y)P.(Y=y|X=x)=αP.(Y=y)∏jaP.(Xja=xja|Y=y)P(Y=y|X=x) = \alpha P(Y=y)\prod_i P(X_i=x_i|Y=y) gdzie jest czynnikiem normalizującym. Wymaga to oszacowania parametrów P ( X i = x i | Y = y ) na …
2
Czy funkcje nieobliczalne stają się asymptotycznie większe?
Czytam o zajętych liczbach bobrów io tym, jak rosną one asymptotycznie większe niż jakakolwiek obliczalna funkcja. Dlaczego tak jest? Czy to z powodu niemożności obliczenia funkcji zajętego bobra? Jeśli tak, to czy wszystkie funkcje niepoliczalne stają się asymptotycznie większe niż funkcje obliczalne? Edytować: Świetne odpowiedzi poniżej, ale chciałbym wyjaśnić prostszym …
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.