Acesso mais rápido do que o navegador!
103 relações: AC, Alemanha, Algoritmo, Algoritmo de Shor, Algoritmo probabilístico, Análise de algoritmos, Análise numérica, Aritmética de Presburger, Autómato celular, Autômato linearmente limitado, Axiomas de Blum, Boris Trakhtenbrot, BPP, BQP, Cambridge University Press, Campo de número de peneira geral, Ciência da computação teórica, Classe de complexidade, Clay Mathematics Institute, Cobertura de vértices (teoria dos grafos), Combinatória, Complexidade de comunicação, Computação paralela, Dólar, Distribuição de probabilidade, DSPACE, Dtime, Equação diferencial, EXPSPACE, Exptime, Fatoração de inteiros, Função parcial, Grande-O, Instituto de Tecnologia de Massachusetts, Investigação operacional, IP (complexidade), Jogo da vida, John Wiley & Sons, László Babai, Leonid Levin, Linguagem de programação, Linguagem formal, Lista de adjacência, Lista de termos relacionados aos algoritmos e às estruturas de dados, Logaritmo discreto, Logística, LSPACE, Manuel Blum, Matemática, Matemática pura, ..., Matriz de adjacência, Máquina de Turing, Máquina de Turing alternada, Máquina de Turing multifita, Máquina de Turing não determinística, Máquina de Turing probabilística, Máquina de Turing quântica, Modelo de árvore de decisão, Modelo de computação, Número inteiro, Número natural, Número primo, NC, NEXPTIME, NP (complexidade), NP-completo, NP-difícil, NSPACE, NTIME, P (complexidade), P versus NP, Porta lógica, Problema computacional, Problema da mochila, Problema de decisão, Problema de função, Problema de satisfatibilidade booliana, Problema do caixeiro-viajante, Problema do caminho hamiltoniano, Problemas do Prémio Millennium, Problemas em aberto da ciência da computação, Programação inteira, PSPACE, QMA, Quicksort, Raymond Smullyan, Regulação, Richard Karp, RP, RSA (sistema criptográfico), Sistema de numeração binário, Sistema dinâmico, Springer Science+Business Media, Stephen Cook, Teorema da aceleração de Blum, Teorema de Savitch, Teoria da computação, Teoria da computabilidade, Teoria dos grafos, Tese de Church-Turing, Tese de Cobham, Teste de primalidade, ZPP. Expandir índice (53 mais) »
AC
Sem descrição
Novo!!: Complexidade computacional e AC · Veja mais »
Alemanha
Alemanha (Deutschland), oficialmente República Federal da Alemanha (Bundesrepublik Deutschland, 10px ouça), é um país localizado na Europa Central. É limitado, a norte, pelo mar do Norte, Dinamarca e mar Báltico; a leste, pela Polônia e Chéquia; a sul, pela Áustria e Suíça e, a oeste, pela França, Luxemburgo, Bélgica e Países Baixos. O território da Alemanha abrange 357.021 quilômetros quadrados e é influenciado por um clima temperado sazonal. Com 82,8 milhões de habitantes, em 31 de dezembro de 2015, o país tem a maior população da União Europeia e é também o lar da terceira maior população de migrantes internacionais em todo o mundo. A região chamada Germânia, habitada por vários povos germânicos, foi conhecida e documentada pelos romanos antes do ano 100. A partir do, os territórios alemães formaram a parte central do Sacro Império Romano-Germânico, que durou até 1806. Durante o, o norte da Alemanha tornou-se o centro da Reforma Protestante. Como um moderno Estado-nação, o país foi unificado pela primeira vez, em consequência da Guerra Franco-Prussiana, em 1871. Em 1949, após a Segunda Guerra Mundial, a Alemanha foi dividida em dois estados, a Alemanha Ocidental, oficialmente "República Federal da Alemanha", e a "Alemanha Oriental", oficialmente República Democrática Alemã, ao longo das linhas de ocupação aliadas. A Alemanha foi reunificada em 1990. A Alemanha Ocidental foi um dos membros fundadores da Comunidade Europeia (CE), em 1957, que, posteriormente, se tornou na União Europeia, em 1993. O país é parte do espaço Schengen e passou a adotar a moeda europeia, o euro, desde quando foi instituído, em 1999. A Alemanha é uma república parlamentar federal de dezesseis estados (em alemão Länder). A capital e maior cidade do país é Berlim, localizada no nordeste do território alemão. O país é membro das Nações Unidas, da OTAN, G8, G20, da OCDE e da OMC. É uma grande potência com a quarta maior economia do mundo por PIB nominal e a quinta maior em paridade do poder de compra. É o segundo maior exportador e o segundo maior importador de mercadorias. Em termos absolutos, a Alemanha atribui o segundo maior orçamento anual de ajudas ao desenvolvimento no mundo, enquanto está em sexto lugar em despesas militares. O país tem desenvolvido um alto padrão de vida e estabeleceu um sistema global de segurança social. A Alemanha ocupa uma posição-chave nos assuntos europeus e mantém uma série de parcerias estreitas em um nível global. O país também é reconhecido como líder científico e tecnológico em vários domínios.
Novo!!: Complexidade computacional e Alemanha · Veja mais »
Algoritmo
Uma animação do algoritmo de ordenação quicksort de uma matriz de valores ao acaso. As barras vermelhas marcam o elemento pivô. No início da animação, estando o elemento para o lado direito, é escolhido como o pivô Em matemática e ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema.
Novo!!: Complexidade computacional e Algoritmo · Veja mais »
Algoritmo de Shor
Na teoria da complexidade computacional e em Computação quântica, o algoritmo de Shor, batizado em homenagem ao matemático Peter Shor, é um algoritmo quântico para fatorar um número N não primo de L bits.
Novo!!: Complexidade computacional e Algoritmo de Shor · Veja mais »
Algoritmo probabilístico
Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica.
Novo!!: Complexidade computacional e Algoritmo probabilístico · Veja mais »
Análise de algoritmos
Em ciência da computação, a análise de algoritmos tem como função determinar os recursos necessários para executar um dado algoritmo.
Novo!!: Complexidade computacional e Análise de algoritmos · Veja mais »
Análise numérica
''Clay tablet'' Babilônio YBC 7289(c. 1800–1600 BCE) http://www.math.ubc.ca/~cass/Euclid/ybc/ybc.html com anotações. (Imagem por Bill Casselman) A análise numérica é o estudo de algoritmos de aproximação para a solução de problemas matemáticos.
Novo!!: Complexidade computacional e Análise numérica · Veja mais »
Aritmética de Presburger
A Aritmética de Presburger é uma teoria de primeira-ordem dos números naturais com soma.
Novo!!: Complexidade computacional e Aritmética de Presburger · Veja mais »
Autómato celular
0-14-016734-X Um celular (AC) é um modelo discreto de computação estudado na teoria dos autômatos.
Novo!!: Complexidade computacional e Autómato celular · Veja mais »
Autômato linearmente limitado
Um Autômato linearmente limitado é uma Máquina de Turing com memória limitada e é o mecanismo reconhecedor de Linguagens sensíveis ao contexto.
Novo!!: Complexidade computacional e Autômato linearmente limitado · Veja mais »
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!!: Complexidade computacional e Axiomas de Blum · Veja mais »
Boris Trakhtenbrot
Boris (Boaz) Avraamovich Trakhtenbrot (Борис Авраамович Трахтенброт; Brichevo, –) ou Boaz (Boris) Trakhtenbrot (בועז טרכטנברוט) foi um matemático russo-israelense.
Novo!!: Complexidade computacional e Boris Trakhtenbrot · Veja mais »
BPP
Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de problemas de decisão solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias.
Novo!!: Complexidade computacional e BPP · Veja mais »
BQP
A relação suspeita entre '''BQP''' para outros espaços de problemasMichael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. Em Teoria da Complexidade Computacional, BQP (do inglês bounded error quantum polynomial time) é a classe de problemas de decisão solúveis por um computador quântico em tempo polinomial, com uma probabilidade de erro de até 1/3 para todas as instâncias.
Novo!!: Complexidade computacional e BQP · Veja mais »
Cambridge University Press
Cambridge University Press é uma editora britânica, fundada em 1534 com o aval do rei Henrique VIII para a Universidade de Cambridge, sendo a editora mais antiga do mundo em operação contínua e a segunda maior editora universitária do mundo.
Novo!!: Complexidade computacional e Cambridge University Press · Veja mais »
Campo de número de peneira geral
Na teoria dos números, um ramo da matemática, o campo de número de peneira geral, (GNFS) é o mais eficiente algoritmo clássico, conhecido por fatorar inteiros maiores do que 100 dígitos.
Novo!!: Complexidade computacional e Campo de número de peneira geral · Veja mais »
Ciência da computação teórica
Ciência da computação teórica (TCS) ou informática teórica é uma divisão ou subconjunto de ciências da computação e matemática que incide sobre os aspectos mais abstratos ou matemáticos da computação e inclui a teoria da computação.
Novo!!: Complexidade computacional e Ciência da computação teórica · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: Complexidade computacional e Classe de complexidade · Veja mais »
Clay Mathematics Institute
O Clay Mathematics Institute (CMI) é uma fundação privada sem fins lucrativos, baseada em Cambridge, Massachusetts.
Novo!!: Complexidade computacional e Clay Mathematics Institute · 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 computacional e Cobertura de vértices (teoria dos grafos) · Veja mais »
Combinatória
A combinatória é um ramo da matemática que estuda coleções finitas de elementos que satisfazem critérios específicos determinados e se preocupa, em particular, com a "contagem" de elementos nessas coleções (combinatória enumerativa), com decidir se certo objeto "ótimo" existe (combinatória extremal) e com estruturas "algébricas" que esses objetos possam ter (combinatória algébrica).
Novo!!: Complexidade computacional e Combinatória · Veja mais »
Complexidade de comunicação
A noção de complexidade de comunicação foi introduzida por Yao em 1979, que investigou o seguinte problema envolvendo duas partes (Alice e Bob).
Novo!!: Complexidade computacional e Complexidade de comunicação · Veja mais »
Computação paralela
Computação paralela é uma forma de computação em que vários cálculos são realizados ao mesmo tempo, operando sob o princípio de que grandes problemas geralmente podem ser divididos em problemas menores, que então são resolvidos concorrentemente (em paralelo).
Novo!!: Complexidade computacional e Computação paralela · Veja mais »
Dólar
O dólar (símbolo: $) é o nome comum de moedas oficiais de 9 países: Austrália, Canadá, Estados Unidos, Hong Kong, Jamaica, Namíbia, Nova Zelândia, Singapura e Taiwan.
Novo!!: Complexidade computacional e Dólar · Veja mais »
Distribuição de probabilidade
Em teoria da probabilidade e em estatística, uma distribuição de probabilidade descreve o comportamento aleatório de um fenômeno dependente do acaso.
Novo!!: Complexidade computacional e Distribuição de probabilidade · Veja mais »
DSPACE
Em complexidade computacional, DSPACE ou simplesmente SPACE é um recurso computacional descrevendo a disponibilidade de memória para uma máquina de Turing.
Novo!!: Complexidade computacional e DSPACE · Veja mais »
Dtime
Na teoria da complexidade computacional, DTIME (ou TIME) é o recurso computacional de tempo de computação para uma máquina de Turing determinística.
Novo!!: Complexidade computacional e Dtime · Veja mais »
Equação diferencial
Soluções de uma equação diferencial (a negro) e as respectivas condições iniciais (a vermelho). Em matemática, uma equação diferencial é uma equação cuja incógnita é uma função que aparece na equação sob a forma das respectivas derivadas.
Novo!!: Complexidade computacional e Equação diferencial · Veja mais »
EXPSPACE
Em teoria da complexidade computacionais, EXPSPACE é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em espaço O(2p(n)) onde p(n) é uma função polinomial de n. (Alguns autores restringem p(n) para uma função linear, mas a maioria chama a classe resultante de ESPACE.) Se, por outro lado, nós usamos uma máquina não determinísitica, teremos a classe NEXPSPACE, que é igual a EXPSPACE pelo teorema de savitch.
Novo!!: Complexidade computacional e EXPSPACE · Veja mais »
Exptime
Na teoria da complexidade computacional, a classe de complexidade Exptime (às vezes chamado EXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em O(2p(n)) tempo, onde p (n) é uma função polinomial de n. Em termos de DTIME, Sabemos que e também, pelo time hierarchy theoremeo space hierarchy theorem, que assim pelo menos uma das três primeiras inclusões e pelo menos uma das três últimas inclusões deve ser adequada, mas não se sabe quais são.
Novo!!: Complexidade computacional e Exptime · Veja mais »
Fatoração de inteiros
Na teoria dos números, a fatoração de inteiros é a decomposição de um número composto em um produto de números inteiros menores.
Novo!!: Complexidade computacional e Fatoração de inteiros · Veja mais »
Função parcial
Em matemática, uma função parcial é quase uma função, falhando na definição, porque para nem todos x do domínio existe algum f(x).
Novo!!: Complexidade computacional e Função parcial · 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!!: Complexidade computacional e Grande-O · Veja mais »
Instituto de Tecnologia de Massachusetts
Instituto de Tecnologia de Massachusetts (Massachusetts Institute of Technology) é uma universidade de pesquisa localizada em Cambridge, Massachusetts, Estados Unidos.
Novo!!: Complexidade computacional e Instituto de Tecnologia de Massachusetts · Veja mais »
Investigação operacional
A pesquisa operacional (PO), ou investigação operacional (IO), é um ramo interdisciplinar da matemática aplicada que faz uso de modelos matemáticos, estatísticos e de algoritmos na ajuda à tomada de decisão.
Novo!!: Complexidade computacional e Investigação operacional · Veja mais »
IP (complexidade)
Em Teoria da complexidade computacional, a classe IP (abreviação de Interactive Polynomial Time (Tempo Polinomial Interativo)) é a classe de problemas solúveis em tempo polinomial por um sistema de prova interativa.
Novo!!: Complexidade computacional e IP (complexidade) · Veja mais »
Jogo da vida
thumb Gosper'' criando ''planadores''. O jogo da vida é um autómato celular desenvolvido pelo matemático britânico John Horton Conway em 1970.
Novo!!: Complexidade computacional e Jogo da vida · Veja mais »
John Wiley & Sons
A John Wiley & Sons, Inc.
Novo!!: Complexidade computacional e John Wiley & Sons · Veja mais »
László Babai
László (Laci) Babai (Budapeste) é um matemático e cientista da computação húngaro.
Novo!!: Complexidade computacional e László Babai · Veja mais »
Leonid Levin
Leonid Anatolievich Levin, Леонид Анатольевич Левин; (Dnipropetrovsk, 2 de novembro de 1948) é um informático soviético-estadunidense.
Novo!!: Complexidade computacional e Leonid Levin · Veja mais »
Linguagem de programação
C. A linguagem de programação é um método padronizado, formado por um conjunto de regras sintáticas e semânticas, de implementação de um código fonte - que pode ser compilado e transformado em um programa de computador, ou usado como script interpretado - que informará instruções de processamento ao computador.
Novo!!: Complexidade computacional e Linguagem de programação · 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!!: Complexidade computacional e Linguagem formal · Veja mais »
Lista de adjacência
Em teoria dos grafos, uma lista de adjacência, estrutura de adjacência ou dicionário é a representação de todas arestas ou arcos de um grafo em uma lista.
Novo!!: Complexidade computacional e Lista de adjacência · Veja mais »
Lista de termos relacionados aos algoritmos e às estruturas de dados
* Abstração.
Novo!!: Complexidade computacional e Lista de termos relacionados aos algoritmos e às estruturas de dados · Veja mais »
Logaritmo discreto
Na matemática, especialmente em álgebra abstrata e suas aplicações, logaritmos discretos são grupos análogos a logaritmos naturais.
Novo!!: Complexidade computacional e Logaritmo discreto · Veja mais »
Logística
Por dentro das instalações da Nexus Distribution, uma empresa americana com base logística. Imagem mostra mercadorias empilhadas em paletes com empilhadeira A logística (gr. logistikḗ, f.fem. de logistikós,ḗ,ón 'relativo ao cálculo; que diz respeito ao raciocínio') é uma especialidade da administração e engenharia responsável por prover recursos e informações para a execução de todas as atividades de uma organização.
Novo!!: Complexidade computacional e Logística · 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!!: Complexidade computacional e LSPACE · Veja mais »
Manuel Blum
Manuel Blum (Caracas, 26 de abril de 1938) é um informático venezuelano.
Novo!!: Complexidade computacional e Manuel Blum · Veja mais »
Matemática
problemas matemáticos Matemática (dos termos gregos: μάθημα, transliterado máthēma, 'ciência', conhecimento' ou 'aprendizagem; e μαθηματικός, transliterado mathēmatikós, 'inclinado a aprender') é a ciência do raciocínio lógico e abstrato, que estuda quantidades (teoria dos números), espaço e medidas (geometria), estruturas, variações e estatística.
Novo!!: Complexidade computacional e Matemática · Veja mais »
Matemática pura
A matemática pura é a matemática que não tem ou não necessita se preocupar com sua possível aplicação em uma determinada área do conhecimento, sendo considerada uma matemática "estética".
Novo!!: Complexidade computacional e Matemática pura · Veja mais »
Matriz de adjacência
Uma matriz de adjacência é uma das formas de se representar um grafo.
Novo!!: Complexidade computacional e Matriz de adjacência · 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!!: Complexidade computacional e Máquina de Turing · Veja mais »
Máquina de Turing alternada
Em complexidade de computação teórica, uma máquina de Turing alternada (MTA) é uma máquina de Turing não-determinística (MTN) com a regra que aceita computações que generalizam regras usadas na definição da complexidade das classes NP e co-NP.
Novo!!: Complexidade computacional e Máquina de Turing alternada · Veja mais »
Máquina de Turing multifita
Uma máquina de Turing multifita é uma máquina de Turing comum com várias fitas.
Novo!!: Complexidade computacional e Máquina de Turing multifita · 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!!: Complexidade computacional e Máquina de Turing não determinística · Veja mais »
Máquina de Turing probabilística
Em Teoria da Computabilidade, uma máquina de Turing probabilística é uma Máquina de Turing não determinística que escolhe aleatoriamente dentre as transições a cada ponto, de acordo com alguma distribuição de probabilidade.
Novo!!: Complexidade computacional e Máquina de Turing probabilística · Veja mais »
Máquina de Turing quântica
Uma máquina de Turing quântica, ou também computador quântico universal é uma máquina abstrata usada para modelar o efeito de um computador quântico.
Novo!!: Complexidade computacional e Máquina de Turing quântica · Veja mais »
Modelo de árvore de decisão
Em complexidade computacional e complexidade de comunicação o modelo de árvore de decisão é o modelo de computação ou comunicação no qual um algoritmo ou processo de comunicação é considerado basicamente uma árvore de decisão, ou seja, uma sequência de operações ramificadas baseadas em comparações de quantidades, sendo as comparações atribuidas uma unidade de custo computacional.
Novo!!: Complexidade computacional e Modelo de árvore de decisão · Veja mais »
Modelo de computação
Em teoria da computabilidade, um modelo de computação é a definição de um conjunto de operações que podem ser usadas numa computação e seus respectivos custos.
Novo!!: Complexidade computacional e Modelo de computação · Veja mais »
Número inteiro
Um número inteiro é um número que pode ser escrito sem um componente fracional.
Novo!!: Complexidade computacional e Número inteiro · Veja mais »
Número natural
Um número natural é um número inteiro não negativo \. Em alguns contextos, número natural é definido como um número inteiro positivo, sendo também o zero considerado como um número natural (mesmo não sendo positivo e sim nulo/neutro): \. O conjunto dos números naturais é, comumente, denotado pelo símbolo \mathbb.
Novo!!: Complexidade computacional e Número natural · Veja mais »
Número primo
Números primos são os números naturais maiores que um que não são produtos de dois números naturais menores 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!!: Complexidade computacional e Número primo · Veja mais »
NC
* Carolina do Norte, um Estado dos Estados Unidos.
Novo!!: Complexidade computacional e NC · Veja mais »
NEXPTIME
Em teoria da complexidade, NEXPSPACE (também chamada de NEXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing não determinística em espaço O(2p(n)) para uma dada p(n) e espaço ilimitado.
Novo!!: Complexidade computacional e NEXPTIME · 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!!: Complexidade computacional 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!!: Complexidade computacional 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 computacional e NP-difícil · Veja mais »
NSPACE
Em teoria da complexidade computational, a classe de complexidade NSPACE(f(n)) é um conjunto de problemas de decisão que podem ser resolvido por uma máquina de Turing não-determinística usando espaço O(f(n)), e tempo ilimitado.
Novo!!: Complexidade computacional e NSPACE · Veja mais »
NTIME
Na teoria da complexidade computacional, a classe de complexidade NTIME(f(n)) é o conjunto dos problemas de decisão que podem ser solucionado por uma máquina de Turing não-determinística usando um tempo O(f(n)) e espaço ilimitado.
Novo!!: Complexidade computacional e NTIME · 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!!: Complexidade computacional e P (complexidade) · Veja mais »
P versus NP
O problema "P versus NP" é o principal problema aberto da Ciência da Computação.
Novo!!: Complexidade computacional e P versus NP · Veja mais »
Porta lógica
Porta NAND: esquema do circuito integrado e ''hardware'' Portas ou circuitos lógicos são dispositivos que operam e trabalham com um ou mais sinais lógicos de entrada para produzir uma e somente uma saída, dependente da função implementada no circuito.
Novo!!: Complexidade computacional e Porta lógica · 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 computacional e Problema computacional · 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!!: Complexidade computacional e Problema da mochila · 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!!: Complexidade computacional e Problema de decisão · Veja mais »
Problema de função
Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma função total) é esperada pra cada entrada, mas a sáida é mais complexa do que um problema de decisão, isto é, não é apenas SIM ou NÃO.
Novo!!: Complexidade computacional e Problema de função · Veja mais »
Problema de satisfatibilidade booliana
Na teoria da complexidade computacional, o problema de satisfatibilidade booliana (do inglês boolean satisfiability problem, muitas vezes abreviado como SATISFIABILITY ou SAT) foi o primeiro problema identificado como pertencente à classe de complexidade NP-completo.
Novo!!: Complexidade computacional e Problema de satisfatibilidade booliana · 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!!: Complexidade computacional e Problema do caixeiro-viajante · Veja mais »
Problema do caminho hamiltoniano
No campo matemático da teoria dos grafos o Problema do caminho hamiltoniano e o Problema do ciclo hamiltoniano são problemas de determinar se um Caminho hamiltoniano ou um Ciclo hamiltoniano existe em um dado grafo (direcionado ou não direcionado).
Novo!!: Complexidade computacional e Problema do caminho hamiltoniano · Veja mais »
Problemas do Prémio Millennium
Os Prêmios dos Problemas do Milênio (em inglês: Millennium Prize Problems) são sete problemas matemáticos estabelecidos pelo Instituto Clay de Matemática.
Novo!!: Complexidade computacional e Problemas do Prémio Millennium · Veja mais »
Problemas em aberto da ciência da computação
Este artigo é uma lista de problemas em aberto na Ciência da computação.
Novo!!: Complexidade computacional e Problemas em aberto da ciência da computação · Veja mais »
Programação inteira
Um Problema de Programação Inteira é um modelo de programação linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros.
Novo!!: Complexidade computacional e Programação inteira · 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!!: Complexidade computacional e PSPACE · Veja mais »
QMA
QMA, na teoria da complexidade, que vem de Quantum Merlin Arthur, é uma classe de complexidade análoga à classe NP ou à classe de complexidade probabilística MA.
Novo!!: Complexidade computacional e QMA · Veja mais »
Quicksort
O algoritmo quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante.
Novo!!: Complexidade computacional e Quicksort · Veja mais »
Raymond Smullyan
Raymond Merrill Smullyan (Far Rockaway, 25 de maio de 1919 – 6 de fevereiro de 2017) foi um matemático estadunidense, pianista, lógico, filósofo taoísta e mágico.
Novo!!: Complexidade computacional e Raymond Smullyan · Veja mais »
Regulação
O conceito de regulação (do latim, regula - vara reta, barra, régua; relacionado ao v.lat. regere - reger, ordenar, controlar, dirigir, guiar - ver reta) permeia, de forma geral, diversas áreas do conhecimento humano, como as tratadas pelas disciplinas técnico-científicas da administração, da cibernética, do direito, da economia, da educação, das engenharias, e dos sistemas dinâmicos, entre outras.
Novo!!: Complexidade computacional e Regulação · Veja mais »
Richard Karp
Richard Manning Karp (Boston) é um cientista da computação e teórico computacional da Universidade da California, Berkeley, reconhecido pela sua pesquisa sobre teoria dos algoritmos, pelo qual recebeu um Prêmio Turing em 1985, Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004, e o Prêmio Kyoto em 2008.
Novo!!: Complexidade computacional e Richard Karp · Veja mais »
RP
* Relações públicas — conjunto de atividades informativas relacionadas com o intercâmbio de informações entre um indivíduo ou organização e o seu público.
Novo!!: Complexidade computacional e RP · Veja mais »
RSA (sistema criptográfico)
Adi Shamir, um dos criadores do RSA RSA (Rivest-Shamir-Adleman) é um dos primeiros sistemas de criptografia de chave pública e é amplamente utilizado para transmissão segura de dados.
Novo!!: Complexidade computacional e RSA (sistema criptográfico) · Veja mais »
Sistema de numeração binário
O sistema binário ou de base 2 é um sistema de numeração posicional em que todas as quantidades se representam com base em dois números, ou seja, zero e um (0 e 1).
Novo!!: Complexidade computacional e Sistema de numeração binário · Veja mais »
Sistema dinâmico
atrator de Lorenz é um exemplo de sistema dinâmico não-linear. O estudo deste sistema incentivou a criação da teoria do Caos. Na física matemática e na matemática, sistema dinâmico é um conceito no qual uma função descreve a relação no tempo de um ponto em um espaço geométrico.
Novo!!: Complexidade computacional e Sistema dinâmico · Veja mais »
Springer Science+Business Media
Springer Science+Business Media ou Springer-Verlag, ou ainda, simplesmente Springer é uma editora mundial baseada na Alemanha, a qual publica livros-texto, livros de referência acadêmica, e periódicos de artigos com revisão por pares (peer-review), com foco em ciência, tecnologia, matemática, e medicina.
Novo!!: Complexidade computacional e Springer Science+Business Media · Veja mais »
Stephen Cook
Stephen Arthur Cook, (Buffalo) é um cientista da computação e matemático estadunidense-canadense, que teve maior contribuição no campo da teoria da complexidade e complexidade de prova.
Novo!!: Complexidade computacional e Stephen Cook · Veja mais »
Teorema da aceleração de Blum
Na teoria da complexidade computacional, o teorema da aceleração de Blum ou teorema do aumento da velocidade de Blum (do inglês, Blum's speedup theorem), inicialmente definido por Manuel Blum em 1967, é um teorema fundamental sobre a complexidade de funções computáveis.
Novo!!: Complexidade computacional e Teorema da aceleração de Blum · 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!!: Complexidade computacional e Teorema de Savitch · Veja mais »
Teoria da computação
A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação.
Novo!!: Complexidade computacional e Teoria da computação · 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 1930 com o estudo das funções computáveis e do grau de Turing.
Novo!!: Complexidade computacional 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 ou de grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.
Novo!!: Complexidade computacional e Teoria dos grafos · Veja mais »
Tese de Church-Turing
Na teoria da computabilidade, a Tese de Church-Turing ou Tese de Church, assim nomeada em referência a Alonzo Church e Alan Turing, é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar.
Novo!!: Complexidade computacional e Tese de Church-Turing · Veja mais »
Tese de Cobham
A Tese de Cobham, também conhecida como a tese de Cobham–Edmonds (assim denominada em referência a Alan Cobham e Jack Edmonds), assegura que problemas computacionais podem ser resolvidos de maneira viável em algum dispositivo de computação apenas se forem computáveis em tempo polinomial, ou seja, se pertencerem à classe de complexidade P.
Novo!!: Complexidade computacional e Tese de Cobham · Veja mais »
Teste de primalidade
Um teste de primalidade é um algoritmo para determinar se um dado número inteiro é primo.
Novo!!: Complexidade computacional e Teste de primalidade · 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!!: Complexidade computacional e ZPP · Veja mais »
Redireciona aqui:
Computação factível, Teoria da complexidade, Teoria da complexidade computacional, Teoria de complexidade computacional.
