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