Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Znaleźć przedmioty, które są w co najmniej
Rozważ zestawów wartości (reprezentowanych jako uporządkowane tablice bez duplikatów i ze znanym rozmiarem (tzn. Rozmiar można uzyskać w O (1)). Wartości można sprawdzić pod kątem równości w czasie O (1). Chcę aby otrzymać zestaw wartości, które są obecne w co najmniej różnych zestawach spośród .nnnkkknnn Oczywistym algorytmem do tego jest …
1
Rozległość modeli rachunku lambda
Tłumaczę książkę na temat LISP i oczywiście dotyka ona niektórych elementów rachunku. Zatem wzmiankowane jest pojęcie ekstensywności wraz z niektórymi modelami λ- rachunku, a mianowicie: P ω i D ∞ (tak, z nieskończonością u góry). I mówi się, że P ω jest ekstensjonalny podczas D ∞ nie jest.λλ\lambdaλλ\lambdaP.ωPω\mathcal{P}_\omegare∞D∞D^\inftyPωPω\mathcal{P}_\omegaD∞D∞D^\infty Ale ... …
2
Pokryj wielokąt wklęsły minimalną liczbą prostokątów
Próbuję pokryć prosty wklęsły wielokąt minimalnymi prostokątami. Moje prostokąty mogą mieć dowolną długość, ale mają maksymalną szerokość, a wielokąt nigdy nie będzie miał ostrego kąta. Pomyślałem o próbie rozłożenia mojego wklęsłego wielokąta na trójkąty, które wytwarzają zestaw minimalnie nakładających się prostokątów minimalnie ograniczających każdy trójkąt, a następnie łączenie tych prostokątów …
1
Rozróżnianie
Biorąc pod uwagę stan kwantowy wybrany losowo równomiernie ze zbioru N stanów mieszanych ρ 1 . . . ρ N , jakie jest maksymalne średnie prawdopodobieństwo prawidłowej identyfikacji A ?ρAρA\rho_ANNNρ1.. . ρN.ρ1...ρN.\rho_1 ... \rho_NZAZAA Problem ten można przekształcić w problem odróżnialności dwóch stanów, rozważając problem odróżnienia od ρ B = …
1
Mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa
W artykule na temat relatywizacji obliczeń przestrzeni logicznej Ladner i Lynch konstruują wyrocznię, do której . W literaturze można znaleźć więcej patologicznych przykładów. Czytałem kilka artykułów na temat relatywizowanych małych klas kosmicznych, a jednym z podstawowych narzędzi w tym obszarze jest mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa (RST), który wymaga deterministycznej, …
2
Warianty bezpośrednich twierdzeń o produktach
Bezpośrednie twierdzenie o produkcie, nieformalnie, mówi, że obliczenie instancji funkcji f jest trudniejsze niż jednorazowe obliczenie f .kkkfafffaff Typowe bezpośrednie twierdzenia o produktach (np. XOR Lemma Yao) patrzą na złożoność średnich przypadków i twierdzą (bardzo z grubsza), że nie może być obliczone przez obwody o wielkości s z prawdopodobieństwem większym …
2
Czy problem znalezienia operatorów spełniających listę zmiennych boolowskich NP jest kompletny?
Jest to podobne do SAT, z tym wyjątkiem, że znamy przypisanie każdej zmiennej, ale nie znamy przypisania żadnego operatora logicznego. Czy w takim przypadku znalezienie przypisania każdego operatora, aby wyrażenie oceniało na wartość logiczną, stanowi problem NPC? Właściwie zastanawiałem się, czy znalezienie przypisania operatorów arytmetycznych w celu spełnienia liczby całkowitej …
1
Konstruowanie wektorów w pozycji ogólnej
Niech prawdziwa macierz k×nk×nk\times n ( k≤nk≤nk\le n ) AA{\bf A} z tą właściwością, że dowolny zbiór kkk kolumn ma pełną rangę. P: istnieje efektywny sposób deterministyczny znaleźć wektor tak że zmodyfikowanym matrycy ' = [aa{\bf a}A′=[Aa]A′=[Aa]{\bf A}' = [{\bf A}\;{\bf a}] zachowuje tę samą właściwość coAA{\bf A} : dowolnekkk …
2
Notacja dla warunkowego operatora ewolucji hamiltonianów
Czytam pracę Harrowa, Hassidima i Lloyda Algorytmy kwantowe dla liniowych układów równań . Na trzeciej stronie tego artykułu piszą Następnie zastosujemy warunkową ewolucję hamiltonowską on| Ψ 0 ⟩ C ⊗ | b ⟩ ...∑T.- 1τ= 0| τ⟩ ⟨ Τ|do⊗ ei A τto/ T∑τ=0T.-1|τ⟩⟨τ|do⊗mijaZAτto/T.\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|^{C}\otimes e^{iA\tau t_{o}/T}| Ψ0⟩do⊗ | b ⟩ …
1
Dolne granice uczenia się w zapytaniu o członkostwo i modelu kontrprzykładowym
Dana Angluin ( 1987 ; pdf ) definiuje model uczenia się z zapytaniami o członkostwo i teoriami (kontrprzykłady do proponowanej funkcji). Pokazuje, że zwykły język reprezentowany przez minimalny DFA z stanów jest możliwy do nauczenia się w czasie wielomianowym (gdzie proponowane funkcje to DFA) z zapytaniami o członkostwo i co …
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.