Informatyka

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

5
Wystarczający i niezbędny warunek dotyczący prawidłowości języka
Które z następujących wyrażeń jest poprawne? istnieją wystarczające i konieczne warunki dotyczące prawidłowości języka, ale jeszcze ich nie odkryto. Nie ma wystarczających i koniecznych warunków dotyczących prawidłowości języka. Pompowanie lematu jest niezbędnym warunkiem nieregularności języka. Pompowanie lematu jest wystarczającym warunkiem nieregularności języka. Wiem, że # (4) jest poprawne, a # …
1
Czy istnieje podububowy algorytm dla następującego problemu?
Biorąc pod uwagę symetryczną rzeczywistą macierz , czy istnieje algorytm, który oblicza sumę ponad wszystkimi 1 \ leq i &lt;j &lt;k \ leq n ze złożonością czasową lepszą niż O (n ^ 3) ?n×nn×nn \times nA=(aij)A=(aij)A=(a_{ij})∑i,j,kmax(aij,aik,ajk)∑i,j,kmax(aij,aik,ajk)\sum_{i,j,k}\max(a_{ij},a_{ik},a_{jk})1≤i&lt;j&lt;k≤n1≤i&lt;j&lt;k≤n1\leq i<j<k\leq nO(n3)O(n3)O(n^3)
1
Co to jest indukcja indukcyjna?
Co to jest indukcja indukcyjna ? Zasoby, które znalazłem to: książka HoTT na końcu rozdziału 5.7. Artykuł nLab artykuł zatytułowany Definicje indukcyjno-indukcyjne ten post na blogu wspomina także o typach indukcyjno-indukcyjnych Pierwsze dwa odniesienia są dla mnie za krótkie, a dwa ostatnie są zbyt techniczne. Czy ktoś może to wytłumaczyć …
2
Uniwersalna / egzystencjalna kwantyfikacja?
Usiłuję zrozumieć cel uniwersalnej i egzystencjalnej kwantyfikacji typów. Bawię się pisząc zabawkowy język na podstawie rachunku konstrukcji . Czytałem o Morte i Henku, aby pomóc mi lepiej zrozumieć. Nie rozumiem, dlaczego CoC ma zarówno lambda, jak i całkowitą abstrakcję. (λx:A.B)(λx:A.B)(\lambda x:A . B) (∀x:A.B)(∀x:A.B)(\forall x:A . B) Wydaje mi się, …
2
Najmniej powszechny niepodzielnik
SSSdddSSS∀x∈S, d∤x∀x∈S, d∤x\forall x \in S,\ d \nmid x Oznacz n=|S|n=|S|n = |S|i C=max(S)C=max(S)C = \max(S) . Rozważ funkcję F(x)=F(x)=F(x) = najmniejsza liczba pierwsza niepodzieląca xxx . Łatwo zauważyć, że F(x)≤logxF(x)≤log⁡xF(x) \leq \log x . I przez zestaw SSS , niech F(S)=F(S)=F(S) = najmniej Prime że nie dzieli każdy z …
2
Czy istnieje uogólnienie Kodowania Huffmana na kodowanie arytmetyczne?
Próbując zrozumieć związki między kodowaniem Huffmana, kodowaniem arytmetycznym i kodowaniem zakresu, zacząłem myśleć o niedociągnięciach kodowania Huffmana związanych z problemem częściowego upakowania bitów . To znaczy, załóżmy, że masz 240 możliwych wartości dla symbolu i potrzebujesz zakodować to w bitach, utkniesz z 8 bitami na symbol, nawet jeśli nie potrzebujesz …
2
Czy HORN-SAT w LIN, jeśli tak, to dlaczego nie oznacza to, że P = LIN?
Zoo Złożoności definiuje jako klasę problemów decyzyjnych rozwiązywanych przez deterministyczną maszynę Turinga w czasie liniowym.L IN.LINLIN L IN.⊆ P.LIN⊆PLIN \subseteq P Ponieważ HORN-SAT można rozwiązać w (jak wskazano w algorytmach czasu liniowego do testowania spełniania formuł róg zdań (1984) )O ( n )O(n)O(n) Przedstawiono nowe algorytmy decydujące o tym, czy …
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.