Vi máquinas de turing sendo representadas com fitas infinitas em uma e em duas direções. Existe alguma diferença no poder dessas máquinas de turing, ou elas são basicamente equivalentes? Na minha cabeça, acho que são equivalentes, pois acho que deve haver alguma maneira de representar a fita...
Quantas operações aritméticas são necessárias para encontrar uma matriz pseudo-inversa de Moore-Penrose de um campo arbitrário? Se a matriz é invertível e com valor complexo, então é apenas o inverso. Encontrar o inverso leva tempo O(nω)O(nω)O(n^\omega) , onde ωω\omega é a constante de...
Esse é um tipo de pergunta de distância de edição e é muito fácil. Estou com morte cerebral bastante neste assunto e não consigo descobrir até agora. Dada uma série de números, por exemplo [3, 1, 1, 1] Como alguém transformaria todos os números de maneira mais eficiente no mesmo número, com o...
Você pode me dar algumas sugestões sobre um bom livro introdutório (mas abrangente) sobre lógica e computação? Alguns tópicos difusos que tenho em mente são: Presburger artihm., PA, ZF, ZFC, HOL Teoria dos conjuntos, Teoria dos tipos Computação de modelagem (máquinas de Turing) em diferentes...
No problema do posto de gasolina, temos nnn cidades {0,…,n−1}{0,…,n−1}\{ 0, \ldots, n-1 \} e estradas entre elas. Cada estrada tem extensão e cada cidade define o preço do combustível. Uma unidade de estrada custa uma unidade de combustível. Nosso objetivo é ir de uma fonte a um destino da maneira...
Estou procurando uma estrutura de dados persistente semelhante à matriz (mas imutável), permitindo operações rápidas de indexação, acréscimo, pré-acréscimo e iteração (boa localidade). O Clojure fornece Vector persistente, mas é apenas para anexação rápida. O vetor de Scala efetivamente anexa e...
O que é um algoritmo de aproximação bicritério? Isso continua aparecendo no caso de cluster de fluxo de dados. Isso está relacionado à otimização de múltiplos objetivos? Foi aqui que me deparei com: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. O artigo trata de uma versão em fluxo contínuo do...
Entendo que a maioria dos problemas é trivial se um oráculo de parada estiver disponível (ou, penso, de forma equivalente, hiper-computação). No entanto, aplicar o argumento que mostra o Problema de Halting é impossível para uma máquina de Turing também mostra que é impossível para um oráculo de...
Durante uma entrevista para uma posição de desenvolvedor Java, me perguntaram o seguinte: Escreva uma função que use dois parâmetros: uma String representando um documento de texto e um número inteiro fornecendo o número de itens a serem retornados. Implemente a função para que ela...
Eu estou querendo saber se existem problemas -Hard que são `` polinomial" no caso da média. Eu acho que existem duas maneiras de interpretar isso?NPNPNP Se , pode haver um algoritmo de resolução de um N P problema -Hard com amortizado (caso médio) tempo de execução O ( n k ) por uma constante k...
Vamos ser algum problema de contagem, que é conhecido por ser # P -Complete .ΠΠ\PiPPP Isso implica que é A P X- difícil (ou seja, não existe PTAS para o problema, a menos que P = N P
Eu estou olhando para o Cálculo de Construções e seu lugar no Cubo Lambda . Se bem entendi, cada eixo do cubo pode ser considerado como adicionando outra operação envolvendo tipos ao cálculo de tipo simples, . O primeiro eixo adiciona operadores de tipo a termo, o segundo operador de tipo a tipo e...
No caso de gráficos não rotulados, o problema do isomorfismo do gráfico pode ser resolvido por vários algoritmos que apresentam um desempenho muito bom na prática. Ou seja, embora o pior caso de tempo de execução seja exponencial, geralmente se tem um tempo de execução polinomial. Eu esperava que...
O problema de determinar se uma determinada expressão booleana é satisfatoriamente distinta em termos computacionais de realmente encontrar uma solução para a expressão? Em outras palavras, existe outra maneira de descobrir que uma determinada expressão é satisfatória sem determinar explicitamente...
Eu li que sistemas operacionais como Android e iOS são de alguma forma otimizados para melhorar a vida útil da bateria. Meu entendimento é que uma CPU executa um certo número de operações em um determinado período de tempo, então eu acho que você pode acelerar os aplicativos reduzindo o número de...
Digamos, por exemplo, que estou processando strings que requer alguma análise de duas strings. Eu não tenho informações sobre o que seus comprimentos podem acabar sendo, então eles vêm de duas famílias distintas. Seria aceitável chamar a complexidade de um algoritmo ou (dependendo se usamos um...
Existem algoritmos conhecidos que emitem corretamente "yes" para um problema NP-completo sem gerar implicitamente um certificado? Entendo que é fácil transformar um oráculo de satisfação em um localizador de tarefas satisfatórias: apenas itere sobre as variáveis, sempre pedindo ao oráculo de...
O º número de Fibonacci pode ser calculado em tempo linear usando o seguinte recorrência:nnn def fib(n): i, j = 1, 1 for k in {1...n-1}: i, j = j, i+j return i O º número de Fibonacci também pode ser computada como . No entanto, isso tem problemas com problemas de arredondamento para...
Eu sei que é bobagem, mas consegui me confundir e preciso de ajuda para resolver isso Suponha que , então claramente para todo oráculo A temos P A = N P A que contradiz o fato de que existe algum oráculo A para o qual P A ≠ N P A , portanto P ≠ N PP= NPP=NPP=NPUMAAAPUMA=
Estou tentando reproduzir as redes sintéticas (gráficos) descritas em alguns papéis. Afirma-se que o modelo Barabasi-Albert foi usado para criar "redes sem escala com distribuições de graduação em direito do poder, ".PUMA( K ) α k- λPA(k)∝k−λP_A(k) ∝ k^{-λ} PUMAPAP_A é uma distribuição de...