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.