Estou estudando técnicas de implementação para linguagens de programação e recentemente me deparei com pilhas de espaguete, que são supostamente uma boa opção para um modelo de estilo de passagem continuada (dado seu uso em, por exemplo, Scheme e SML / NJ ). Por uma questão de simplicidade, vamos...
Eu quero produzir caminho mais curto ( k seria menor que 10) entre todos os pares em um gráfico. O gráfico é (na verdade um mapa do metrô):kkkkkk ponderado positivamente sem direção escasso com cerca de 100 nós Meu plano atual é aplicar o caminho mais curtokkk a cada par; Agora estou procurando...
Dada uma triangulação (sem pontos de Steiner) de um polígono simples , pode-se considerar o duplo dessa triangulação, que é definido da seguinte forma. Criamos um vértice para cada triângulo em nossa triangulação e conectamos dois vértices se os triângulos correspondentes compartilharem uma aresta....
Há uma redução famosa e elegante do problema de correspondência bipartida máxima para o problema de fluxo máximo: criamos uma rede com um nó de origem , um nó terminal e um nó para cada item a ser correspondido e, em seguida, adicionamos arestas apropriadas.tsssttt Certamente, existe uma maneira...
Normalmente, vejo que na representação semântica operacional estrutural do loop while, o estado do programa não muda: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S)...
As respostas a essa pergunta no Crypto Stack Exchange basicamente dizem que, para medir a complexidade do problema do logaritmo, precisamos levar em consideração o tamanho do número que representa o tamanho do grupo. Parece arbitrário, por que não escolhemos o tamanho do grupo como argumento?...
Um gráfico bipartido é plano se não tiver ou menores.K3 , 3K3,3K_{3, 3}K5K5K_5 Estou procurando condições necessárias ou suficientes para permitir que desenhos planares sem arestas "circulem" conjuntos de vértices. Estes são desenhos satisfatórios: Todos os vértices de uma parte são desenhados...
Publiquei isso no MathUnderflow, mas não obtive respostas, então pensei em experimentar aqui, Estou lendo o antigo artigo de Rabin e Fischer [publicará um link quando possível] onde, entre outras coisas, é comprovada a complexidade duplamente exponencial da aritmética de Presburger. A prova se...
Eu estava pensando recentemente o que aconteceria se permitíssemos que as gramáticas sem contexto tivessem um número infinito de regras. Claramente, se permitirmos arbitrários conjuntos infinitos de regras, todo idioma sobre algum alfabeto poderia ser descrito por um CFG com . Mas e se...
No artigo de Chris Okasaki, " Achatando Combinadores: Sobrevivendo Sem Parênteses ", ele mostra que dois combinadores são suficientes e necessários como base para codificar expressões completas de Turing sem a necessidade de um operador de aplicativo ou parênteses. Comparado às codificações de...
Estou tentando criar uma prova para o seguinte: Para qualquer idioma , existe uma linguagem B tal que A ≤ T B , mas B ≰ T A .AAABBBA≤TBA≤TBA \le_{\mathrm{T}} B≰TA≰TA\nleq_{\mathrm{T}} A Eu estava pensando em deixar ser um T M , mas eu percebo que nem todos os idiomas são Turing redutível a A T...
Suponha que você estenda o Cálculo de construções com "furos" - ou seja, trechos incompletos de código que você ainda não preencheu. Gostaria de saber se existe um algoritmo para preencher essas funções automaticamente. Por exemplo (usando a sintaxe de Morte ): Caso A: λ (pred : ?) -> λ (Nat...
Segundo esta fonte, a constante Chaitin é normal.ΩΩ\Omega Cada probabilidade de parada é um número real normal e transcendental que não é computável, o que significa que não há algoritmo para calcular seus dígitos. De fato, cada probabilidade de parada é aleatória de Martin-Löf, o que significa...
Estou procurando uma definição formal de arquivo que não inclua apenas armazenamento, mas também abstrações como procfs ou / dev / null (ou qualquer arquivo baseado em fusível) que não estejam relacionadas ao armazenamento. Até agora eu sei que todos os arquivos são abstrações que pode ser...
Para resolver esse problema, observei primeiro que ϕ(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) Onde ϕ(m)ϕ(m)\phi(m) é o número de divisores (não necessariamente primos) de...
Estou lendo este artigo bem conhecido sobre Universos na teoria dos tipos . No começo, eu esperava algo semelhante ao Setωda Agda, mas acontece que é algo ainda mais geral. Parece generalizar a construção do universo de um tipo indutivo-recursivo simples para um aglutinante (semelhante a e ). A...
Existe um teorema que diz que: Dado um autômato de estado finito com estados, se existe uma string cujo comprimento satisfaz , o idioma aceito pelo autômato é infinito.nnnWWwn≤|w|≤2n−1n≤|w|≤2n−1n \leq |w| \leq 2n-1 Eu entendo a restrição , mas não entendo por que a restrição está...
Os seguintes presentes gramática livre de contexto uma "pendurado outra" tipo ambigüidade (imaginar que aaa significa if expr thene bbb significa elsee ccc está para algum outro tipo de instrução ou bloco): S→aSbS|aS|cS→aSbS|aS|c \begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\;...
Em Spanner, TrueTime e The The Theemem CAP , Eric Brewer escreve: Uma coisa sutil sobre o Spanner é que ele obtém serialização dos bloqueios, mas obtém consistência externa (semelhante à linearizabilidade ) do TrueTime [ ênfase adicionada ]. Qual é a definição de consistência externa e como...
Dado que: Uma linguagem com sistemas do tipo muito expressivo (por exemplo, Idris ) também pode ter mecanismos de escape como interfaces de função estrangeira / unsafePerformIO. Existem assistentes de prova que podem ser usados para provar algumas propriedades de um programa escrito em um...