Pół dekady temu siedziałem w klasie struktur danych, w której profesor oferował dodatkowy kredyt, jeśli ktokolwiek mógł przemierzać drzewo bez użycia rekurencji, stosu, kolejki itp. (Lub innych podobnych struktur danych) i tylko kilka wskazówek. Wpadłem na to, co uważałem za oczywistą odpowiedź na...
Próbuję przygotować się do egzaminu i zdałem sobie sprawę, że nie jestem pewien, jak działa TLB i pamięć podręczna danych. Rozumiem, że TLB jest zasadniczo pamięcią podręczną ostatnio używanych adresów fizycznych. Jednak patrzyłem na diagram w moim podręczniku (pokazany poniżej) i nie rozumiem, co...
Klika problem jest znany -Complete problemem przy czym wielkość wymaganej klika jest częścią wejścia. Jednak problem kliki k ma trywialny wielomianowy algorytm czasu ( O ( n k ), gdy k jest stałe). Interesują mnie najlepiej znane górne granice, gdy k jest stałe.NPNPNPO(nk)O(nk)O(n^k)kkk Czy...
Z tego, czego się nauczyłem, asymptotycznie ścisłe wiązanie oznacza, że jest ono wiązane od góry i od dołu jak w notacji theta. Ale co oznacza asymptotycznie ciasna górna granica dla notacji
Zdefiniuj język jako . Innymi słowy, zawiera słowa, których nie można wyrazić jako jakieś słowo powtórzone dwukrotnie. Czy bezkontekstowy czy nie?LLLL={a,b}∗−{ww∣w∈{a,b}∗}L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}LLLLLL Próbowałem przeciąć z , ale nadal nie mogę niczego...
Próbuję skonstruować wszystkie nierówne macierze (lub n × n, jeśli chcesz) z elementami 0 lub 1. Operacją, która daje macierze równoważne, jest jednoczesna wymiana wiersza i i j ORAZ kolumny i i j. na przykład. dla 1 ↔ 2 ( 0 0 0 0 1 1 1 0 0 ) ∼ ( 1 0 1 0 0 0 0 1 0 )8 × 88×88\times 8n × nn×nn\times...
Wiem, że można udowodnić, że PROLOG jest kompletny z Turinga, tworząc program symulujący maszynę Turinga w następujący sposób: turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :-...
Próbuję owinąć głowę wokół dowodu kompletności NP, który wydaje się obracać wokół SAT / 3CNF-SAT. Może jest późna godzina, ale obawiam się, że nie mogę wymyślić formuły 3CNF, której nie można spełnić (prawdopodobnie brakuje mi czegoś oczywistego). Czy możesz podać mi przykład takiej...
Mam czworościanu oraz graniastosłupa . jest tak ograniczony, że zawsze dzieli wszystkie swoje wierzchołki z . Chcę ustalić, czy leży wewnątrz .ttt t p tppptttpppttt ppp Chciałbym dodać jeden szczegół do problemu, w przypadku gdy może on przyczynić się do rozwiązania: jest czworościanem Delaunaya,...
Jestem zdezorientowany, dlaczego projektanci MIPS mieliby 5 bitów poświęconych przesunięciu i mieli osobne bity opcodu i funkcji. Ponieważ MIPS jest tak RYZYKO, zakładam, że tylko kilka przesunięć można by wykonać w kilku instrukcjach, więc te 5 bitów wydaje się marnować miejsce, gdy można je...
Niektóre procesory mają rejestr flag (ARM, x86, ...), inne nie (MIPS, ...). Jaka jest zaleta posiadania instrukcji CMP do aktualizacji rejestru flag, a następnie instrukcji gałęzi zamiast używania rejestru zerowego i gałęzi warunkowych do sprawdzania znaku, przepełnienia
Układanka „Flow Flow” składa się z dodatniej liczby całkowitej i zestawu (nieuporządkowanych) par odrębnych wierzchołków na wykresie siatki tak że każdy wierzchołek zawiera co najwyżej jedną parę. Rozwiązaniem takiej układanki jest zestaw niekierowanych ścieżek na wykresie, dzięki czemu każdy...
Możliwe jest parsowanie dokumentu za pomocą pojedynczego przejścia z automatu stanów. Jaka jest korzyść z dwóch przejść, tj. posiadanie leksera do konwersji tekstu na tokeny i parsera do testowania reguł produkcyjnych dla tych tokenów? Dlaczego nie mieć pojedynczego przejścia, które stosuje reguły...
Czytam Algebrę liniową i jej aplikacje, aby pomóc w zrozumieniu materiałów informatycznych (głównie uczenia maszynowego), ale martwię się, że wiele informacji nie jest użytecznych dla CS. Na przykład wiedza o tym, jak skutecznie rozwiązywać układy równań liniowych, nie wydaje się bardzo przydatna,...
Ostatniej jesieni wybrałem się na wycieczkę po superkomputerze Blue Waters na University of Illinois. Zapytałem, czy ktoś kiedykolwiek korzystał z całego komputera. Powiedziano mi, że zawsze pracował nad wieloma projektami. To sprawiło, że zastanawiałem się nad przydatnością superkomputerów. Być...
W moim podręczniku wspomniano, że: gdzie to pusty język.∅∅∗={ϵ}∅∗={ϵ}\emptyset^*=\{\epsilon\}∅∅\emptyset Wiemy jednak, że , gdzie to dowolny język.L⋅∅=∅L⋅∅=∅L \cdot \emptyset = \emptysetLLL Nie jestem w stanie intuicyjnie zrozumieć tej koncepcji, ponieważ operacja gwiazdy Kleene wskazuje na fakt,...
Co oznacza ?logO(1)nlogO(1)n\log^{O(1)}n Jestem świadomy notacji wielkiej-O, ale ta notacja nie ma dla mnie sensu. Nie mogę też nic na ten temat znaleźć, ponieważ wyszukiwarka nie ma możliwości prawidłowej interpretacji tego. W pewnym kontekście zdanie, w którym znalazłem, brzmi „[...] nazywamy...
Pseudo-wielomianowy algorytm czasu jest algorytmem, który ma wielomianowy czas działania na wartości wejściowej (wielkość), ale wykładniczy czas działania na wielkości wejściowej (liczba bitów). Na przykład sprawdzenie, czy liczba jest liczbą pierwszą, czy nie, wymaga przejścia przez liczby od 2...
W artykule Philipa Wadlera na temat Twierdzeń za darmo stwierdza w części 2, że parametryczność, że nie ma naiwnych teoretycznych modeli polimorficznego rachunku lambda W naiwnym modelu teoretycznym zestawu typy są zestawami, a funkcje są funkcjami zestawu teoretycznego, co wydaje się...
Niech Σ={0,1}Σ={0,1}\Sigma = \{ 0, 1 \} . Język mówi się, że „anty-palindrom” własność jeśli każdy ciąg że jest palindrom, . Ponadto dla każdego łańcucha który nie jest palindromem, lub , ale nie oba (!) (Wyłączne lub).L⊆Σ∗L⊆Σ∗L \subseteq \Sigma^* wwww∉Lw∉Lw\notin Luuuu∈Lu∈Lu\in...