Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

Material de Estudo 46: Ciência da Computação Teórica 
1. Qual das seguintes classes de complexidade computacional descreve problemas que 
podem ser resolvidos por um algoritmo determinístico em tempo polinomial? 
o a) P 
o b) NP 
o c) NP-completo 
o d) NP-difícil 
o e) Exponencial 
Resposta: a) P 
Justificativa: A classe P inclui problemas para os quais existe um algoritmo que os resolve em 
um tempo que cresce polinomialmente com o tamanho da entrada. 
2. Qual dos seguintes modelos de computação é usado para descrever a capacidade 
teórica de algoritmos e problemas computacionais? 
o a) Máquina de Turing 
o b) Autômato finito 
o c) Linguagem de programação 
o d) Circuito lógico 
o e) Banco de dados relacional 
Resposta: a) Máquina de Turing 
Justificativa: A Máquina de Turing é um modelo matemático abstrato que define a computação 
como uma sequência de operações em uma fita de dados, sendo fundamental na teoria da 
computabilidade. 
3. Qual dos seguintes problemas é considerado NP-completo, ou seja, é um dos 
problemas mais difíceis de resolver em tempo polinomial? 
o a) Ordenação de listas. 
o b) Busca em árvores binárias. 
o c) Caixeiro viajante. 
o d) Cálculo de fatoriais. 
o e) Busca binária. 
Resposta: c) Caixeiro viajante. 
Justificativa: O problema do caixeiro viajante envolve encontrar o menor caminho que visita 
todas as cidades uma única vez, sendo um problema clássico de otimização combinatória NP-
completo. 
4. Qual das seguintes áreas da ciência da computação teórica estuda a capacidade de 
algoritmos de aprender e melhorar seu desempenho com base em dados? 
o a) Teoria da computabilidade. 
o b) Teoria da complexidade computacional. 
o c) Aprendizado de máquina. 
o d) Teoria dos grafos. 
o e) Teoria dos autômatos. 
Resposta: c) Aprendizado de máquina. 
Justificativa: O aprendizado de máquina desenvolve algoritmos que podem aprender padrões e 
fazer previsões a partir de dados, sendo uma área interdisciplinar entre ciência da computação 
e estatística. 
5. Qual dos seguintes conceitos da teoria da computabilidade descreve a existência de 
problemas que não podem ser resolvidos por nenhum algoritmo? 
o a) Decidibilidade. 
o b) Indecidibilidade. 
o c) Completude. 
o d) Eficiência. 
o e) Otimização. 
Resposta: b) Indecidibilidade. 
Justificativa: A indecidibilidade refere-se à existência de problemas para os quais não existe um 
algoritmo que possa determinar se uma determinada entrada pertence ou não à solução do 
problema. 
6. Qual dos seguintes modelos de computação é usado para descrever a capacidade de 
reconhecimento de padrões em sequências de símbolos? 
o a) Máquina de Turing. 
o b) Autômato finito. 
o c) Linguagem de programação. 
o d) Circuito lógico. 
o e) Banco de dados relacional. 
Resposta: b) Autômato finito.

Mais conteúdos dessa disciplina