Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Faça o download
Acesso mais rápido do que o navegador!
 

Complexidade parametrizada

Índice 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.

15 relações: Algoritmo de aproximação, Ciência da computação, Cobertura de vértices (teoria dos grafos), Coloração de grafos, Complexidade computacional, Conjunto dominante, Conjunto independente, Função (matemática), NP-completo, NP-difícil, P versus NP, Problema computacional, Redução (complexidade), Satisfatibilidade, Tempo de execução.

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!!: Complexidade parametrizada e Algoritmo de aproximação · 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!!: Complexidade parametrizada e Ciência da computação · Veja mais »

Cobertura de vértices (teoria dos grafos)

Na matemática, na disciplina de teoria dos grafos, uma cobertura de vertices de um grafo é um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do conjunto.

Novo!!: Complexidade parametrizada e Cobertura de vértices (teoria dos grafos) · Veja mais »

Coloração de grafos

Em teoria dos grafos, coloração de grafos é um caso especial de rotulagem de grafos; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições.

Novo!!: Complexidade parametrizada e Coloração de grafos · Veja mais »

Complexidade computacional

A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si.

Novo!!: Complexidade parametrizada e Complexidade computacional · Veja mais »

Conjunto dominante

Dominating sets (red vertices). Em teoria dos grafos, um conjunto dominante para um grafo G.

Novo!!: Complexidade parametrizada e Conjunto dominante · Veja mais »

Conjunto independente

Na teoria dos grafos, um conjunto independente de um grafo G é um conjunto S de vértices de G tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se a e b são vértices quaisquer de um conjunto independente, não há aresta entre a e b. Todo grafo tem ao menos um conjunto independente: o conjunto vazio.

Novo!!: Complexidade parametrizada e Conjunto independente · Veja mais »

Função (matemática)

Uma função não injetiva e não sobrejetiva do domínio X para o contradomínio Y. A função é não injetova pois há dois elementos do domínio ligados a um mesmo elemento do contradomínio (cor vermelha). A função é não sobrejetiva pois há elementos de Y sem correspondentes em X (cores azul e lilás). Uma função é uma relação de um conjunto A com um conjunto B. Denotamos uma função por f:A\to B, y.

Novo!!: Complexidade parametrizada e Função (matemática) · Veja mais »

NP-completo

Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo.

Novo!!: Complexidade parametrizada e NP-completo · 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!!: Complexidade parametrizada 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!!: Complexidade parametrizada e P versus NP · Veja mais »

Problema computacional

Na ciência da teoria da computação, um problema computacional é um objeto matemático que representa um coleção de questões que computadores talvez queiram resolver.

Novo!!: Complexidade parametrizada e Problema computacional · Veja mais »

Redução (complexidade)

Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro.

Novo!!: Complexidade parametrizada e Redução (complexidade) · Veja mais »

Satisfatibilidade

Na lógica matemática, satisfatibilidade e validade são conceitos elementares da semântica.

Novo!!: Complexidade parametrizada e Satisfatibilidade · Veja mais »

Tempo de execução

Em informática, tempo de execução ou runtime (termo em inglês), é o período em que um programa de computador permanece em execução.

Novo!!: Complexidade parametrizada e Tempo de execução · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »