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