Pytania otagowane jako reference-request

Pytania wymagające literatury na temat konkretnych, wąskich zagadnień.

2
Problemy decyzyjne w
Jakie są przykłady trudnych problemów decyzyjnych, które można rozwiązać w czasie wielomianowym? Szukam problemów, dla których optymalny algorytm jest „wolny” lub problemów, dla których najszybszy znany algorytm jest „wolny”. Oto dwa przykłady: Rozpoznawanie idealnych wykresów. W swojej pracy FOCS'03 [1] Cornuéjols, Liu i Vuskovic podali algorytm czasowy dla problemu, gdzie …
4
Czy istnieje repozytorium dla hierarchii dowodów?
Jestem samoukiem, asystentem ds. Dowodów i postanowiłem zacząć od kilku podstawowych dowodów i podążać swoją drogą. Ponieważ dowody są oparte na innych dowodach, a zatem tworzą hierarchię, czy istnieje repozytorium hierarchii dowodów? Wiem, że mogę wybrać konkretnego asystenta proofów i przeanalizować jego bibliotekę, aby wyodrębnić jego hierarchię, jednak jeśli chcę …
2
Jakie jest pochodzenie λ dla pustego łańcucha?
Zazwyczaj używam symbolu dla pustego łańcucha (pusty wyraz lub łańcuch pusty). Ale wiem, że niektórzy ludzie używają λ zamiast ε .εε\varepsilonλλ\lambdaεε\varepsilon Myślę, że pochodzi od słowa „pusty”. Jednak nie wiem, skąd się bierze λ .εε\varepsilonλλ\lambda W teorii automatów istnieje przejście epsilon na automatach, a także mówi się, że jest to …
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ść …
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 …
2
Skutecznie próbkuj najkrótsze ścieżki
Niech GGG jest wykresem, niech sss i ttt są dwa wierzchołki GGG . Możemy skutecznie próbki najkrótszą sss - ttt ścieżkę równomiernie i niezależnie losowo ze zbioru wszystkich najkrótszych ścieżek między sss i ttt ? Dla uproszczenia możemy założyć, że GGG jest prosty, nieukierunkowany i nieważony. Nawet w ograniczonych wielu …
2
Kilka pytań na temat obliczeń równoległych i klasy NC
Mam wiele powiązanych pytań dotyczących tych dwóch tematów. Po pierwsze, większość tekstów złożoności tylko tuszować klasę . Czy istnieje dobry zasób, który bardziej szczegółowo omawia badania? Na przykład coś, co omawia wszystkie moje pytania poniżej. Ponadto, jestem przy założeniu, że N C nadal widzi ilość godziwą badań ze względu na …
1
Liczenie par inwersji
Klasyczne zastosowanie dzielenia i podbijania polega na rozwiązaniu następującego problemu: Biorąc pod uwagę tablicę różnych, porównywalnych elementów, policz liczbę par inwersji w tablicy: pary ( i , j ) takie, że a [ i ] > a [ j ] i i < j .a [ 1 … n ]za[1…n]a[1\dots …
1
Kiedy
Zgodnie z artykułem Wikipedii , L w oznacza „skanowanie od lewej do prawej”, a „R” oznacza „pochodzenie od prawej”. Jednak w oryginalnym artykule Knutha na temat gramatyki definiuje (na stronie 610) jako język, który jest „możliwy do przetłumaczenia z lewej na prawą za pomocą związanego ”.L R ( k )L.R(k)LR(k)L …
1
Badania dotyczące oceny nieświadomości pamięci podręcznej w praktyce
Algorytmy i struktury danych ignorowane przez pamięć podręczną są raczej nową rzeczą, wprowadzoną przez Frigo i in. w algorytmach niepamięci Cache, 1999 . Teza Prokopa z tego samego roku wprowadza także wczesne pomysły. Artykuł Frigo i in. przedstawić niektóre wyniki eksperymentalne pokazujące potencjał teorii oraz algorytmów i struktur danych nieobsługiwanych …
1
Przybliżenie minimalnej przepustowości drzew binarnych
Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. Problem decyzyjny jest NP-zupełny nawet dla drzew binarnych. Wyniki złożoności dla minimalizacji przepustowości. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, nr 3, 1978 . …
4
Samokształcenie informatyki
Jestem 16-letnim mężczyzną, który niedawno otrzymał od mojej dużej przyjaciółki encyklopedię informatyki. Zazwyczaj nie interesuję się komputerami i technologią, ale informatyka zaczęła mnie fascynować. Mam jednak zamiar studiować fizykę i / lub matematykę, a nie CS, więc moje pytanie brzmi: czy przydatne byłoby przeprowadzenie samodzielnej nauki informatyki? Oczywiście nie idę …
1
Maszyny o dostępie swobodnym z tylko dodawaniem, mnożeniem, równością
Literatura jest dość jasna, że ​​jednostronne pamięci RAM z pierwotnym mnożeniem są nieuzasadnione, ponieważ są nie mogą być symulowane przez maszyny Turinga w czasie wielomianowym potrafi rozwiązać problemy związane z PSPACE w czasie wielomianowym Jednak wszystkie odniesienia, które mogę znaleźć na ten temat (Simon 1974, Schonhage 1979) obejmują również operacje …
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.