Informatyka

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

6
Czym różni się programowanie dynamiczne od siły Brute?
Czytałem o Programowaniu dynamicznym, kiedy natknąłem się na następujący cytat Algorytm programowania dynamicznego zbada wszystkie możliwe sposoby rozwiązania problemu i wybierze najlepsze rozwiązanie. Dlatego z grubsza możemy myśleć o programowaniu dynamicznym jako inteligentnej metodzie brutalnej siły, która pozwala nam przejść przez wszystkie możliwe rozwiązania, aby wybrać najlepsze . Jeśli zakres …
4
Jak pokazać, że „odwrócony” język regularny jest regularny
Utknąłem na następujące pytanie: „Zwykłe języki są dokładnie tymi, które są akceptowane przez automaty skończone. Biorąc pod uwagę ten fakt, pokaż, że jeśli język jest akceptowany przez jakiś automat skończony, wówczas jest również akceptowany przez niektóre skończone; składa się ze wszystkich słów z odwrócone. ”LLLLRLRL^{R}LRLRL^{R}LLL
1
Wydajne obliczanie lub przybliżanie wymiaru VC sieci neuronowej
Moim celem jest rozwiązanie następującego problemu, który opisałem na podstawie jego danych wejściowych i wyjściowych: Wejście: Kierunkowy wykres acykliczny z m węzłami, n źródłami i 1 ujściem ( m > n ≥ 1 ).GGGmmmnnn111m>n≥1m>n≥1m > n \geq 1 Wynik: VC wymiar (lub zbliżanie niego) dla sieci neuronowej z topologii .GGG …
5
Punkt stały, co to znaczy w świecie informatyki
Ciągle natrafiam na odniesienia do stałego punktu w pytaniach i odpowiedziach na stackexchange i szukam znaczenia w Internecie, oczywiście znajdując odnośniki na stronach takich jak Wikipedia. Jednak żadne z odniesień tak naprawdę nie odpowiada na moje pytanie, co jest stałym punktem i co to znaczy w świecie informatyki.
4
Cel szarego węzła w wyszukiwaniu na głębokości pierwszego wykresu
W wielu implementacjach pierwszego wyszukiwania głębokości, które widziałem (na przykład: tutaj ), kod rozróżnia szary wierzchołek (wykryty, ale nie odwiedzono wszystkich jego sąsiadów) i czarny wierzchołek (odkryty i odwiedzono wszystkich jego sąsiadów) . Jaki jest cel tego rozróżnienia? Wygląda na to, że algorytm DFS nigdy nie odwiedzi odwiedzonego wierzchołka, niezależnie …
5
Przykład algorytmu bez dowodu poprawności
Mamy logikę Hoare'a. Dlaczego wciąż jest możliwe, że algorytm ma rację, ale nie ma dowodów na jego poprawność? Załóżmy, że algorytm jest wyrażony w C. Następnie możemy argumentować krok po kroku, że robi to, co powinien. Więc moje pytanie brzmi: Podaj przykład algorytmu, który jest odpowiedni, ale nie ma dowodu …
2
Czym jest ta ułamkowa notacja „dyskretna matematyka” stosowana w formalnych regułach?
W artykule „Bezkonfliktowy zreplikowany typ danych JSON” napotkałem ten zapis do formalnego definiowania „reguł”: Jak nazywa się ten zapis? Jak to czytać? Na przykład: DOCreguła nie ma nic w „liczniku” - dlaczego nie? te EXECi GETzasady wydają się mieć dwa oddzielne terminy powyżej linii, co to znaczy? VARreguła wyróżnia się …
4
Dlaczego wykresy skierowane są ważne?
Chcesz poprawić ten post? Podaj szczegółowe odpowiedzi na to pytanie, w tym cytaty i wyjaśnienie, dlaczego Twoja odpowiedź jest poprawna. Odpowiedzi bez wystarczającej ilości szczegółów mogą być edytowane lub usuwane. Czytaliśmy o algorytmach dla MST, silnej łączności, routingu itp. W grafach ukierunkowanych. Ostatnio ludzie przeprowadzają badania nad algorytmami dynamicznymi i …
1
Czy minimalne cięcie może być łatwiejsze niż przepływ sieci?
Dzięki twierdzeniu o maksymalnym przepływie min-cut wiemy, że możemy użyć dowolnego algorytmu do obliczenia maksymalnego przepływu na grafie sieciowym do obliczenia -min-cut. Dlatego złożoność obliczenia minimum -cięcie jest nie większa niż złożoność obliczenia przepływu maksymalnego .( s , t )(s,t)(s,t)(s , t )(s,t)(s,t)(s , t )(s,t)(s,t) Czy może być mniej? …
5
Czy można rozwiązać problem zatrzymania, jeśli masz ograniczony lub przewidywalny wkład?
Problemu zatrzymania nie można rozwiązać w ogólnym przypadku. Można wymyślić zdefiniowane reguły, które ograniczają dozwolone dane wejściowe i czy problem zatrzymania można rozwiązać w tym szczególnym przypadku? Na przykład wydaje się prawdopodobne, że język, który nie dopuszcza na przykład pętli, bardzo łatwo będzie stwierdzić, czy program się zatrzyma, czy nie. …
1
Czy funkcja obliczalna może zbiegać się w liczbę nieobliczalną?
Czy istnieje funkcja obliczalna taka, że:f:N→Qf:N→Qf:\mathbb{N}\rightarrow \mathbb{Q} Dla wszystkicht∈N:0≤f(t)&lt;Xt∈N:0≤f(t)&lt;Xt\in\mathbb{N}: 0\le f(t) < X limt→∞f(t)=Xlimt→∞f(t)=X\lim\limits_{t\rightarrow\infty} f(t) = X Gdzie XXX jest nieobliczalną liczbą rzeczywistą. Jedyne odniesienie do tego pytania, które znalazłem, to odpowiedź na to pytanie : /math//a/1052579/168764 , gdzie wydaje się, że funkcja się utrzyma, ale nie mam pojęcia, jak …
5
Co oznacza szybszy algorytm w informatyce teoretycznej?
Jeśli istnieje algorytm działający w czasie O(f(n))O(f(n))O(f(n)) dla jakiegoś problemu A, a ktoś wymyśli algorytm działający w czasie, , gdzie , czy uważa się to za ulepszenie w stosunku do poprzedniego algorytmu?O(f(n)/g(n))O(f(n)/g(n))O(f(n)/g(n))g(n)=o(f(n))g(n)=o(f(n))g(n) = o(f(n)) Czy ma sens, w kontekście informatyki teoretycznej, wymyślić taki algorytm?
18 algorithms 
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.