Informatyka

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

3
Studiowanie teorii języka programowania
Ostatnio bardzo się zainteresowałem zrozumieniem i sprawdzeniem aspektów (funkcjonalnych) języków programowania. Jednak gdy zagłębiam się głębiej, rzeczy takie jak rachunek , teoria kategorii i semantyka denotacyjna są nieco trudne do odczytania bez odpowiedniego wyjaśnienia.λλ\lambda Czytam SICP (całkiem pouczającą książkę), ale chcę zagłębić się w teorię programowania funkcjonalnego. Czy są jakieś …
3
Algorytm Brzozowskiego do minimalizacji DFA
Algorytm minimalizacji DFA Brzozowskiego buduje minimalny DFA dla DFA poprzez:GGG odwrócenie wszystkich krawędzi w , czyniąc stan początkowy stanem akceptacyjnym, a stanami początkowymi początkowymi, aby otrzymać NFA N ' dla języka odwrotnego,GGGN′N′N' używając konstrukcji powerset, aby uzyskać dla języka odwrotnego,G′G′G' odwrócenie krawędzi (i zamiana początkowej akceptacji) w aby uzyskać NFA …
4
Quicksort wyjaśnił dzieciom
W ubiegłym roku czytałem fantastyczny artykuł na temat „Mechaniki kwantowej dla przedszkola” . To nie był łatwy papier. Zastanawiam się teraz, jak wytłumaczyć quicksort w najprostszych możliwych słowach. Jak mogę udowodnić (lub przynajmniej falę ręczną), że średnia złożoność wynosi i jakie są najlepsze i najgorsze przypadki dla klasy przedszkolnej? A …
3
Język nieskończony a język skończony
Nie jestem pewien, czy w teorii komputerowej używa się zwrotów „nieskończony” język lub „skończony” język. Myślę, że źródłem problemu jest to, że język taki jak jest nieskończony w tym sensie, że może wygenerować nieskończoną (ale policzalną) liczbę łańcuchów. Jednak nadal może być rozpoznany przez automat skończony .L = { a …
6
Dlaczego DFS nie może być używany do znajdowania najkrótszych ścieżek na nieważonych wykresach?
Rozumiem, że użycie DFS „tak jak jest” nie znajdzie najkrótszej ścieżki na nieważonym wykresie. Ale dlaczego poprawianie DFS, aby umożliwić mu znajdowanie najkrótszych ścieżek na nieważonych wykresach, jest tak beznadziejną perspektywą? Wszystkie teksty na ten temat po prostu stwierdzają, że nie można tego zrobić. Nie jestem przekonany (sam tego nie …
1
Splot 2D: Przerzucanie jądra?
Dlaczego w pierwszej kolejności musimy przerzucać jądro w trybie splotu 2D? Jaka jest z tego korzyść? Dlaczego więc nie możemy pozostawić tego nieprzypiętego? http://www.songho.ca/dsp/convolution/convolution2d_example.html Wejście jądro wynik „Najpierw odwróć jądro, które jest zacienionym pudełkiem, zarówno w kierunku poziomym, jak i pionowym”
5
Maszyna Turinga + dylatacja czasu = rozwiązać problem zatrzymania?
Istnieją relatywistyczne czasoprzestrzenie (np. Czasoprzestrzenie MH; patrz Hogarth 1994), w których linia świata o nieskończonym czasie trwania może być zawarta w przeszłości skończonego obserwatora. Oznacza to, że normalny obserwator może mieć dostęp do nieskończonej liczby kroków obliczeniowych. Zakładając, że komputer może funkcjonować idealnie przez nieskończony czas (i wiem, że to …
2
Czym jest ta struktura / koncepcja danych, w której wykres punktów definiuje podział na przestrzeń
Zetknąłem się z algorytmem rozwiązywania rzeczywistego problemu i pamiętam klasę, w której wziąłem udział, gdzie zrobiłem coś bardzo podobnego dla niektórych na zadanie domowe. Zasadniczo jest to wykres punktów, a linie są rysowane tak, aby były w równej odległości między dwoma punktami. Tworzy idealną przegrodę, w której linie wokół punktu …
1
NP-zupełny problem z wielomianową liczbą tak-wystąpień?
Mam wrażenie, że dla każdego problemu NP-zupełnego, dla nieskończenie wielu rozmiarów wejściowych , liczba wystąpień tak we wszystkich możliwych wejściach wielkości jest (przynajmniej) wykładnicza w n .nnnnnnnnn Czy to prawda? Czy można to udowodnić (prawdopodobnie tylko przy założeniu, że P.≠ N.P.P.≠N.P.P\neq NP )? A może sztucznie możemy znaleźć problem, w …
8
Kardynalność zbioru algorytmów
Ktoś w dyskusji przywołał, że (uważa) może istnieć co najmniej ciągła liczba strategii podejścia do określonego problemu. Specyficznym problemem były strategie handlowe (nie algorytmy, ale strategie), ale myślę, że to nie ma znaczenia dla mojego pytania. To sprawiło, że pomyślałem o liczności zbioru algorytmów. Trochę szukałem, ale nic nie wymyśliłem. …
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.