Informatyka

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

3
Jakie jest krótkie, ale pełne wyjaśnienie czystego / zależnego systemu typów?
Jeśli coś jest proste, powinno być całkowicie wyjaśnione kilkoma słowami. Można to zrobić dla rachunku λ: Rachunek λ jest gramatyką składniową (w zasadzie strukturą) z regułą redukcji (co oznacza, że ​​procedura wyszukiwania / zamiany jest wielokrotnie stosowana do każdego wystąpienia określonego wzorca, dopóki taki wzorzec nie istnieje). Gramatyka: Term = …
2
Co to są bardzo krótkie programy o nieznanym statusie zatrzymania?
Ten 579-bitowy program w Binary Lambda Calculus ma nieznany status zatrzymania: 01001001000100010001000101100111101111001110010101000001110011101000000111001110 10010000011100111010000001110011101000000111001110100000000111000011100111110100 00101011000000000010111011100101011111000000111001011111101101011010000000100000 10000001011100000000001110010101010101010111100000011100101010110000000001110000 00000111100000000011110000000001100001010101100000001110000000110000000100000001 00000000010010111110111100000010101111110000001100000011100111110000101101101110 00110000101100010111001011111011110000001110010111111000011110011110011110101000 0010110101000011010 Oznacza to, że nie wiadomo, czy ten program się zakończy, czy nie. Aby to ustalić, musisz rozwiązać hipotezę Collatza - lub przynajmniej dla wszystkich liczb do 2 ^ 256. W tym …
3
Algorytm wykrywania cyklu Floyda Określenie punktu początkowego cyklu
Szukam pomocy w zrozumieniu algorytmu wykrywania cyklu Floyda. Przeszedłem wyjaśnienie na Wikipedii ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare ) Widzę, jak algorytm wykrywa cykl w czasie O (n). Nie jestem jednak w stanie wyobrazić sobie, że kiedy wskaźniki żółwia i zająca spotkają się po raz pierwszy, początek cyklu można ustalić, przesuwając wskaźnik żółwia z …
2
Dlaczego zwykły język nazywa się „zwykłym”?
Właśnie zakończyła pierwszy rozdział Wprowadzenie do teorii obliczeń przez Michaela Sipser który wyjaśnia podstawy automatów skończonych. Definiuje zwykły język jako wszystko, co można opisać za pomocą automatów skończonych. Ale nie mogłem znaleźć, gdzie tłumaczy, dlaczego zwykły język nazywa się „zwykłym”. Jakie jest pochodzenie terminu „regularny” w tym kontekście? UWAGA: Jestem …
5
Znajdowanie interesujących anagramów
Powiedzieć, że 1 2 ... n i są dwa ciągi o tej samej długości. Anagramming dwóch ciągów bijective mapowania tak, że dla każdego .a1a2…ana1a2…ana_1a_2\ldots a_nb1b2…bnb1b2…bnb_1b_2\ldots b_np:[1…n]→[1…n]p:[1…n]→[1…n]p:[1\ldots n]\to[1\ldots n]ai=bp(i)ai=bp(i)a_i = b_{p(i)}iii Może być więcej niż jedno anagramowanie dla tej samej pary ciągów. Na przykład, jeśli `abcab` mamy i , między innymi.a=a=a=b=b=b=cababp1[1,2,3,4,5]→[4,5,1,2,3]p1[1,2,3,4,5]→[4,5,1,2,3]p_1[1,2,3,4,5]\to[4,5,1,2,3]p2[1,2,3,4,5]→[2,5,1,4,3]p2[1,2,3,4,5]→[2,5,1,4,3]p_2[1,2,3,4,5] …
2
Jaka jest różnica między drzewami radix a próbami Patricii?
Uczę się o drzewach Radix (inaczej skompresowanych próbach) i Patricii, ale znajduję sprzeczne informacje na temat tego, czy faktycznie są one takie same. Drzewo radix można uzyskać z normalnej (nieskompresowanej) trie, łącząc węzły z ich rodzicami, gdy węzły są jedynym dzieckiem. Dotyczy to również prób Patricii. W jaki sposób dwie …
2
Symulowanie prawdopodobieństwa 1 z 2 ^ N przy mniej niż N losowych bitach
Powiedz, że muszę zasymulować następujący rozkład dyskretny: P(X=k)={12N,1−12N,if k=1if k=0P(X=k)={12N,if k=11−12N,if k=0 P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} Najbardziej oczywistym sposobem jest narysowanie losowych bitów i sprawdzenie, czy wszystkie są równe (lub ). Jednak teoria …
2
Dlaczego uważamy, że PSPACE ≠ EXPTIME?
Mam problem z intuicyjnym zrozumieniem, dlaczego ogólnie uważa się, że PSPACE różni się od EXPTIME. Jeśli PSPACE jest zbiorem problemów możliwych do rozwiązania w wielomianu kosmicznym w wielkości wejściowej fa( n )f(n)f(n) , to w jaki sposób może istnieć klasa problemów, które doświadczają większego wybuchu czasu wykładniczego i nie wykorzystują …
2
NP-Trudne problemy, których nie ma w NP, ale są rozstrzygalne
Zastanawiam się, czy istnieje dobry przykład łatwego do zrozumienia problemu NP-Hard, który nie jest NP-Complete i nie jest nierozstrzygalny? Na przykład problem zatrzymania jest NP-trudny, a nie NP-kompletny, ale jest nierozstrzygalny. Uważam, że oznacza to, że problem można zweryfikować, ale nie w czasie wielomianowym. (Proszę poprawić to oświadczenie, jeśli tak …
4
Jak mogę zweryfikować rozwiązanie problemu Traveling Salesman w czasie wielomianowym?
Tak więc problem decyzyjny TSP (problem sprzedawcy podróży) jest NP kompletny . Ale nie rozumiem, w jaki sposób mogę sprawdzić, czy dane rozwiązanie TSP jest w rzeczywistości optymalne w czasie wielomianowym, biorąc pod uwagę, że nie ma sposobu na znalezienie optymalnego rozwiązania w czasie wielomianowym (co jest spowodowane tym, że …
5
Dodawanie elementów do posortowanej tablicy
Jaki byłby najszybszy sposób na zrobienie tego (z punktu widzenia algorytmu, a także ze względów praktycznych)? Myślałem o czymś następującym. Mógłbym dodać na końcu tablicy, a następnie użyć bąbelkowego sortowania, ponieważ ma najlepszy przypadek (tablica całkowicie posortowana na początku), który jest zbliżony do tego i ma liniowy czas działania (w …
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.