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!
 

Problema de decisão

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

14 relações: Andrew Hodges, Complexidade computacional, Conjunto recursivo, Conjuntos recursivamente enumeráveis, Constance Reid, David Hilbert, Entscheidungsproblem, Kurt Gödel, Linguagem formal, Número primo, Otimização, Sistema formal, Teoria da computabilidade, Teoria dos grafos.

Andrew Hodges

Andrew Hodges (Londres, 1949) é um escritor e matemático britânico.

Novo!!: Problema de decisão e Andrew Hodges · 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!!: Problema de decisão e Complexidade computacional · Veja mais »

Conjunto recursivo

Na teoria da computabilidade, um conjunto de números naturais é chamado recursivo, computável ou decidível se existe um algoritmo que termina após uma quantidade finita de tempo e decide corretamente se um número pertence ou não ao conjunto.

Novo!!: Problema de decisão e Conjunto recursivo · Veja mais »

Conjuntos recursivamente enumeráveis

Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se.

Novo!!: Problema de decisão e Conjuntos recursivamente enumeráveis · Veja mais »

Constance Reid

Constance Bowman Reid (St. Louis, Missouri, — São Francisco, Califórnia) foi autora de diversas biografias de matemáticos e livros populares sobre matemática.

Novo!!: Problema de decisão e Constance Reid · Veja mais »

David Hilbert

David Hilbert (Königsberg, — Göttingen) foi um matemático alemão.

Novo!!: Problema de decisão e David Hilbert · Veja mais »

Entscheidungsproblem

O Entscheidungsproblem (termo alemão para "problema de decisão") é um problema da lógica simbólica que consiste em achar um algoritmo genérico para determinar se um dado enunciado da lógica de primeira ordem pode ser provado.

Novo!!: Problema de decisão e Entscheidungsproblem · Veja mais »

Kurt Gödel

Kurt Friedrich Gödel (Brünn, Áustria-Hungria, — Princeton, Estados Unidos) foi um filósofo, matemático e lógico austríaco, naturalizado norte-americano.

Novo!!: Problema de decisão e Kurt Gödel · 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!!: Problema de decisão e Linguagem formal · Veja mais »

Número primo

Número primo é qualquer número p cujo conjunto dos divisores não inversíveis não é vazio, e todos os seus elementos são produtos de p por números inteiros inversíveis.

Novo!!: Problema de decisão e Número primo · Veja mais »

Otimização

O ponto de máximo em um paraboloide. Em matemática, o termo otimização refere-se ao estudo de problemas em que se busca minimizar ou maximizar uma função através da escolha sistemática dos valores de variáveis reais ou inteiras dentro de um conjunto viável.

Novo!!: Problema de decisão e Otimização · Veja mais »

Sistema formal

Um sistema formal ou sistema lógico é, por assim dizer, qualquer sistema de pensamento abstrato bem definido, em um modelo matemático.

Novo!!: Problema de decisão e Sistema formal · Veja mais »

Teoria da computabilidade

A teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 30 com o estudo das funções computáveis e dos graus de Turing.

Novo!!: Problema de decisão e Teoria da computabilidade · Veja mais »

Teoria dos grafos

Grafo com quatro vértices e 6 arestas. É um grafo completo, conexo e planar. A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.

Novo!!: Problema de decisão e Teoria dos grafos · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »