Wiem, że to bardzo częste pytanie. Ale mam inny punkt widzenia. Spróbuję to tutaj wyrazić. Z tego, co wiem, każda instrukcja wykonywana przez procesor jest w języku maszynowym i wszystko, co może zrobić, to wykonywanie operacji arytmetycznych dzięki ALU i jego tranzystorom (jeśli idziemy na...
Wiem, że bram NAND można używać do tworzenia obwodów, które implementują każdą tabelę prawdy, a nowoczesne komputery są zbudowane z bram NAND. Jaki jest teoretyczny związek między bramkami NAND a kompletnością Turinga? Wydaje mi się, że obwody bramki NAND są bliższe automatom skończonym niż maszyny...
Czytam tutaj o problemie z maksymalnym przepływem . Nie mogłem zrozumieć intuicji stojącej za wykresem rezydualnym. Dlaczego podczas obliczania przepływu bierzemy pod uwagę tylne krawędzie? Czy ktoś może mi pomóc zrozumieć pojęcie wykresu resztkowego? Jak zmienia się algorytm w niekierowanych...
Dobrze wiadomo, że 2-SAT znajduje się w P. Jednak wydaje się dość interesujące, że zliczanie liczby rozwiązań dla danej formuły 2-SAT, tj. # 2-SAT jest # P-trudne. Oznacza to, że mamy przykład problemu, dla którego decyzja jest łatwa, ale liczenie jest trudne. Ale rozważ arbitralny problem...
Podczas wykonywania drugiego kata kodu (który prosi pięć razy o zaimplementowanie algorytmu wyszukiwania binarnego, za każdym razem inną metodą), wpadłem na nieco inne rozwiązanie, które działa w następujący sposób: Jeśli mam posortowaną tablicę o długości 100 i widzę, że jej pole początkowe...
Właśnie przeczytałem Czy ten algorytm nadal może być uważany za algorytm wyszukiwania binarnego? i przypomniałem sobie, że kilka lat temu napisałem indeksatora / wyszukaj pliki dziennika, aby znaleźć wpisy dziennika w dużych plikach tekstowych według okna daty / godziny. Robiąc to, postanowiłem...
Czytam artykuł i w jego opisie złożoności czasowej napisano, że złożoność czasowa to .O~(22n)O~(22n)\tilde{O}(2^{2n}) Przeszukałem internet i wikipedię, ale nie mogę znaleźć tego, co oznacza tylda w notacji big-O / Landau. W samym artykule nie znalazłem też żadnych wskazówek na ten temat. Co...
Znam semantykę operacyjną (zarówno małą, jak i dużą) do definiowania języków programowania. Interesuje mnie również nauka semantyki denotacyjnej, ale nie jestem pewien, czy będzie to warte wysiłku. Czy po prostu będę uczyć się tego samego materiału z innego punktu widzenia, czy też są...
Mam problem z algorytmem. Biorąc pod uwagę macierz (lub zestaw) o nieujemne liczby całkowite. Znajdź maksymalny zestaw z tak że dla wszystkich ,.TT.TnnnSS.STT.Ta∈Sza∈S.a\in Sa⩾|S|za⩾|S.|a\geqslant |S| Na przykład: Jeśli TT.T = [1, 3, 4, 1, 3, 6], wówczas SS.S może być [3, 3, 6] lub [3, 4, 6]...
W Cormen et al .'s Wprowadzenie do algorytmów , sekcja 15.3 Elementy programowania dynamicznego wyjaśniają zapamiętywanie w następujący sposób: Zapamiętany algorytm rekurencyjny zachowuje pozycję w tabeli dla rozwiązania każdego podproblemu. Każdy wpis w tabeli początkowo zawiera specjalną...
Czy udowodniono, że obliczenia kwantowe nie są lepsze w rozwiązywaniu całkowitych problemów z NP niż obliczenia klasyczne, czy po prostu sądzi
Niektóre prace Conora McBride'a, Diff , Dissect , wiążą pochodną typów danych z ich „typem jednootworowych kontekstów”. Oznacza to, że jeśli weźmiesz pochodną typu, pozostanie ci typ danych, który pokazuje, jak typ danych wygląda od wewnątrz w danym punkcie. Na przykład, jeśli masz listę (w...
Zamknięte . To pytanie jest oparte na opiniach . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby można było na nie odpowiedzieć faktami i cytatami, edytując ten post . Zamknięte 2 lata temu . Zasadniczo programiści...
Mam na myśli to [zabawne] pytanie. Dlaczego niedeterministyczny automat skończony nazywa się niedeterministyczny, podczas gdy my definiujemy przejścia dla danych wejściowych. Cóż, mimo że istnieje wiele przejść i epsilon , są one zdefiniowane, co oznacza, że maszyna jest deterministyczna dla tych...
Czytałem tę książkę dla mojej klasy, Randomized Algorytmy. W tej książce znajduje się cała sekcja poświęcona znalezieniu mediany tablicy za pomocą losowego wyboru, co prowadzi do bardziej wydajnego algorytmu. Teraz chciałem wiedzieć, czy istnieją jakieś praktyczne zastosowania tego algorytmu w...
Jestem programistą z automatami, ale nie logiką. Przeczytałem w artykułach, że te dwa są ze sobą ściśle powiązane. Deterministyczne automaty skończone (DFA), automaty drzewa i automaty z widocznym przesunięciem w dół są powiązane z logiką Monadic drugiego rzędu (MSO). Chociaż rozumiem automaty i...
Znam ideę podstawowej eliminacji rekurencji ogona, w której funkcje, które zwracają bezpośredni wynik wywołania do siebie, można przepisać jako pętle iteracyjne. foo(...): # ... return foo(...) Rozumiem również, że jako szczególny przypadek funkcja może być nadal przepisana, jeśli wywołanie...
Czy są jakieś techniki rozwiązywania równań funkcyjnych dla nieznanych funkcji w rachunku lambda? Załóżmy, że mam funkcję tożsamości zdefiniowaną jako taką: Ix=xjax=xI x = x (czyli przez spisanie równanie dla oczekiwanego zachowania tej funkcji), a teraz chcę go rozwiązać za wykonując jakąś...
Jeśli dobrze to rozumiem, algorytm, który oblicza wartość rzeczywistej funkcji ma złożoność obliczeniową O ( g ( n ) ), jeśli zachowuje następujące warunki: Gdy obliczamy f z dokładnością δ, wymaga to rzędu g ( n ) kroków.faffO ( g( n ) )O(g(n))O(g(n))faffδδ\deltasol( n )g(n)g(n) Co jednak jeśli...
Czytałem o językach programowania opartych na stosie, takich jak FORTH i Cat , i wydaje się, że biorąc pod uwagę ich naturę, mogą one wykonywać tylko jedną akcję na raz, niezależnie od swojego paradygmatu (FORTH jest konieczny, a Cat funkcjonalny). Język imperatywny zmodyfikowałby stos, a język...