Informatyka

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

3
nierozstrzygalny problem i jego negacja jest nierozstrzygalna
Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie. Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i jego uzupełnienie są nierozstrzygalne i nierozstrzygalne? Myślałem o języku diagonalizacji …
1
Czy ustalenie, czy istnieje liczba pierwsza w przedziale, o którym wiadomo, że jest w P czy NP-zupełna?
Widziałem z tego postu przy przepełnieniu stosu, że istnieją pewne stosunkowo szybkie algorytmy przesiewania przedziału liczb, aby sprawdzić, czy jest liczba pierwsza w tym przedziale. Czy to jednak oznacza, że ​​ogólny problem decyzyjny: (Czy istnieje liczba pierwsza w przedziale?) Znajduje się w P. (Było wiele odpowiedzi na ten post, których …
3
Teoretyczna złożoność trudna do sprawdzenia wartości
Funkcja zliczania liczb pierwszych , zdegradowana , jest zdefiniowana jako liczba liczb pierwszych mniejsza lub równa x .π(x)π(x)\pi(x)xxx Możemy zdefiniować problem decyzyjny z w następujący sposób:π(x)π(x)\pi(x) Biorąc pod uwagę dwie liczby i n , zapisane binarnie, zdecyduj, czy π ( x ) = n .xxxnnnπ(x)=nπ(x)=n\pi(x) = n Rozmawiałem dziś z …
1
Jakie jest optymalne rozwiązanie konkursu TSP Procter and Gamble z 1962 roku?
W 1962 r. Możesz wygrać nagrodę w wysokości 10 000 USD (około 80 000 USD w dzisiejszych pieniądzach), jeśli znajdziesz rozwiązanie problemu euklidesowego sprzedawcy podróżującego zdefiniowanego w 33 miastach. http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html Patrząc na zdjęcie, problem wydaje się dość łatwy. Nie udało mi się jednak znaleźć bardziej szczegółowych zasobów na temat problemu. …
2
Wydajny algorytm do generowania losowo dwóch rozproszonych, obłąkanych permutacji multiset
tło \newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr Załóżmy, że mam dwie identyczne partie nnn kulek. Każdy marmur może mieć jeden z kolorów ccc , gdzie c≤nc≤nc≤n . Niech ninin_i oznacza liczbę kulek koloru iii w każdej partii. Niech SS\msS będzie multiset {1,…,1n1,2,…,2n2,…,1c,…,cnc}{1,…,1⏞n1,2,…,2⏞n2,…,1c,…,c⏞nc}\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\} reprezentujący jedną partię. W reprezentacji częstotliwości , SS\msS …
4
Czy problem izomorfizmu grafu został rozwiązany?
Wydaje się, że strona problemu z izomorfizmem grafu w Wikipedii wskazuje, że nie, nie została rozwiązana. Jednak mój przyjaciel zwrócił uwagę na algorytm wielomianu czasowego dla izomorfizmu grafowego . Nie jestem wystarczająco wyrafinowany, aby podążać za rozumowaniem zawartym w artykule. Mam własną bardzo trudną próbę zastosowania algorytmu wielomianowego bez żadnego …
2
Czy krzyżówki wyrażeń regularnych są trudne NP?
Pewnego dnia wygłupiałem się na tej stronie: http://regexcrossword.com/ i zastanawiałem się, jaki był najlepszy sposób rozwiązania tego problemu. Czy potrafisz rozwiązać następujący problem w czasie wielomianowym, czy jest to trudne NP? Biorąc pod uwagę siatkę NxM z N wyrażeniami regularnymi dla kolumn i M dla wierszy, znajdź dowolne rozwiązanie siatki, …
2
analiza czasu algorytmu „wielkość wejściowa” a „elementy wejściowe”
Nadal jestem trochę mylony z terminami „długość wejściowa” i „rozmiar wejściowy”, gdy są używane do analizy i opisu bezobjawowej górnej granicy algorytmu Wydaje się, że długość wejściowa dla algorytmu zależy od rodzaju danych i algorytmu, o którym mówisz. Niektórzy autorzy odnoszą się do długości wejściowej do rozmiaru znaków, które są …
1
Balonowanie pamięci w systemie operacyjnym
Niektóre hiperwizory optymalizują użycie pamięci za pomocą metody nazywanej balonowaniem (przynajmniej tak ją nazywa KVM), ta metoda deduplikuje pamięć między maszynami wirtualnymi i ustawia wspólne strony na tylko do odczytu z kopiowaniem przy zapisie. Jest to swego rodzaju przeciwieństwo wywołania wideł. Czy można wdrożyć procesy na poziomie systemu operacyjnego (myślałem …
3
W jaki sposób procesor znajduje kod jądra po przerwie?
Gdy wystąpi przerwanie, procesor wstrzymuje bieżący proces i wywołuje kod jądra, aby obsłużyć przerwanie. Skąd procesor wie, gdzie wejść do jądra? Rozumiem, że istnieją procedury obsługi przerwań, które można zainstalować dla każdej linii przerwań. Ale ponieważ procesor wykonuje tylko „logikę przewodową”, musi istnieć pewne predefiniowane miejsce, które wskazuje albo na …
1
Dlaczego algorytm mnożenia czasu liniowego Knutha nie „liczy się”?
Strona wikipedii na temat algorytmów mnożenia wspomina o interesującym autorstwa Donalda Knutha . Zasadniczo polega na połączeniu mnożenia transformacji Fouriera ze wstępnie obliczoną tabelą mnożenia wielkości logarytmicznych. Działa w czasie liniowym. Artykuł działa tak, jakby ten algorytm jakoś nie liczy się jako „prawdziwy” algorytm mnożenia. Co ważniejsze, uważa się za …
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.