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