Informatyka

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

2
Znajdowanie co najmniej dwóch ścieżek o tej samej długości na ukierunkowanym wykresie
Załóżmy, że mamy skierowany wykres i dwa węzły A i B . Chciałbym wiedzieć, czy istnieją już algorytmy do obliczania następującego problemu decyzyjnego:G = ( V, E)G=(V,E)G=(V,E)ZAAAbBB Czy istnieją co najmniej dwie ścieżki między i B o tej samej długości?ZAAAbBB Co powiesz na złożoność? Czy mogę to rozwiązać w czasie …
1
Czy każdy wystarczająco duży ciąg ma powtórzenia?
Niech będzie skończonym zestawem znaków o ustalonym rozmiarze. Niech będzie ciągiem znaków nad . Mówimy, że niepusty substrat z jest powtórzeniem, jeśli dla jakiegoś ciągu .α Σ β αΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaγβ= γγβ=γγ\beta = \gamma \gammaγγ\gamma Teraz moje pytanie dotyczy tego, czy: Dla każdego istnieje pewna liczba taka, że ​​dla każdego łańcucha powyżej …
1
Klasyfikacja trudnych do rozwiązania / możliwych do rozwiązania wariantów problemu satysfakcji
Ostatnio znalazłem w artykule [1] specjalną symetryczną wersję SAT o nazwie 2/2/4-SAT . Ale istnieje wiele wariantów kompletnych , na przykład: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NPNP\text{NP} Możliwe są inne warianty: - SAT , Planar-NAE- SAT , ...222SATSAT\text{SAT}SATSAT\text{SAT} Czy istnieją artykuły ankietowe (lub strony internetowe), które klasyfikują wszystkie (dziwne) …
1
Złożoność wież Hanoi
Wpadłem w następujące wątpliwości co do złożoności Towers of Hanoi , co do których chciałbym waszych komentarzy. Czy to jest w NP? Próba odpowiedzi: Załóżmy, że Peggy (przysłowie) rozwiązuje problem i przekazuje go Victorowi (weryfikatorowi). Victor łatwo widzi, że końcowy stan rozwiązania jest właściwy (w czasie liniowym), ale nie będzie …
4
Pomiar opóźnień sieci w jedną stronę
To jest łamigłówka na temat pomiaru opóźnienia sieci, którą stworzyłem. Wierzę, że rozwiązaniem jest to, że jest to niemożliwe, ale przyjaciele się nie zgadzają. Tak czy inaczej, szukam przekonujących wyjaśnień. (Choć jest to układanka, myślę, że pasuje do tej strony internetowej ze względu na jej przydatność w projektowaniu i doświadczeniu …
1
Czy istnieje istniejąca struktura danych o ustalonym rozmiarze, która wypchnie najstarszy / ostatni element, jeśli wstawiony zostanie nowy element?
Szukam struktury danych, która wypchnie jej najstarszy / ostatni element, jeśli wstawiony zostanie nowy element. Na przykład niech Dreprezentuje strukturę. Dzawiera 3 elementy Number Dwartości domyślnych tego typu będą inicjowane do 1, 2i 3. D=[1,2,3]D=[1,2,3]D = [1, 2, 3] Jeśli Numberto zawiera wartość 5jest włożona D, 3zostanie wypchnięty, natomiast 1i …
2
Czy istnieje nietrywialny typ, który jest równy jego własnej pochodnej?
Artykuł zatytułowany The Derivative of a Regular Type to Type One-Hole Contexts pokazuje, że „zamek błyskawiczny” typu - jego konteksty z jedną dziurą - są zgodne z regułami różnicowania w algebrze typów. Mamy: ∂xx∂x0∂x1∂x( S+ T)∂x( S× T)↦ 1↦ 0↦ 0↦ ∂xS.+ ∂xT.↦ ∂xS.× T+ S× ∂xT.∂xx↦1∂x0↦0∂x1↦0∂x(S+T)↦∂xS+∂xT∂x(S×T)↦∂xS×T+S×∂xT\begin{align} \partial_x x &\mapsto …
5
Czym dokładnie jest obliczenie?
Wiem, czym jest obliczenie w jakimś niejasnym sensie (tak robią komputery), ale chciałbym bardziej rygorystyczną definicję. Dictionary.comDefinicje obliczeń, obliczeń, obliczeń i obliczeń są okrągłe, więc to nie pomaga. Wikipediadefiniuje obliczenia jako „każdy rodzaj obliczeń zgodny z dobrze zdefiniowanym modelem”. Definiuje obliczenia jako „zamierzony proces, który przekształca jeden lub więcej danych …
4
Używasz ludzi jako komponentów do budowy komputera?
Ok, zanim zacznę, zdaję sobie sprawę, że jest to na marginesie tematu (przeczytałem Pomoc dotyczącą pytań na tej stronie), szczególnie, że nie jest to rzeczywisty problem. Jednak: Nie mogę znaleźć niczego istotnego w Google Z purystycznego punktu widzenia z pewnością musi należeć do informatyki? W każdym razie, jeśli przekroczyłem granicę, …
3
Czy funkcje o wolniejszym wzroście niż odwrotny Ackermann pojawiają się w granicach środowiska wykonawczego?
Niektóre skomplikowane algorytmy ( szukanie związku ) mają prawie stałą odwrotną funkcję Ackermanna, która pojawia się w asymptotycznej złożoności czasowej, i są optymalne w najgorszym przypadku, jeśli prawie stały odwrotny termin Ackermanna jest ignorowany. Czy istnieją przykłady znanych algorytmów z czasami działania, które obejmują funkcje, które rosną zasadniczo wolniej niż …
1
Czy istnieją w pełni optymalizujące kompilatory do kończenia programów?
W książce Andrew W. Appela, Modern Compiler Implementation in ML , mówi w rozdziale 17, że teoria obliczalności pokazuje, że zawsze będzie możliwe wynalezienie nowych transformacji optymalizacyjnych i udowadnia, że ​​w pełni optymalizujący kompilator rozwiąże problem zatrzymania: Program Q, który nie wytwarza mocy wyjściowej i nigdy nie zatrzymuje się, można …
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.