Informatyka

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

5
Czy przyszłe komputery kwantowe będą korzystać z binarnego, trójskładnikowego lub czwartorzędowego układu liczbowego?
Nasze obecne komputery używają bitów, więc używają systemu liczb binarnych. Ale słyszałem, że przyszłe komputery kwantowe będą używać kubitów zamiast prostych bitów. Ponieważ w słowie „qubit” znajduje się słowo „bi”, najpierw pomyślałem, że oznacza to, że komputery kwantowe będą używać binarnych (podstawa 2). Ale potem usłyszałem, że kubity mają trzy …
2
Zgadywanie najmniejszej unikalnej dodatniej liczby całkowitej
Rozważmy następującą grę: jest kilku graczy i komputer. Każdy gracz wprowadza jedną dodatnią liczbę całkowitą i swoje imię (gracz nie zna liczb innych, tylko własne). Gdy wszyscy gracze wykonają ruchy, komputer generuje imię zwycięzcy - który podał najniższy unikalny numer. Jak myślisz, jaka jest najlepsza strategia dla tej gry?
2
Liczba możliwych ścieżek wyszukiwania podczas wyszukiwania w BST
Mam następujące pytanie, ale nie mam na to odpowiedzi. Byłbym wdzięczny, jeśli moja metoda jest poprawna: P: Podczas wyszukiwania wartości klucza 60 w drzewie wyszukiwania binarnego węzły zawierające wartości klucza 10, 20, 40, 50, 70, 80, 90 są przemieszczane, niekoniecznie w podanej kolejności. Ile jest możliwych różnych zamówień, w których …
4
Dlaczego w Regexach nie ma permutacji? (Nawet jeśli wydaje się, że zwykłe języki to potrafią)
Problem Nie ma łatwego sposobu na uzyskanie permutacji za pomocą wyrażenia regularnego. Permutacja: Uzyskanie słowa („aabc”) w innym porządku, bez zmiany liczby lub rodzaju liter.w=x1…xnw=x1…xnw=x_1…x_n Regex: wyrażenie regularne. Dla weryfikacji: „Permutacje regexów bez powtórzeń” Odpowiedź tworzy kod JavaScript zamiast wyrażenia regularnego, zakładając, że byłoby to prostsze. „Jak znaleźć wszystkie permutacje …
2
MIN-2-XOR-SAT i MAX-2-XOR-SAT: czy są NP-twarde?
Jaka jest złożoność MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} i MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Czy są w P? Czy są twarde NP? Aby sformalizować to dokładniej, pozwól Φ(x)=∧niCi,Φ(x)=∧jandoja,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, gdzie x=(x1,…,xm)x=(x1,…,xm)\mathbf{x} = (x_1,\dots,x_m) a każda klauzula CiCiC_i ma postać (xi⊕xj)(xi⊕xj)(x_i \oplus x_j) lub (xi⊕¬xj)(xi⊕¬xj)(x_i \oplus \neg x_j) . Problem 2-XOR-SAT2-XOR-SAT\text{2-XOR-SAT} polega na znalezieniu przypisania do xx\mathbf{x} które …
2
Czy można rozwiązać dowolny problem NP-Complete przy użyciu co najwyżej przestrzeni wielomianowej (ale przy użyciu czasu wykładniczego?)
Czytam o NPC i jego związku z PSPACE i chcę wiedzieć, czy problemy NPC można rozwiązać w sposób deterministyczny za pomocą algorytmu o najgorszym przypadku wymaganej przestrzeni wielomianowej, ale potencjalnie zajmującego wykładniczy czas (2 ^ P (n), gdzie P jest wielomianem). Co więcej, czy można ją ogólnie uogólnić na EXPTIME …
3
Dlaczego pusty symbol nie jest uważany za część alfabetu wejściowego maszyny Turinga?
Definicje maszyn Turinga zawsze wyrażają jasno, że pusty symbol nie jest częścią alfabetu wejściowego. Zastanawiam się, co poszło nie tak, kiedy byłoby uczynić go częścią alfabetu wejściowego, ponieważ skutecznie pusty symbol już wydaje się być częścią wejścia. Aby wyjaśnić, że „wydaje się” w ostatnim zdaniu, rozważ następujące kwestie. W ustawieniach …
3
Jakie inne języki programowania oprócz Pythona i poprzednika są dostępne przy użyciu wcięć do definiowania bloków kodu? [Zamknięte]
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było tematem dotyczącym wymiany stosów w informatyce. Zamknięte 11 miesięcy temu . Python dość dobrze wykorzystuje wcięcia do syntaktycznego definiowania bloków kodu. (Zobacz Instrukcje złożone w Skorowidzu języka Python). Po latach …
2
Faktoryzacji słowo w Czas
Biorąc pod uwagę dwa ciągi , piszemy dla ich konkatenacji. Biorąc pod uwagę ciąg i liczba całkowita , napisać dla złączonych kopii . Teraz biorąc pod uwagę ciąg, możemy użyć tego zapisu do „skompresowania” go, tzn. można zapisać jako . Nazwijmy ten ciężar kompresji liczba znaków w niej występujących, więc …
4
Co oznacza wiodący operator kołowrotu?
Wiem, że różni autorzy używają różnych notacji do reprezentacji semantyki języka programowania. W rzeczywistości Guy Steele rozwiązuje ten problem w ciekawym filmie . Chciałbym wiedzieć, czy ktoś wie, czy wiodący operator bramki obrotowej ma dobrze rozpoznane znaczenie. Na przykład nie rozumiem wiodącego operatora na początku mianownika:⊢⊢\vdash x:T1⊢t2:T2⊢λx:T1.t2 : T1→T2x:T.1⊢t2):T.2)⊢λx:T.1.t2) : …
2
Problemy, które wydają się wykładnicze, ale są P
Próbuję zbudować listę algorytmów / problemów, które są „wyjątkowo przydatne”, jak w przypadku rozwiązywania problemów, które „wydają się” z natury bardzo wykładnicze, ale mają jakiś szczególnie sprytny algorytm, który ostatecznie je rozwiązuje. Przykłady tego, co mam na myśli: Programowanie liniowe (algorytm simpleksowy jest czasem wykładniczym; znalezienie rozwiązania wielomianowego czasu zajęło …
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.