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