Acesso mais rápido do que o navegador!
16 relações: Algoritmo de aproximação, Algoritmo probabilístico, APX-completude, Ciência da computação, Complexidade parametrizada, Fortemente NP-completo, Função polinomial, Grande-O, NP-difícil, P versus NP, Problema da mochila, Problema de otimização, Problema do caixeiro-viajante, Redução linear, Redução PTAS, Subconjunto.
Algoritmo de aproximação
Em ciência da computação e pesquisa operacional (PO), algoritmos de aproximação são algoritmos usados para encontrar soluções aproximadas em problemas de otimização.
Novo!!: Esquema de aproximação de tempo polinomial e Algoritmo de aproximação · Veja mais »
Algoritmo probabilístico
Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica.
Novo!!: Esquema de aproximação de tempo polinomial e Algoritmo probabilístico · Veja mais »
APX-completude
Em teoria da complexidade a classe 'APX' (uma abreviação de "aproximável" em inglês) é o conjunto de Problemas de otimização NP que permitem algoritmos de aproximação em tempo polinomial com relação de aproximação delimitadas por uma constante (ou algoritmos de aproximação de fator constante por simplicidade).
Novo!!: Esquema de aproximação de tempo polinomial e APX-completude · Veja mais »
Ciência da computação
A Ciência da Computação lida com fundamentos teóricos da informação, computação, e técnicas práticas para suas implementações e aplicações.
Novo!!: Esquema de aproximação de tempo polinomial e Ciência da computação · Veja mais »
Complexidade parametrizada
Em ciência da computação, complexidade parametrizada é um ramo da teoria da complexidade computacional que foca em classificar problemas computacionais de acordo com sua dificuldade inerente com respeito a múltiplos parâmetros da entrada.
Novo!!: Esquema de aproximação de tempo polinomial e Complexidade parametrizada · Veja mais »
Fortemente NP-completo
Em Complexidade computacional, NP-completude forte é uma propriedade computacional de problemas que é um caso especial de NP-completude.
Novo!!: Esquema de aproximação de tempo polinomial e Fortemente NP-completo · Veja mais »
Função polinomial
Gráfico de uma função polinomial Em matemática, função polinomial é uma função P que pode ser expressa da forma: em que n é um número inteiro não negativo e os números a_0, a_1,...
Novo!!: Esquema de aproximação de tempo polinomial e Função polinomial · Veja mais »
Grande-O
''g''(''x'') sempre que ''x'' ≥ ''x''0. Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples.
Novo!!: Esquema de aproximação de tempo polinomial e Grande-O · Veja mais »
NP-difícil
NP-difícil (ou NP-hard, ou NP-complexo) na teoria da complexidade computacional, é uma classe de problemas que são, informalmente, "Pelo menos tão difíceis quanto os problemas mais difíceis em NP".
Novo!!: Esquema de aproximação de tempo polinomial e NP-difícil · Veja mais »
P versus NP
O problema "P versus NP" é o principal problema aberto da Ciência da Computação.
Novo!!: Esquema de aproximação de tempo polinomial e P versus NP · Veja mais »
Problema da mochila
Problema da mochila: Como maximizar o valor com um peso máximo? O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória.
Novo!!: Esquema de aproximação de tempo polinomial e Problema da mochila · Veja mais »
Problema de otimização
Problema de otimização, em matemática ou ciência da computação, é um problema de encontrar a melhor solução de todas as soluções viáveis.
Novo!!: Esquema de aproximação de tempo polinomial e Problema de otimização · Veja mais »
Problema do caixeiro-viajante
O problema do caixeiro-viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem.
Novo!!: Esquema de aproximação de tempo polinomial e Problema do caixeiro-viajante · Veja mais »
Redução linear
Em Ciência da Computação, em particular no estudo de algoritmos de aproximação, uma L-redução ("redução linear") é uma transformação de problemas de otimização que linearmente preservam características de aproximação.
Novo!!: Esquema de aproximação de tempo polinomial e Redução linear · Veja mais »
Redução PTAS
Na teoria de complexidade computacional, uma redução PTAS é uma redução com preservação de aproximação que é geralmente usada para fazer reduções junto à soluções para problemas de otimização.
Novo!!: Esquema de aproximação de tempo polinomial e Redução PTAS · Veja mais »
Subconjunto
Diagrama de Euler ilustrando o fato de que A é subconjunto de B ou, equivalentemente, que B é superconjunto de A Em teoria dos conjuntos, quando todo elemento de um conjunto A é também elemento de um conjunto B, dizemos que A é um subconjunto de B, denotado A \subseteq B (também dito "A é uma parte de B" ou "A está contido em B").
Novo!!: Esquema de aproximação de tempo polinomial e Subconjunto · Veja mais »
