Uma maneira de mostrar que verificar a viabilidade de um sistema linear de desigualdades é tão difícil quanto a programação linear é através da redução dada pelo método elipsóide. Uma maneira ainda mais fácil é adivinhar a solução ideal e apresentá-la como uma restrição via pesquisa binária. Ambas...
Se temos um gráfico grande (direcionado) GGG e uma árvore com raízes menores , qual é a complexidade mais conhecida para encontrar subgráficos de isomórficos para ? Estou ciente dos resultados do isomorfismo da subárvore, onde e são árvores e também onde é planar ou limitou a largura de árvore (e...
A transformada de Walsh-Hadamard (WHT) é uma generalização da transformada de Fourier e é uma transformação ortogonal em um vetor de números reais ou complexos de dimensão . A transformação é popular na computação quântica, mas foi estudada recentemente como uma espécie de pré-condicionador para...
Considere o seguinte problema: Dado um gráfico de consulta G=(V,E)G=(V,E)G = (V, E) e um gráfico de referência G′=(V′,E′)G′=(V′,E′)G' = (V', E') , queremos encontrar o mapeamento injetivo f:V→V′f:V→V′f : V \rightarrow V' que minimiza o número de arestas (v1,v2)∈E(v1,v2)∈E(v_1, v_2) \in E tal que ....
Quais são alguns problemas não triviais em que sabemos que o algoritmo atual que temos é o ideal assintoticamente ideal? (Para máquinas de turing) E como isso é
Suponha que queremos encontrar ou max x ∏ i j ∈ E f ( x i , x j )∑x∏i j ∈ Ef( xEu, xj)∑x∏Euj∈Ef(xEu,xj)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏i j ∈ Ef( xEu, xj)maxx∏Euj∈Ef(xEu,xj)\max_x \prod_{ij \in E} f(x_i,x_j) Onde max ou soma é tomada sobre todas as bulas de , o produto é tomado ao longo...
De forma simples: Um autômato finito bidirecional pode reconhecer gráficos vertex que contêm um triângulo com estados ?o ( v 3 )vvvo(v3)o(v3)o(v^3) Detalhes De interesse aqui estão os gráficos vertex codificados usando uma sequência de arestas, cada aresta sendo um par de vértices distintos...
Coloquialmente, a definição do expoente de multiplicação de matrizes é o menor valor para o qual existe um algoritmo conhecido de multiplicação de matrizes . Como não é aceitável como definição matemática formal, acho que a definição técnica é algo como o mínimo em todo tal forma que existe um...
Existe um algoritmo linear de riffle shuffle no tempo linear? Este é o algoritmo que algumas mãos especialmente hábeis são capazes de executar: dividir uniformemente uma matriz de entrada de tamanho uniforme e depois intercalar os elementos das duas metades. Mathworld tem uma breve página sobre...
Minha pergunta é geral: como começo a pensar em termos de design e complexidade de algoritmos? Vou fazer um Curso de Pós-Graduação em Design de Algoritmos. Eu me matriculei mais cedo, mas desisti depois, porque não conseguia acompanhá-lo. Eu tenho que fazer este curso como um requisito. Existe um...
Ao tentar criar meu próprio algoritmo de classificação, estou procurando o benchmark ideal com o qual posso compará-lo. Para uma ordem não classificada dos elementos A e uma ordem classificada B , qual é uma maneira eficiente de calcular o número ideal de transposições para ir de A a B ? Uma...
Existem vários algoritmos e estruturas de dados que exploram a idéia de que obtém seu valor mínimo em k = \ sqrt n . Exemplos comuns incluemmax{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n algoritmo de passo gigante de baby-step para calcular logaritmo discreto em...
Uma extensão clássica do problema de fluxo máximo é o problema de "fluxo máximo ao longo do tempo": você recebe um dígrafo, dois nós distintos como fonte e coletor, onde cada arco tem dois parâmetros, uma capacidade por -unidade e um atraso. Você também é dado um horizonte de tempo . O objetivo é...
Larry Wasserman tem um post recente, onde fala sobre a "polícia de valor p". Ele faz uma observação interessante (toda a ênfase é minha) (a premissa em itálico que acrescentei e sua resposta abaixo): A queixa mais comum é que físicos e jornalistas explicam o significado de um valor-p...
fundo A memória externa, ou modelo DAM, define o custo de um algoritmo pelo número de E / Ss realizadas (essencialmente, o número de falhas de cache). Esses tempos de execução geralmente são dados em termos de MMM , tamanho da memória e BBB , número de palavras que podem ser transferidas para a...
Os solucionadores SAT oferecem uma maneira poderosa de verificar a validade de uma fórmula booleana com um quantificador. Por exemplo, para verificar a validade de ∃ x . φ ( x )∃x.φ(x)\exists x . \varphi(x) , podemos usar um solucionador SAT para determinar se é satisfatório. Para verificar a...
Eu fiz essa pergunta no Stack Overflow há um tempo atrás: Problema: a venda de Bob . Alguém sugeriu postar a pergunta aqui também. Alguém já fez uma pergunta relacionada a esse problema aqui - subfloresta de peso mínimo de determinada cardinalidade - mas, pelo que entendi, não me ajuda com o meu...
Esta questão foi postada anteriormente em Computer Science Stack Exchange aqui . Imagine que você é um vendedor ambulante de muito sucesso, com clientes em todo o país. Para acelerar o envio, você desenvolveu uma frota de drones descartáveis de entrega, cada um com um alcance efetivo de 50...
Quais são os bons papéis / livros para entender melhor o poder da Decomposição Modular e suas propriedades? Estou particularmente interessado em aspectos algorítmicos da Decomposição Modular. Ouvi dizer que é possível encontrar uma decomposição modular de um gráfico em tempo linear. Existe um...
Na minha introdução ao curso de programação, estamos aprendendo sobre o método Initialization-Maintenance-Termination de provar que um algoritmo faz o que esperamos. Mas apenas tivemos que provar que um algoritmo já conhecido como correto está correto. Nunca fomos solicitados a mostrar que um...