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

Linguagem esparsa

Índice Linguagem esparsa

Em teoria da complexidade computacional, uma linguagem esparsa é uma linguagem formal (um conjunto de strings) cujo número de strings de comprimento n na língua é limitada por uma função de polinômio n. São utilizadas principalmente no estudo da relação entre a classe de complexidade NP com outras classes.

17 relações: Cadeia de caracteres, Classe de complexidade, Co-NP-completo, Coeficiente binomial, Complexidade computacional, E (complexidade), Função polinomial, Linguagem formal, Linguagem unária, LSPACE, NP (complexidade), NP-completo, P (complexidade), P versus NP, P-completo, P/polinomial, Redução em tempo polinomial.

Cadeia de caracteres

Na programação de computadores, uma cadeia de caracteres ou string é uma sequência de caracteres, geralmente utilizada para representar palavras, frases ou textos de um programa.

Novo!!: Linguagem esparsa e Cadeia de caracteres · Veja mais »

Classe de complexidade

Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.

Novo!!: Linguagem esparsa e Classe de complexidade · Veja mais »

Co-NP-completo

Na teoria da complexidade computacional, problemas computacionais co-NP-completos são os problemas mais difíceis em co-NP, no sentido de que são os mais propensos a não serem P. Se existisse uma forma de resolver um problema co-NP-completo rapidamente, então esse algoritmo poderia ser usado para resolver todos os problemas co-NP de forma rápida.

Novo!!: Linguagem esparsa e Co-NP-completo · Veja mais »

Coeficiente binomial

O coeficiente binomial, também chamado de número binomial, de um número n, na classe k, consiste no número de combinações de n termos, k a k. O número binomial de um número n, na classe k, pode ser escrito como.

Novo!!: Linguagem esparsa e Coeficiente binomial · 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!!: Linguagem esparsa e Complexidade computacional · Veja mais »

E (complexidade)

Na teoria da complexidade computacional, a Classe de complexidade E é o conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística em tempo 2O(n) e, portanto, é igual à classe de complexidade DTIME(2O(n)).

Novo!!: Linguagem esparsa e E (complexidade) · 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!!: Linguagem esparsa e Função polinomial · Veja mais »

Linguagem formal

Entende-se por linguagem formal estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos.

Novo!!: Linguagem esparsa e Linguagem formal · Veja mais »

Linguagem unária

Em teoria da complexidade computacional, uma linguagem unária ou linguagem de registro é uma linguagem formal (um conjunto de strings), onde todas as strings têm a forma de 1k, onde "1" pode ser qualquer símbolo arbitrário.

Novo!!: Linguagem esparsa e Linguagem unária · Veja mais »

LSPACE

Em teoria da complexidade, L (também conhecido como LSPACE ou DLOGSPACE) é a classe de complexidade que contém problemas de decisão os quais podem ser resolvidos por uma máquina de Turing utilizando uma quantidade de espaço de memória logarítmico.

Novo!!: Linguagem esparsa e LSPACE · Veja mais »

NP (complexidade)

Na teoria da complexidade computacional, NP é o acrônimo em inglês para Tempo polinomial não determinístico (Non-Deterministic Polynomial time) que denota o conjunto de problemas que são decidíveis em tempo polinomial por uma máquina de Turing não-determinística.

Novo!!: Linguagem esparsa e NP (complexidade) · 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!!: Linguagem esparsa e NP-completo · Veja mais »

P (complexidade)

Na teoria da complexidade computacional, P é o acrônimo em inglês para Tempo polinomial determinístico (Deterministic Polynomial time) que denota o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística.

Novo!!: Linguagem esparsa e P (complexidade) · Veja mais »

P versus NP

O problema "P versus NP" é o principal problema aberto da Ciência da Computação.

Novo!!: Linguagem esparsa e P versus NP · Veja mais »

P-completo

Na teoria da complexidade computacional, a noção de problema de decisão P-completo é útil na análise de questões como.

Novo!!: Linguagem esparsa e P-completo · Veja mais »

P/polinomial

Na Teoria da complexidade computacional, P/poly é a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma máquina de Turing com um polynomial-bounded advice function.

Novo!!: Linguagem esparsa e P/polinomial · Veja mais »

Redução em tempo polinomial

Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial.

Novo!!: Linguagem esparsa e Redução em tempo polinomial · Veja mais »

Redireciona aqui:

Linguagem Esparça.

CessanteEntrada
Ei! Agora estamos em Facebook! »