Teoretyczne informatyka

Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do...

Muszę przechowywać zestawy elementów typu a. Typ a jest częściowo uporządkowany, więc porównanie i może zwrócić mniejsze, większe, równe lub nieporównywalne.a 2za1za1a_1za2)za2)a_2 Jednym z problemów z tablicami skrótów jest to, że dwa równe elementy mogą być reprezentowane w różny sposób i nie...

Klasa złożoności BQP odpowiada podprogramom kwantowym w czasie wielomianowym, przyjmującym klasyczne dane wejściowe i wyrzucającym probabilistyczny sygnał klasyczny. Porada kwantowa modyfikuje to, aby uwzględnić kopie niektórych z góry określonych stanów porady kwantowej, ale jak zwykle z...

To pytanie jest ściśle związane z innym postem: Przejścia fazowe w trudnych problemach NP, ale jest nieco inne. Chociaż pytanie dotyczy twardości poszczególnych przypadków trudnych problemów NP, chodzi o uszeregowanie trudności tych samych przypadków. Istnieje wiele bibliografii na temat efektu...

Potocznie definicja wykładnika mnożenia macierzy jest najmniejszą wartością, dla której znany jest algorytm mnożenia macierzy . Nie jest to dopuszczalne, formalnej definicji matematycznej tak Chyba określenie techniczne jest czymś w infimum na wszystkich tak, że istnieje algorytm mnożenia macierzy...

Pytanie 1 Kiedy możemy powiedzieć, że dwa programy (napisane w jakimś języku programowania, takim jak C ++) są różne? Pierwszą skrajnością jest stwierdzenie, że dwa programy są równoważne, jeśli są identyczne. Inną skrajnością jest stwierdzenie, że dwa programy są równoważne, jeśli obliczają tę...

Rozważ następujący problem: Dane wejściowe : hiperpłaszczyzna H = { y ∈ R n : a T y = b }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , podana przez wektor a ∈ Z na∈Zn\mathbf{a} \in \mathbb{Z}^n i b ∈ Zb∈Zb \in \mathbb{Z} w standardowej reprezentacji...

Jakie są nietrywialne problemy, o których wiemy, że obecny algorytm jest asymptotycznie optymalny? (Do maszyn Turinga) Jak to

Preambuła. Klasa złożoności AM to te problemy, które można rozwiązać za pomocą dwóch okrągłych interaktywnych systemów dowodowych między sprawdzonym „Merlinem” a weryfikatorem „Arthurem”. Problem - który testuje niektóre właściwości obiektu X - występuje w AM, jeśli: W przypadku TAK , dla...

Szukałem formalizacji twierdzenia o zwartości dla FOL, ale nie znalazłem żadnego. Czy ktoś jest świadomy takiego rozwoju lub powiązanej

Algebra boolowska może być wyrażona w ten sposób bez typu rachunku lambda (na przykład). true = \t. \f. t; false = \t. \f. t; not = \x. x false true; and = \x. \y. x y false; or = \x. \y. x true y; Również algebra boolowska może być zakodowana w Systemie F w następujący sposób : CBool = All X.X...

1-wym algorytm Weisfeiler-Lehman (WL) jest powszechnie znany jako kanonicznej oznakowania lub algorytmu kolor rafinacji. Działa w następujący sposób: Początkowe zabarwienie jest jednolite, C 0 ( v ) = 1 dla wszystkich wierzchołków v ∈ V ( G ) ∪ V ( H ) .do0do0C_0do0( v ) = 1do0(v)=1C_0(v) = 1v ∈...

W perspektywie języka programowania, co oznacza podtyp? Słyszałem, że „Dziedziczenie nie jest poddziałem”. Jakie są zatem różnice między dziedziczeniem a

Istnieje wiele algorytmów i struktur danych, które wykorzystują ideę, że otrzymuje minimalną wartość przy k = \ sqrt n . Typowe przykłady to k = √max{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n algorytm gigantycznego kroku dziecka do obliczania logarytmu dyskretnego w...

Wykresy płaskie są wolne od . Wykresy te mogą być rozłożone na części składowe tri połączone, które wiadomo, że są albo płaską lub K 5 składników.K.3 , 3K.3),3)K_{3,3}K.5K.5K_5 Czy istnieje taki „ładny” rozkład grafów z rodzaju 1? W swojej przełomowej pracy nad nieletnimi grafami Roberston i...

Połączony wykres można rozłożyć na jego połączone elementy. To drzewo punktów odcięcia bloku jest unikalne. Podobnie, dwupołączone wykresy można rozłożyć na trójkołowe komponenty. Odpowiednie drzewo SPQR opisuje wszystkie cięcia 2-wierzchołkowe na wykresie i jest jednoznacznie określone na...

Solwery SAT dają potężny sposób na sprawdzenie poprawności formuły logicznej za pomocą jednego kwantyfikatora. Na przykład, aby sprawdzić poprawność , możemy użyć solwera SAT, aby ustalić, czy φ ( x ) jest zadowalające. Aby sprawdzić ważność ∀ x . φ ( x ) , możemy użyć solwera SAT do ustalenia,...

Podczas wdrażania filtra Bloom tradycyjne podejście wymaga wielu niezależnych funkcji skrótu. Kirsch i Mitzenmacher pokazali, że tak naprawdę potrzebujesz tylko dwóch, a resztę możesz wygenerować jako kombinacje liniowe. Moje pytanie brzmi: jaka tak naprawdę jest różnica między dwiema funkcjami...

W przypadku płaskiego osadzenia wykresu płaskiego na płaszczyźnie o prostych krawędziach, zdefiniuj wierzchołek jako ostry wierzchołek, jeśli maksymalny kąt między dwiema kolejnymi krawędziami wokół niego jest większy niż 180. Innymi słowy, jeśli istnieje linia przechodząca przez ten wierzchołek...

Czy istnieje jakiś pakiet oprogramowania umożliwiający rozkład jednostek unitarnych z na obwody kwantowe w ramach predefiniowanego uniwersalnego zestawu bramek?U(