Acesso mais rápido do que o navegador!
29 relações: Axiomas de Blum, Complexidade computacional, Conjunção lógica, David Stifler Johnson, Disjunção lógica, Gramática livre de contexto, Gramática regular, Gramática sensível ao contexto, Grande-O, Lógica matemática, Linguagem recursiva, Linguagem recursivamente enumerável, Lista de classes de complexidade, Máquina abstrata, Máquina de Turing, Máquina de Turing não determinística, Negação, Neil Immerman, NP (complexidade), NP-completo, NP-difícil, P (complexidade), Problema de decisão, PSPACE, Redução (complexidade), Subconjunto, Teorema de Savitch, Vera Fischer, ZPP.
Axiomas de Blum
Na teoria da complexidade computacional, os axiomas de Blum ou axiomas de complexidade de Blum são axiomas que especificam propriedades desejáveis de medidas de complexidade no conjunto de funções computáveis.
Novo!!: Classe de complexidade e Axiomas de Blum · 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!!: Classe de complexidade e Complexidade computacional · Veja mais »
Conjunção lógica
A conjunção é uma operação na lógica matemática, que pode ser ligada à operação de interseção de conjuntos.
Novo!!: Classe de complexidade e Conjunção lógica · Veja mais »
David Stifler Johnson
David Stifler Johnson (9 de dezembro de 1945 – 8 de março de 2016) foi um cientista da computação estadunidense especializado em algoritmos e otimização.
Novo!!: Classe de complexidade e David Stifler Johnson · Veja mais »
Disjunção lógica
Disjunção, operador ou (OR), é uma operação lógica utilizada em lógicas digitais e lógicas matemáticas.
Novo!!: Classe de complexidade e Disjunção lógica · Veja mais »
Gramática livre de contexto
A gramática livre de contexto (GLC), em teoria de linguagem formal, é uma gramática formal onde todas as regras de produções são da forma A\ \to\ \alpha A é um símbolo não terminal, e \alpha é uma cadeia de terminal e/ou não terminais (\alpha pode ser vazia). Uma linguagem formal é considerada “livre do contexto” quando suas regras de produções podem ser aplicadas independentemente do contexto do simbolo não terminal.
Novo!!: Classe de complexidade e Gramática livre de contexto · Veja mais »
Gramática regular
Em Teoria da computação as Gramáticas regulares também conhecida como Tipo 3 da Hierarquia de Chomsky, é uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples.
Novo!!: Classe de complexidade e Gramática regular · Veja mais »
Gramática sensível ao contexto
Em Teoria da computação uma gramática sensível ao contexto (GSC), também conhecida como Tipo 1 da Hierarquia de Chomsky, é uma gramática formal em que os lados esquerdo e direito de qualquer regra de produção podem ser cercados por um contexto de símbolo terminal e símbolo não-terminal.
Novo!!: Classe de complexidade e Gramática sensível ao contexto · 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!!: Classe de complexidade e Grande-O · Veja mais »
Lógica matemática
A lógica matemática é uma subárea da matemática que explora as aplicações da lógica formal para a matemática.
Novo!!: Classe de complexidade e Lógica matemática · Veja mais »
Linguagem recursiva
A linguagem recursiva em matemática, lógica e ciência da computação, uma linguagem formal (a definir de sequências finitas de símbolos tomados de um fixo alfabeto) é chamada recursiva se é um subconjunto recursivo no conjunto de todas as palavras possíveis sobre o alfabeto da linguagem.
Novo!!: Classe de complexidade e Linguagem recursiva · Veja mais »
Linguagem recursivamente enumerável
Em matemática, lógica e ciência da computação, uma linguagem recursivamente enumerável é um tipo de Linguagem formal que também é chamada de linguagem Turing-reconhecível.
Novo!!: Classe de complexidade e Linguagem recursivamente enumerável · Veja mais »
Lista de classes de complexidade
Essa é uma lista de classes de complexidade da teoria da complexidade computacional.
Novo!!: Classe de complexidade e Lista de classes de complexidade · Veja mais »
Máquina abstrata
Uma máquina abstrata (ou computador abstrato) é um modelo teórico de um sistema computacional de hardware ou software usado para detalhar o funcionamento do sistema,Macura usado na teoria dos autômatos.
Novo!!: Classe de complexidade e Máquina abstrata · Veja mais »
Máquina de Turing
Representação artística de uma máquina de Turing A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).
Novo!!: Classe de complexidade e Máquina de Turing · Veja mais »
Máquina de Turing não determinística
Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.
Novo!!: Classe de complexidade e Máquina de Turing não determinística · Veja mais »
Negação
Negação, em lógica e matemática, é uma operação unária sobre valores lógicos, por exemplo o valor lógico de uma proposição.
Novo!!: Classe de complexidade e Negação · Veja mais »
Neil Immerman
Neil Immerman (24 de novembro de 1953, cidade de Manhasset, Nova Iorque) é um teórico cientista da computação americano, professor de ciência da computação da Universidade de Massachusetts Amherst.
Novo!!: Classe de complexidade e Neil Immerman · 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!!: Classe de complexidade 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!!: Classe de complexidade 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!!: Classe de complexidade e NP-difícil · 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!!: Classe de complexidade e P (complexidade) · Veja mais »
Problema de decisão
Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.
Novo!!: Classe de complexidade e Problema de decisão · Veja mais »
PSPACE
Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço.
Novo!!: Classe de complexidade e PSPACE · Veja mais »
Redução (complexidade)
Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro.
Novo!!: Classe de complexidade e Redução (complexidade) · 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!!: Classe de complexidade e Subconjunto · Veja mais »
Teorema de Savitch
Na teoria da complexidade computacional, o teorema de Savitch, provado por Walter Savitch em 1970, afirma que para toda função ƒ(n) ≥ log(n), em outras palavras, se uma máquina de Turing não-determinística pode resolver um problema usando um espaço f(n) (polinomial), uma máquina de Turing determinística ordinária pode resolver o mesmo problema dentro dessa região delimitada.
Novo!!: Classe de complexidade e Teorema de Savitch · Veja mais »
Vera Fischer
Vera Fischer (Blumenau, 27 de novembro de 1951) é uma atriz e ex-modelo brasileira.
Novo!!: Classe de complexidade e Vera Fischer · Veja mais »
ZPP
Na Teoria da complexidade computacional, ZPP (inglês: Zero-error Probabilistic Polinomial time, Probalístico de tempo polinominal sem erros) é a classe complexa de problemas em que uma Máquina de Turing existe com estas propriedades.
Novo!!: Classe de complexidade e ZPP · Veja mais »
