Teoretyczne informatyka

W odpowiedzi na inne pytanie, Rozszerzenia beta teorii rachunku lambda , Evgenij podał odpowiedź: beta + reguła {s = t | s i t są zamkniętymi nierozwiązywalnymi warunkami} gdzie termin M jest rozwiązywalne, czy możemy znaleźć sekwencję kategoriach takich, że M aplikacja „s do nich jest równa I . Odpowiedź …

14 pl.programming-languages  lambda-calculus  lo.logic 

Twierdzenie Rice'a stwierdza, że ​​każda nietrywialna właściwość zbioru rozpoznawana przez niektóre maszyny Turinga jest nierozstrzygalna. Szukam teoretycznego złożoności twierdzenia typu Rice, które mówią nam, które nietrywialne właściwości zbiorów NP są trudne do rozwiązania.

14 cc.complexity-theory  computability  np 

Próbując naprawić błąd w bibliotece, bezskutecznie szukałem artykułów na temat znajdowania podzakresów na czerwonych i czarnych drzewach. Zastanawiam się nad rozwiązaniem wykorzystującym zamki błyskawiczne i czymś podobnym do zwykłej operacji dołączania stosowanej w algorytmach usuwania niezmiennych struktur danych, ale wciąż zastanawiam się, czy istnieje lepsze podejście, którego nie udało mi …

14 ds.data-structures  tree 

Kto wprowadził pomysł rekurencji ? Czy ktoś może wyjaśnić, skąd się wziął i jak wpłynął na informatykę?

14 reference-request  ho.history-overview  recursion 

Niech G będzie drzewem na 2n wierzchołkach. Szerokość grzbietu G, tw (G) = 1. Załóżmy teraz, że dodajemy n krawędzi do G, aby uzyskać wykres H. Łatwa górna granica na tw (H) wynosi n + 1. Czy jest to w zasadzie najlepszy możliwy? Wydaje się, że tw (H) powinno być …

14 upper-bounds  treewidth 

Jeśli jesteś zaznajomiony z weryfikacją programu, prawdopodobnie wolisz przeczytać pytanie przed tłem . Jeśli nie jesteś zaznajomiony z weryfikacją programu, być może nadal będziesz w stanie odpowiedzieć na to pytanie, ale prawdopodobnie wolisz najpierw przeczytać tło . tło Często mówi się, że sprawdzenie częściowej poprawności jest nierozstrzygalne. Dla celów dyskusji …

14 cc.complexity-theory  lo.logic  program-verification  program-logic 

Robin Milner zdefiniował bigraphy jako rodzaj struktury graficznej o strukturze podobnej do wykresu, ale w której węzły można zagnieżdżać. Uogólniają kalkulatory procesowe, takie jak CCS i calculus, ale wydaje się, że Milner zamierzał je stosować znacznie bardziej ogólnie: notatki z seminarium na krótko przed jego śmiercią opisują ostatnie wydarzenia.ππ\pi Patrząc …

14 process-algebra  ho.history-overview 

Niedawno dowiedziałem się o chciwych przypuszczeniach dotyczących najkrótszego problemu superstrun . W tym problemie otrzymujemy zestaw ciągów s1, … , Sns1,…,sns_1,\dots, s_n i chcemy znaleźć najkrótszy superstrun sss tj. Taki, aby każdy sjasis_i pojawiał się jako podciąg sss . Problem ten jest trudny do przeprowadzenia w NP i po długiej …

14 reference-request  approximation-algorithms  greedy-algorithms 

Dla teorii typów przez spójność rozumiem, że ma typ, który nie jest zamieszkany. Z silnej normalizacji sześcianu lambda wynika, że ​​układ FFF i układ FωFωF_\omega są spójne. Typy indukcyjne MLTT + mają również dowód normalizacji. Jednak wszystkie powinny być wystarczająco mocne, aby zbudować model PA, co dowodzi, że PA jest …

14 type-theory  proof-theory 

Niech będzie jakimś językiem, a następnie zdefiniujemy spójność syntaktyczną jako u ∼ v : ⇔ ∀ x , y ∈ X ∗ : x u y ∈ L ↔ x v y ∈ L i iloraz monoidu X ∗ / ∼ L wynosi nazywany składniowym monoid z L .L ⊆ …

14 fl.formal-languages  automata-theory  regular-language  algebra  monoid 

f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f\colon\{-1,1\}^n \to \{-1,1\}iiiInfi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)]Infi⁡[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)] \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})] x⊕ix⊕ix^{\oplus i}iiixxxfffMinInf[f]=defmini∈[n]Infi[f].MinInf⁡[f]=defmini∈[n]Infi⁡[f].\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f]. Biorąc pod uwagę parametr p∈[0,1]p∈[0,1]p\in[0,1] , wybieramy funkcję ppp losową fff , wybierając jej wartość na każdym z 2n2n2^n wejść niezależnie losowo, aby była równa 111 z prawdopodobieństwem ppp , a −1−1-1 z prawdopodobieństwem …

14 reference-request  pr.probability  boolean-functions 

Na podstawie podręcznika Wprowadzenie do algorytmów poprawność zachłannego algorytmu wymaga problemu z dwiema właściwościami: chciwy wybór nieruchomości optymalna podkonstrukcja Łatwo jest wymyślić przeciwne przykłady, dla których chciwe rozwiązanie zawodzi z powodu braku właściwości chciwego wyboru, np. Problem plecaka 0/1. Ale trudno mi sobie wyobrazić inną możliwość. Czy ktoś może mi …

14 greedy-algorithms 

Szukam przykładów wyników, które są sprzeczne z intuicją ludzi podczas ogólnej dyskusji publiczności. Wyniki, które na pytanie ekspertów niebędących ekspertami „co podpowiada ci intuicja?”, Prawie wszystko byłoby błędne. Oświadczenie o wynikach powinno być łatwe do wyjaśnienia studentom w cs / matematyce. Głównie szukam wyników w informatyce. Jakie są najbardziej sprzeczne …

14 big-list  teaching  intuition 

Czytam formalną prezentację teorii typów Martina-Löfsa (załącznik do książki HoTT ). Autorzy wprowadzić hierarchię światów, a oraz W -types jak liczb naturalnych N (indukcyjnie przez 0 , a s u c c ). W końcu dodają także wyższe typy indukcyjne.Π , Σ , + , 0 , 1Π,Σ,+,0,1\Pi, \Sigma,+, {\bf …

14 type-theory 

Można mówić o treewidth z logicznego obwodu, określające go jako treewidth o „o zabarwieniu moralnym” wykresu na przewodach (wierzchołków) otrzymany w następujący sposób: przewody CONNECT aaa i bbb , gdy bbb jest wyjście z bramki mające jako wejście (lub nawzajem); Podłączyć przewody a i b , gdy są one wykorzystywane …

14 circuit-complexity  pr.probability  treewidth  arithmetic-circuits