Teoretyczne informatyka

5

Larry Wasserman ma niedawny post, w którym mówi o „policji p-value”. Robi interesujący punkt (wszystkie moje podkreślenia) (przesłankę kursywą, którą dodałem, a jego odpowiedź poniżej): Najczęstszą skargą jest to, że fizycy i dziennikarze nieprawidłowo wyjaśniają znaczenie wartości p. Na przykład, jeśli wartość p wynosi 0,000001, zobaczymy takie stwierdzenia, jak: „istnieje …

15 ds.algorithms soft-question big-list

1

Skróty filtra Bloom: więcej czy więcej?

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 skrótu i jedną z podwójną entropią? Wynika to z patrzenia na …

15 ds.data-structures it.information-theory hash-function

1

Rysujesz wykresy z kilkoma „ostrymi” wierzchołkami?

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 wierzchołek w osadzeniu, tak że wszystkie krawędzie padające na ten wierzchołek leżą …

15 graph-theory cg.comp-geom graph-drawing

4

Jedność parametryczna a parametryczność binarna

Ostatnio zainteresowałem się parametrownością po obejrzeniu artykułu LICS Bernardy'ego i Moulina z 2012 r. ( Https://dl.acm.org/citation.cfm?id=2359499 ). W tym artykule internalizują one jednoargumentową parametryczność w systemie czystego typu z typami zależnymi i podpowiadają, w jaki sposób można rozszerzyć konstrukcję na dowolne arie. Wcześniej widziałem tylko parametr binarny. Moje pytanie brzmi: …

15 lo.logic pl.programming-languages type-systems logical-relations parametricity

1

Rozkład grafów połączonych na k na elementy połączone (k + 1)

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 podstawie jego wykresu. Ten proces nie uogólnia się na większą łączność. Na przykład, …

15 graph-theory co.combinatorics

1

Rozkładanie wykresów rodzaju pierwszego

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 Seymour wykazali, że każdy …

15 graph-theory co.combinatorics planar-graphs graph-minor

2

Godne uwagi przykłady idei pierwiastka kwadratowego w analizie złożoności

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 O(n−−√)O(n)O(\sqrt n) , statyczne zliczanie zakresu ortogonalnego 2D w czasie O(n−−√)O(n)O(\sqrt n) …

15 ds.algorithms ds.data-structures big-list teaching

1

Czym dziedziczenie różni się od podtypu?

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 poddziałem?

15 pl.programming-languages type-theory type-systems object-oriented

1

Twardość obliczeń etykiet Weisfeiler-Lehman

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 …

15 cc.complexity-theory graph-theory graph-isomorphism logspace

1

Czy algebrę boolowską można wyrazić prostym typem lambda caclulus?

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 …

15 lo.logic type-theory lambda-calculus

1

Czy wymaganie jednoznaczności poprawnych odpowiedzi dla Merlina ogranicza moc protokołów Arthur-Merlin?

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 losowego komunikatu „wyzwanie” (o wielomianowej długości) Arthur generuje z …

15 cc.complexity-theory interactive-proofs unique-solution

5

Pakiet oprogramowania do dekompozycji obwodów kwantowych

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

15 quantum-computing software

1

Rozwiązanie w przybliżeniu liniowego równania diofantyny

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 binarnej. Wyjście …

15 cc.complexity-theory optimization linear-algebra integer-lattice

1

Ranking trudności trudnych problemów NP w praktyce

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 znanego jako Przejście Fazowe . W szczególności w przypadku losowych …

15 cc.complexity-theory np-hardness sat

10

Jakie są problemy, gdy wiemy, że mamy optymalny algorytm?

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

15 cc.complexity-theory ds.algorithms complexity-classes