Teoria da complexidade computacional - Questionário
A) Conceção de hardware para computadores B) Analisar os recursos necessários para resolver problemas computacionais C) Aspectos psicológicos da interação homem-computador D) Desenvolvimento de novas linguagens de programação
A) Números romanos B) Letras gregas C) Notação Big O D) Código binário
A) PSPACE B) BPP C) NP D) EXP
A) NP-completo B) P C) BPP D) EXPTIME
A) NP-completo B) ESPAÇO C) BQP D) PSPACE
A) Classificar os problemas computacionais com base na sua dificuldade inerente B) Para gerar números aleatórios C) Construir supercomputadores D) Para criar computadores mais rápidos
A) Problema P vs NP B) NP-completude C) Algoritmos quânticos D) Computação paralela
A) Expandido B) Perito C) Exploratório D) Tempo exponencial
A) Uma questão teórica que não tem solução. B) Uma equação matemática que não pode ser resolvida. C) Uma tarefa resolvida por um computador utilizando um algoritmo. D) Um problema de hardware em computadores.
A) O conjunto de todos os caracteres ASCII B) O alfabeto hexadecimal C) O conjunto de todas as letras minúsculas D) O alfabeto binário {0, 1}
A) Utilização exclusiva de notação decimal. B) Não é necessário utilizar nenhuma codificação. C) Uma escolha específica e concreta de codificação da entrada. D) Codificação utilizando linguagem natural.
A) Encontrar o caminho mais curto em um grafo. B) Determinar se um grafo dado é conexo ou não. C) Determinar o número de nós em um grafo. D) Calcular o fluxo máximo em uma rede.
A) Determinar se um número é primo. B) O problema do caixeiro-viajante. C) Verificar se um grafo é bipartido. D) Verificar se dois grafos são isomorfos.
A) Bits B) Caracteres C) Palavras D) Bytes
A) Um dispositivo para manipular objetos físicos. B) Uma tecnologia de computação prática. C) Um modelo teórico para a computação geral. D) Uma forma inicial de hardware de computador.
A) O teorema P vs NP. B) A tese de Church-Turing. C) Os teoremas da incompletude de Gödel. D) O teorema de Cook-Levin.
A) Máquina de Turing determinística. B) Máquina de Turing não determinística. C) Máquina de Turing quântica. D) Máquina de Turing probabilística.
A) Eles utilizam bits aleatórios para realizar cálculos. B) Eles exigem a possibilidade de implementação física. C) Eles operam de forma determinística. D) Eles são limitados a um tempo de execução polinomial.
A) Axiomas relacionados ao problema P vs NP B) Axiomas de complexidade de Blum C) Teorema de Cook-Levin D) Axiomas de completude de Turing
A) Complexidade de árvores de decisão B) Complexidade do entrelaçamento quântico C) Complexidade de circuitos D) Complexidade da comunicação
A) Gabriel Lamé B) Edmonds C) Juris Hartmanis D) Leonid Levin
A) co-P não seria igual a co-NP B) NP não seria igual a co-NP C) co-P seria igual a co-NP D) P não seria igual a NP
A) QMA B) NC C) IP D) BPP
A) Redução em tempo polinomial. B) Redução em tempo exponencial. C) Redução em tempo logarítmico. D) Redução em tempo linear.
A) NC B) L C) PP D) NL
A) Teorema de Cook-Levin B) Teorema da hierarquia de espaço C) Teorema da hierarquia de tempo D) Teorema de Savitch
A) Mertens, Stephan B) Fortnow, Lance; Homer, Steven C) Cook, Stephen D) Khalil, Hatem; Ulery, Dana
A) 1971 B) 1972 C) 1965 D) 1967
A) 1955 B) 1971 C) 1960 D) 1956
A) Conjuntos elementares B) Autômatos linearmente limitados C) Medidas de complexidade D) Cálculos em tempo real
A) Oded Goldreich B) Christos Papadimitriou C) Sanjeev Arora; Boaz Barak D) Michael R. Garey; David S. Johnson
A) Análise amortizada B) Complexidade no cenário médio C) Complexidade no melhor cenário D) Complexidade no pior cenário
A) #P B) BPP C) NC D) RP
A) Gabriel Lamé B) Richard E. Stearns C) Juris Hartmanis D) Alan Turing
A) 1950 B) 1965 C) 1936 D) 1945
A) Michael Sipser B) Sanjeev Arora C) Boaz Barak D) Christos Papadimitriou
A) Complexidade de circuitos B) Complexidade espacial C) Complexidade temporal D) Complexidade de comunicação
A) John Myhill B) Boris Trakhtenbrot C) Raymond Smullyan D) Hisao Yamada
A) Downey, Rod; Fellows, Michael B) Wuppuluri, Shyam; Doria, Francisco A. C) Cook, Stephen; Fortnow, Lance D) Papadimitriou, Christos; Sipser, Michael
A) AC B) QMA C) BPP D) RP
A) Boris Trakhtenbrot B) Raymond Smullyan C) John Myhill D) Hisao Yamada
A) co-NP B) BQP C) PP D) NP
A) Problema P vs NP B) Teorema de Savitch C) Teorema de Cook-Levin D) Teorema da hierarquia de tempo
A) "Complexidade computacional" B) "Função de sinalização" C) "Máquina de Turing" D) "Tempo polinomial"
A) Sistemas dinâmicos contínuos e equações diferenciais. B) Algoritmos probabilísticos. C) Processamento de sinais digitais. D) Máquinas de estados finitos.
A) Expressões booleanas. B) Estados quânticos. C) Grafos discretos. D) Funções contínuas.
A) PH B) PP C) MA D) BQP
A) 15 B) 10 C) 30 D) 21
A) NC B) BPP C) QMA D) AC
A) NP B) FP C) PSPACE D) EXPTIME
A) P B) EXPTIME C) NP D) TODOS
A) Sanjeev Arora; Boaz Barak B) Oded Goldreich C) Michael R. Garey; David S. Johnson D) Christos Papadimitriou |
Criado com That Quiz —
a página para criar testes de Matemática e de outras áreas.