Informatyka

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

5
Jak udowodnić, że problem NIE jest NP-Complete?
Czy istnieje jakaś ogólna technika dla udowodnienia, że ​​problem NIE jest NP-Complete? Dostałem to pytanie na egzaminie, które poprosiło mnie o wykazanie, czy jakiś problem (patrz poniżej) jest NP-Complete. Nie mogłem wymyślić żadnego prawdziwego rozwiązania, a właśnie udowodniłem, że było w P. Oczywiście nie jest to prawdziwa odpowiedź. NP-Complete jest …
2
Jaka jest różnica między abstrakcyjnymi a konkretnymi strukturami danych?
Myślałem asocjacyjną (tj mapie lub słownika) i tabela mieszania były takie same pojęcia, dopóki nie zobaczyłem w Wikipedii tym W przypadku słowników z bardzo małą liczbą powiązań sensowne może być zaimplementowanie słownika przy użyciu listy powiązań, połączonej listy powiązań. ... Najczęściej stosowaną implementacją tablicy asocjacyjnej ogólnego przeznaczenia jest tablica skrótów: …
3
Liczba słów w zwykłym języku
Według Wikipedii , dla każdego zwykłego języka istnieją stałe i wielomiany takie, że dla każdego liczby słów o długości w spełnia równanieLLLλ1,…,λkλ1,…,λk\lambda_1,\ldots,\lambda_kp1(x),…,pk(x)p1(x),…,pk(x)p_1(x),\ldots,p_k(x)nnnsL(n)sL(n)s_L(n)nnnLLL sL(n)=p1(n)λn1+⋯+pk(n)λnksL(n)=p1(n)λ1n+⋯+pk(n)λkn\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n . Język L={02n∣n∈N}L={02n∣n∈N}L =\{ 0^{2n} \mid n \in\mathbb{N} \} jest zwykły ( (00)∗(00)∗(00)^* pasuje do niego). sL(n)=1sL(n)=1s_L(n) = 1 iff n jest parzyste, a sL(n)=0sL(n)=0s_L(n) …
5
Czy interakcja ma większą moc niż algorytmy?
Słyszałem motto oddziaływanie jest silniejsze niż algorytmów z Peterem Wegner . Podstawą tego pomysłu jest to, że (klasyczna) Maszyna Turinga nie jest w stanie poradzić sobie z interakcją, to znaczy komunikacją (wejście / wyjście) ze światem zewnętrznym / środowiskiem. Jak to może być tak? Jak coś może być mocniejsze niż …
4
Czy problem grafu skończonego jest rozstrzygalny? Jakie czynniki decydują o problemie?
Chcę wiedzieć, czy można rozwiązać następujący problem i jak się dowiedzieć. W każdym problemie, który widzę, mogę powiedzieć „tak” lub „nie”, więc czy większość problemów i algorytmów można rozstrzygać, z wyjątkiem kilku (które podano tutaj )? Wejście: kierowane i skończonych wykres z i , jak wierzchołki Pytanie: Czy ścieżką w …
3
Książka z przepisami dla kodowań SAT?
Solwery SAT stają się coraz bardziej wydajne w rozwiązywaniu dużych instancji i są używane jako zaplecze w różnych kontekstach. Za każdym razem, gdy chce się ich użyć do rozwiązania problemu w określonej domenie, musi wymyślić kodowanie ad-hoc, które nie tylko ma odpowiedni zestaw rozwiązań, ale także nakłada ograniczenia (nawet nadmiarowe) …
7
Jak zbudować bramę XOR przy użyciu tylko 4 bramek NAND?
xorbrama, teraz muszę zbudować tę bramę, używając tylko 4 nandbram a b out 0 0 0 0 1 1 1 0 1 1 1 0 the xor = (a and not b) or (not a and b), czyli A¯¯¯¯B+AB¯¯¯¯A¯B+AB¯\begin{split}\overline{A}{B}+{A}\overline{B}\end{split} Znam odpowiedź, ale jak uzyskać schemat bramy ze wzoru? EDYTOWAĆ Mam …
1
Spójność pamięci a spójność pamięci podręcznej
Czy to prawda, że ​​spójność sekwencyjna jest silniejszą właściwością niż spójność pamięci podręcznej? Według Sorin, Daniel J; Hill, Mark D; Wood, David A: A Primer on Memory Consistency and Cache Coherence , Morgan & Claypool, 2011 sekwencyjną spójność można opisać jako (nie formalnie): Model pamięci spójności sekwencyjnej określa, że ​​system …
4
Dlaczego nie używamy szybkiego sortowania na połączonej liście?
Algorytm szybkiego sortowania można podzielić na następujące kroki Zidentyfikuj oś przestawną. Podziel listę połączoną na partycje na podstawie przestawnej. Podziel listę połączoną rekurencyjnie na 2 części. Teraz, jeśli zawsze wybieram ostatni element jako oś przestawną, wówczas identyfikacja elementu przestawnego (1. krok) zajmuje czas.O ( n )O(n)\mathcal O(n) Po zidentyfikowaniu elementu …
4
Dlaczego szyfrowanie RSA stało się popularne przy wymianie kluczy?
To delikatne pytanie. Nie wiem dużo o kryptografii ani jej historii, ale wydaje się, że powszechnym zastosowaniem RSA jest wymiana kluczy poprzez szyfrowanie klucza symetrycznego w celu wysłania dłuższej wiadomości (np. Opis iMessage tutaj ). Czy nie do tego właśnie służy wymiana kluczy Diffie-Hellmana, która jest starsza (i wydaje mi …
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.