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