Digamos que encontrei um algoritmo de 2 aproximações para um determinado problema e quero mostrar que a análise é rigorosa. Agora preciso criar um exemplo de tamanho genérico nnn ou basta mostrar que tenho um exemplo de tamanho 101010 para o qual o algoritmo produz
Dado um problema, é possível provar qual seria a melhor eficiência de pior algoritmo de um algoritmo para resolver esse problema? Por exemplo, vamos dar o problema de classificar uma matriz. Muitos dos algoritmos de classificação mais simples têm uma eficiência de pior caso de O...
Peço desculpas, mas mesmo após essas duas outras postagens: aqui e aqui ainda estou tendo problemas para entender as TMs e a relativização do oracle. Esta questão vem à questão de um ângulo diferente: Por que as provas não relativizantes são consideradas mais válidas do que argumentos baseados em...
Tenho uma pergunta geral sobre o mapeamento de reduções. Eu já vi vários exemplos de redução de funções paraATMATMA_{TM} onde ATM={⟨M,w⟩: For M is a turing machine which accepts string w}ATM={⟨M,w⟩: For M is a turing machine which accepts string w}A_{TM} = \{\langle M, w \rangle : \text{ For } M...
Tentei provar que o seguinte idioma é recursivo: para , um número inteiro positivo: ondeΣ = { 0 , 1 }Σ={0,1}\Sigma=\{0,1\}kkkeuk=HT M ,ε∩ΣkLk=HTM,ε∩Σk L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k HT M ,ε= { ⟨ M⟩ | M é uma TM que para em uma entrada vazia }HTM,ε={⟨M⟩∣M is a TM that halts on an...
Estou fazendo uma tese de pós-graduação sobre a comprovação da correção do programa para multiplicar 2 matrizes usando a lógica Hoare. Para fazer isso, preciso gerar o loop invariável para aninhado para este programa: for i = 1:n for j = 1:n for k = 1:n C(i,j) = A(i,k)*B(k,j) + C(i,j); end...
O teorema de Ramsey afirma que todo gráfico com nós contém um clique ou um conjunto independente com pelo menos nós.nnn12log2n12log2n\frac{1}{2}\log_2 n Tentei procurar em alguns lugares (incluindo o Sipser), mas não consegui entender muito bem as provas. Eu apreciaria se alguém pudesse me dar...
Deixei G = ( V, E)G=(V,E)G = (V,E) ser um gráfico tendo nnn vértices, nenhum dos quais está isolado, e n - 1n-1 1n−1 bordas, onde n ≥ 2n≥2n \geq 2. Mostre queGGG contém pelo menos dois vértices de grau um. Eu tentei resolver esse problema usando a propriedade ∑v ∈ Vdeg( v ) = 2 |...
Eu desenvolvi o seguinte pseudocódigo para o problema da soma dos pares: Dada uma matriz de números inteiros e um número inteiro , retorne YES se houver posições i, j em A com A [i] + A [j] = b , NO caso contrário.AAAbbbi,ji,ji,jAAAA[i]+A[j]=bA[i]+A[j]=bA[i] + A[j] = b Agora devo declarar um...
Resolvendo a relação de recorrência . O livro do qual este exemplo é afirma falsamente que adivinhando e depois argumentando T(n)=2T(⌊n/2⌋)+nT(n)=2T(⌊n/2⌋)+nT(n) = 2T(\lfloor n/2 \rfloor) + nT(n)=O(n)T(n)=O(n)T(n) = O(n)T(n)≤cnT(n)≤cnT(n) \leq
Estou procurando uma aproximação de ΘΘ\ThetaT( n ) = T( n - 1 ) + cn2T(n)=T(n−1)+cn2T(n) = T(n-1) + cn^{2} Isto é o que eu tenho até agora: T( n - 1 )T( N )T( n - 2 )T( N )T( n - 3 )T( N )= T( n - 2 ) + c ( n - 1)2= T( n - 2 ) + c ( n - 1 ) + cn2= T( n - 3 ) + c ( n - 2)2= T( n - 3 ) + c ( n -...
Como minha pergunta se relaciona diretamente a uma parte do texto de um livro de 2004, Lógica em Ciência da Computação: Modelagem e Raciocínio sobre Sistemas (2ª Edição), de Michael Huth e Mark Ryan , para fornecer contexto para a discussão a seguir, citando parcialmente o livro literalmente: O...
Ouvi algumas alegações de que o cálculo de construções sem tipos indutivos não é poderoso o suficiente para expressar provas por indução. Isso está correto? Se sim, por que a codificação da Igreja não é suficiente para
Preciso provar que o TAUT é coNP-completo. Eu mostrei esse reduzindo para . No entanto, não consigo descobrir como provar que todos os problemas no coNP podem ser reduzidos para em tempo polinomial. Para fazer isso, eu precisaria de uma de duas coisas:TAUT∈coNPTAUT∈coNP\text{TAUT} \in...
Como preparação para um exame sobre algoritmos e complexidade, atualmente estou resolvendo exercícios antigos. Um conceito com o qual eu já estava lutando quando o encontrei pela primeira vez é o conceito de análise amortizada. O que é análise amortizada e como fazê-lo? Em nossas notas de aula,...