- 1. A teoria da complexidade computacional é um ramo da ciência teórica da computação que se centra na classificação dos problemas computacionais com base na sua dificuldade inerente e na quantidade de recursos necessários, como o tempo e o espaço. Trata de compreender a eficiência dos algoritmos, analisar a viabilidade de resolver problemas em diferentes tipos de máquinas e determinar as limitações do poder computacional. Ao estudar a teoria da complexidade computacional, os investigadores procuram investigar os limites da computação e identificar as capacidades e limitações dos computadores na resolução de vários tipos de problemas.
Em que se centra a teoria da complexidade computacional?
A) Analisar os recursos necessários para resolver problemas computacionais
B) Aspectos psicológicos da interação homem-computador
C) Conceção de hardware para computadores
D) Desenvolvimento de novas linguagens de programação
- 2. Que notação é normalmente utilizada para indicar a complexidade dos algoritmos?
A) Código binário
B) Números romanos
C) Notação Big O
D) Letras gregas
- 3. Que classe de complexidade contém problemas de decisão que são eficientemente verificáveis?
A) NP
B) PSPACE
C) BPP
D) EXP
- 4. Qual é a classe de complexidade que representa os problemas mais difíceis em NP?
A) NP-completo
B) BPP
C) P
D) EXPTIME
- 5. O que significa "EXP" na teoria da complexidade computacional?
A) Tempo exponencial
B) Perito
C) Exploratório
D) Expandido
- 6. Que classe de complexidade é utilizada para classificar os problemas que podem ser resolvidos por um computador quântico em tempo polinomial?
A) BQP
B) PSPACE
C) NP-completo
D) ESPAÇO
- 7. A que é que o teorema de Cook-Levin está relacionado na teoria da complexidade computacional?
A) NP-completude
B) Algoritmos quânticos
C) Problema P vs NP
D) Computação paralela
- 8. Qual é o principal objetivo da teoria da complexidade computacional?
A) Classificar os problemas computacionais com base na sua dificuldade inerente
B) Para criar computadores mais rápidos
C) Para gerar números aleatórios
D) Construir supercomputadores
|