Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Czy istnieją problemy „pełne (O)”?
Wiele klas złożoności ma „kompletne” problemy. Czy istnieją kompletne problemy dla klasy złożoności problemów, które można rozwiązaćO ( 1 )O(1)O(1) czas? Komplikacja polega na tym, że klasa ta zależy od modelu obliczeniowego; problem można rozwiązaćO ( 1 )O(1)O(1)czas w jednym rozsądnym modelu obliczeniowym, ale nie w innym, biorąc pod uwagę, …
1
λ-rachunek: Co jest najbardziej wydajne w reprezentacji pamięci w funkcjach?
Chciałbym porównać wydajność struktur danych zakodowanych funkcyjnie (Church / Scott) i klasycznie zakodowanych (asembler / C). Ale zanim to zrobię, muszę wiedzieć, jak wydajna jest / może być reprezentacja funkcji w pamięci. Funkcję tę można oczywiście częściowo zastosować (inaczej zamknięcie). Interesuję się zarówno obecnym algorytmem kodowania, popularnymi językami funkcjonalnymi (Haskell, …
2
Liczenie wysp w macierzach boolowskich
Biorąc pod uwagę n×mn×mn \times m Macierz boolowska XX\mathrm X, pozwolić 000 pozycje reprezentują morze i 111wpisy reprezentują ziemię. Zdefiniuj wyspę jako sąsiadującą pionowo lub poziomo (ale nie po przekątnej)111 wpisy. Pierwotne pytanie polegało na zliczeniu liczby wysp w danej matrycy. Autor opisał rozwiązanie rekurencyjne (O(nm)O(nm)\mathcal{O}(nm) pamięć). Ale bezskutecznie próbowałem …
1
Czy system typów może służyć jako asystent dowodu dla funkcji zagranicznych?
Jeśli się uwzględni: Język z bardzo ekspresyjnymi systemami typów (np. Idris ) może również mieć mechanizmy specjalne, takie jak interfejsy funkcji obcych / niebezpieczne SafePerformIO. Istnieją asystenci sprawdzania, których można użyć do udowodnienia niektórych właściwości programu napisanego w języku, który nie ma systemu typów zdolnego do wyrażania tych właściwości. Korespondencja …
2
Jaki jest obecny stan równoległych lub współbieżnych programów w izomorfizmie Curry-Howarda?
W Dowodach i typach Girarda możemy przeczytać: Z algorytmicznego punktu widzenia rachunek sekwencyjny nie ma izomorfizmu Curry'ego-Howarda ze względu na wiele sposobów pisania tego samego dowodu. To uniemożliwia nam użycie go jako maszynopisu -calculus, chociaż dostrzegamy jakąś głęboką strukturę tego rodzaju, prawdopodobnie związaną z równoległością.λλ\lambda Dowody i typy , JY …
2
Spójność zewnętrzna a linearyzowalność
W Spanner, TrueTime & WPR Twierdzenie , Eric Brewer pisze: Jedną subtelną rzeczą w Spanner jest to, że uzyskuje możliwość serializacji z blokad, ale uzyskuje spójność zewnętrzną (podobną do linearyzowalności ) z TrueTime [ podkreślenie dodane ]. Jaka jest definicja spójności zewnętrznej i czym różni się od linearyzowalności ?
1
Jak można ws z | w | = | s | a my będziemy bez kontekstu, podczas gdy w # s nie jest?
Dlaczego (jeśli tak) separator ##\# robi różnicę między tymi dwoma językami? Powiedzmy: L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} Oto dowód i gramatyk reprezentującyLLL jak CFLCFLCFL A poniżej dodam dowód na to L#∉CFLL#∉CFLL_{\#} \notin CFL : Czy ##\#znak naprawdę …
2
Czy istnieje inna rozdzielczość problemu „zwisające inaczej” niż „najbliższy odpowiednik”?
Poniższa gramatyka bezkontekstowa przedstawia dwuznaczność typu „wiszące inne” (wyobraź to sobie zaaaoznacza if expr thenibbboznacza elseidocc oznacza inny rodzaj instrukcji lub bloku): S.→ a S.b S.|a S.|doS→aSbS|aS|c \begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned} Na przykład, a a c b caacbcaacbc może być analizowany jako ( ( C …
3
Warunek nieskończoności języka automatu skończonego
Istnieje twierdzenie, które mówi, że: Biorąc pod uwagę automat skończony mający stanów, jeśli istnieje ciąg którego długość spełnia wówczas język akceptowany przez automat jest nieskończony.nnnwwwn ≤ | w | ≤ 2 n - 1n≤|w|≤2n−1n \leq |w| \leq 2n-1 Rozumiem ograniczenie , ale nie rozumiem, dlaczego ograniczenie jest tam.| w | …
1
Co to jest super wszechświat?
Czytam ten dobrze znany artykuł o wszechświatach w teorii typów . Na początku spodziewałem się czegoś podobnego do SetωAgdy, ale okazuje się, że jest to nawet coś bardziej ogólnego. Wydaje się uogólniać konstrukcję wszechświata od zwykłego typu indukcyjno-rekurencyjnego do spoiwa (podobnego doΠΠ\Pi i ΣΣ\Sigma). Główne pytanie, które chcę zadać, to …
2
Co to jest plik?
Szukam formalnej definicji pliku, która obejmuje nie tylko pamięć, ale także abstrakcje, takie jak procfs lub / dev / null (lub dowolny plik oparty na bezpieczniku), które nie dotyczą pamięci. Jak dotąd wiem, że wszystkie pliki to abstrakcje może być zidentyfikowany może mieć nazwy (zwykle zorganizowane w struktury hierarchiczne) można …
2
Dla dowolnego języka istnieje takie, że ale
Próbuję wymyślić dowód na następujące kwestie: Dla każdego języka AAA istnieje język BBB , tak że A≤TBA≤TBA \le_{\mathrm{T}} B a B ≰TA≰TA\nleq_{\mathrm{T}} A . Myślałem o pozwoleniu BBB być ATMATMA_{\mathrm{TM}} , ale zdaję sobie sprawę, że nie wszystkie języki Turing można zredukować do ATMATMA_{\mathrm{TM}} , więc A≤TBA≤TBA \le _T B …
2
Wydajne obliczanie najmniejszej liczby całkowitej za pomocą n dzielników
Aby rozwiązać ten problem, po raz pierwszy to zauważyłem ϕ(pe11 pe22⋯ pekk)=(e1+1)(e2+1)⋯(ek+1)ϕ(p1e1 p2e2⋯ pkek)=(e1+1)(e2+1)⋯(ek+1)\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1) Gdzie to liczba (niekoniecznie pierwsza) dzielników . Jeśli jest najmniejszą liczbą całkowitą taką, że , toϕ(m)ϕ(m)\phi(m)mmmmmmϕ(m)=nϕ(m)=n\phi(m) = n ϕ(m)=nϕ(m)=n\phi(m) = n (e1+1)(e2+1)⋯(ek+1)=n(e1+1)(e2+1)⋯(ek+1)=n(e_1 + 1)(e_2 …
1
Jak potężne są CFG, które pozwalają na nieskończoną liczbę zasad?
Zastanawiałem się ostatnio, co by się stało, gdybyśmy pozwolili gramatykom bezkontekstowym mieć nieskończoną liczbę reguł. Oczywiście, gdybyśmy zezwolili na arbitralne takie nieskończone zbiory reguł, każdy językLLL nad jakimś alfabetem ΣΣ\Sigma może być opisany przez CFG G=({S},Σ,R,S)G=({S},Σ,R,S)G = (\{S\},\Sigma,R,S) z R={S→w∣w∈L}R={S→w∣w∈L}R = \{S \rightarrow w \mid w \in L \}. Ale …
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.