Informatyka

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

2
Czy istnieje jakieś badanie lub teoria łącząca wyszukiwanie binarne i wyszukiwanie interpolacyjne?
Właśnie przeczytałem Czy ten algorytm nadal może być uważany za algorytm wyszukiwania binarnego? i przypomniałem sobie, że kilka lat temu napisałem indeksatora / wyszukaj pliki dziennika, aby znaleźć wpisy dziennika w dużych plikach tekstowych według okna daty / godziny. Robiąc to, postanowiłem spróbować poszukać interpolacji (nie wiedziałem, że tak to …
3
Jaka może być różnica w złożoności między znalezieniem rozwiązania łamigłówki Sudoku a POTWIERDZENIEM, że jest to rozwiązanie unikalne?
Zwykle więc Sudoku ma , ale to pytanie rozciąga się również na zagadek o . Istnieje wiele reguł wielomianowego odliczania czasu, które mogą poczynić postępy w znalezieniu rozwiązania łamigłówki Sudoku. Ale czasem wartości odgadnięcia i następujące łańcuchy wniosków mogą być wymagane w celu wyeliminowania wartości komórki lub kombinacji wartości komórek. …
3
Które języki badawcze mają silniejszy system typów niż Haskell i dlaczego?
Tutaj czytam: Haskell zdecydowanie nie ma najbardziej zaawansowanego systemu czcionek (nawet bliskiego, jeśli liczyć języki badawcze), ale spośród wszystkich języków faktycznie używanych w produkcji Haskell jest prawdopodobnie na szczycie. Pytam więc o dwie rzeczy: które języki badawcze mają mocniejsze systemy typów niż Haskell; co poprawiają. Jestem tylko programistą, więc nie …
7
Jak program jest wykonywany na poziomie procesora?
Wiem, że to bardzo częste pytanie. Ale mam inny punkt widzenia. Spróbuję to tutaj wyrazić. Z tego, co wiem, każda instrukcja wykonywana przez procesor jest w języku maszynowym i wszystko, co może zrobić, to wykonywanie operacji arytmetycznych dzięki ALU i jego tranzystorom (jeśli idziemy na poziomie sprzętowym). Jest to jednak …
1
Najszybsza znana złożoność kombinatorycznego algorytmu ILP?
Zastanawiam się, co jest najbardziej znany algorytm, jeśli chodzi o Big- notacji, aby rozwiązać Programowanie Integer Linear?OOO Wiem, że problem jest , więc nie oczekuję niczego wielomianowego. Wiem, że istnieje wiele heurystyk, które są wykorzystywane w praktycznych zastosowaniach, takich jak CPLEX, ale bardziej interesuje mnie formalna, w najgorszym przypadku złożoność …
1
Dowód twierdzenia Karpa-Liptona
Próbuję zrozumieć dowód twierdzenia Karp-Lipton, jak stwierdzono w książce „Złożoność obliczeniowa: nowoczesne podejście” (2009). W szczególności ta książka stwierdza, co następuje: Twierdzenie Karpa-Liptona Jeśli NP , to PH .P ∖ p o l y⊆⊆\subseteq P∖polyP∖polyP_{\backslash poly} =Σp2=Σ2p= \Sigma^p_2 Dowód: Zgodnie z twierdzeniem 5,4, w celu wykazania pH , to wystarczy, …
1
Czy istnieje kompletny problem dla klasy rozstrzygających problemów Turinga?
Języki, takie jak są uzupełniane ponownie przy wielu redukcjach. To banalne, aby zobaczyć, że co-RE ma również kompletne problemy. S. Schmitz [1] rozważa niektóre klasy pomiędzy ELEM a REC . Stanowią one kompletne problemy dla tych klas w ramach specjalnie spreparowanych redukcji.HALTTMHALTTM\text{HALT}_{TM}RE-completeRE-complete\textsf{RE-complete}co-REco-RE\text{co-RE}ELEMELEM\text{ELEM}RECREC\text{REC} Czy istnieją całkowite problemy dla (aka REC ) …
2
Czy istnieje skuteczny algorytm równoważności wyrażeń?
np. xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) ? Wyrażenia pochodzą ze zwykłej algebry w szkole średniej, ale ograniczają się do dodawania i mnożenia arytmetycznego (np. 2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 ), bez odwrotności, odejmowania lub dzielenia. Litery są zmiennymi. Jeśli to pomoże, możemy zabronić jakiegokolwiek wyrażenia reprezentowanego przez wartości liczbowe inne niż 111 ; tzn. nie x2x2x^2 ani …
2
Czy istnieją ustalone klasy złożoności z liczbami rzeczywistymi?
Niedawno student poprosił mnie o sprawdzenie dla nich dowodu twardości NP. Dokonali redukcji zgodnie z: Zmniejszam ten problem P′P′P' którym wiadomo, że jest NP-kompletny do mojego problemu PPP (z redukcją wielokrotnego wielokrotności jeden), więc PPP jest NP-twardy. Moja odpowiedź brzmiała w zasadzie: Ponieważ PPP ma instancje z wartościami z RR\mathbb{R} …
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if …
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.