Informatyka

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

9
Reprezentują liczbę rzeczywistą bez utraty precyzji
Bieżący zmiennoprzecinkowy (zmiennoprzecinkowy ANSI C, podwójny) pozwala przedstawić przybliżoną liczbę rzeczywistą. Czy istnieje sposób na przedstawienie liczb rzeczywistych bez błędów ? Oto pomysł, który miałem, ale nie idealny. Na przykład 1/3 to 0.33333333 ... (podstawa 10) lub o.01010101 ... (podstawa 2), ale także 0,1 (podstawa 3) Czy dobrym pomysłem jest …
3
Dlaczego Miller – Rabin zamiast testu pierwotności Fermata?
Z dowodu Millera-Rabina , jeśli liczba przechodzi test pierwotności Fermata , musi również przejść test Millera-Rabina z tą samą podstawą (zmienną w dowodzie). A złożoność obliczeń jest taka sama.zaaa Z testu pierwotności Fermata wynika : Chociaż liczby Carmichaela są znacznie rzadsze niż liczby pierwsze, 1 jest ich wystarczająco dużo, aby …
2
Czy możemy skonstruować redukcję Karp z redukcji Cooka między problemami NP?
Mieliśmy kilka pytań na temat relacji redukcji Cooka i Karp . Oczywiste jest, że redukcje Cooka (redukcje Turinga w czasie wielomianowym) nie definiują tego samego pojęcia kompletności NP jak redukcje Karp (redukcje w postaci wielomianu w jednym czasie), które są zwykle stosowane. W szczególności redukcje Cooka nie mogą oddzielić NP …
3
Po co używać języków w teorii złożoności
Właśnie zaczynam wchodzić w teorię obliczeń, która bada, co można obliczyć, jak szybko, z wykorzystaniem ilości pamięci iz jakim modelem obliczeniowym. Mam dość podstawowe pytanie, ale naprawdę mam nadzieję, że niektórzy z was pomogą mi zrozumieć koncepcję: Dlaczego wszystko koncentruje się wokół pojęcia i definicji JĘZYKÓW (tj. Języków zwykłych i …
1
Krótki i sprytny dowód silnego twierdzenia o dualności dla programowania liniowego
Rozważ programy liniowe Primal:Ax⃗ ≤b⃗ maxc⃗ Tx⃗ Primal:Ax→≤b→maxc→Tx→\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} Dual:c⃗ ≤y⃗ TAminy⃗ Tb⃗ Dual:c→≤y→TAminy→Tb→\begin{array}{|ccc|} \hline Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} & \min \vec{y}^T\vec{b} \\ \hline \end{array} Twierdzenie o słabym dualności mówi, że jeśli i spełniają ograniczenia, to …
2
Jak omawiać współczynniki w notacji big-O
Jakiej notacji używa się do omawiania współczynników funkcji w notacji big-O? Mam dwie funkcje: f(x)=7x2+4x+2f(x)=7x2+4x+2f(x) = 7x^2 + 4x +2 g(x)=3x2+5x+4g(x)=3x2+5x+4g(x) = 3x^2 + 5x +4 Oczywiście obie funkcje to , a właściwie Θ ( x 2 ) , ale to nie pozwala na dalsze porównania. Jak omówić współczynniki 7 …
2
Jasny, kompletny, dowód na to, że język jest konkurencyjny w Turingu?
Widziałem strony internetowe, które rzekomo „dowodzą”, że HTML5 + CSS jest Turing Complete. Widziałem strony internetowe, które rzekomo „dowodzą”, że SQL jest Turing Complete. Widziałem kilka stron internetowych, które rzekomo „wyjaśniają”, co to znaczy być Turing Complete. Wystarczająco! Gdzie mogę znaleźć książkę (napisaną przez eksperta w dziedzinie teorii obliczeń) lub …
4
Przykład algorytmu, w którym element wykonawczy niskiego rzędu dominuje w środowisku wykonawczym dla jakichkolwiek praktycznych danych wejściowych?
Notacja Big-O ukrywa stałe współczynniki, więc istnieją pewne algorytmy O(n)O(n)O(n) , które są niewykonalne dla jakiegokolwiek rozsądnego rozmiaru wejściowego, ponieważ współczynnik na jest tak duży.nnn Czy są jakieś znane algorytmy, których środowisko wykonawcze to ale z jakimś niskim terminem, który jest tak ogromny, że dla rozsądnych wielkości wejściowych całkowicie dominuje …
3
Jaka struktura danych skutecznie przechowuje zakresy liczb całkowitych?
Muszę przechowywać kolekcję liczb całkowitych z zakresu od 0 do 65535, aby móc szybko wykonać następujące czynności: Wstaw nową liczbę całkowitą Wstaw zakres ciągłych liczb całkowitych Usuń liczbę całkowitą Usuń wszystkie liczby całkowite poniżej liczby całkowitej Sprawdź, czy występuje liczba całkowita Moje dane mają tę właściwość, że często zawierają ciągi …
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.