Teoria da complexidade computacional
- 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) Aspectos psicológicos da interação homem-computador
C) Analisar os recursos necessários para resolver problemas computacionais
D) Conceção de hardware para computadores
- 2. Que notação é normalmente utilizada para indicar a complexidade dos algoritmos?
A) Letras gregas
B) Notação Big O
C) Código binário
D) Números romanos
- 3. Que classe de complexidade contém problemas de decisão que são eficientemente verificáveis?
A) PSPACE
B) NP
C) BPP
D) EXP
- 4. Qual é a classe de complexidade que representa os problemas mais difíceis em NP?
A) BPP
B) EXPTIME
C) P
D) NP-completo
- 5. O que significa "EXP" na teoria da complexidade computacional?
A) Expandido
B) Tempo exponencial
C) Exploratório
D) Perito
- 6. Que classe de complexidade é utilizada para classificar os problemas que podem ser resolvidos por um computador quântico em tempo polinomial?
A) PSPACE
B) NP-completo
C) ESPAÇO
D) BQP
- 7. A que é que o teorema de Cook-Levin está relacionado na teoria da complexidade computacional?
A) Computação paralela
B) Problema P vs NP
C) NP-completude
D) Algoritmos quânticos
- 8. Qual é o principal objetivo da teoria da complexidade computacional?
A) Construir supercomputadores
B) Para gerar números aleatórios
C) Para criar computadores mais rápidos
D) Classificar os problemas computacionais com base na sua dificuldade inerente
|