- 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) 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
- 2. Que notação é normalmente utilizada para indicar a complexidade dos algoritmos?
A) Notação Big O
B) Números romanos
C) Letras gregas
D) Código binário
- 3. Que classe de complexidade contém problemas de decisão que são eficientemente verificáveis?
A) EXP
B) NP
C) PSPACE
D) BPP
- 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) Expandido
B) Perito
C) Exploratório
D) Tempo exponencial
- 6. Que classe de complexidade é utilizada para classificar os problemas que podem ser resolvidos por um computador quântico em tempo polinomial?
A) ESPAÇO
B) PSPACE
C) BQP
D) NP-completo
- 7. A que é que o teorema de Cook-Levin está relacionado na teoria da complexidade computacional?
A) Algoritmos quânticos
B) NP-completude
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
|