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