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