Material de Estudo-15

Prévia do material em texto

Material de Estudo 15: Ciência da Computação Teórica 
1. Um cientista da computação teórica está estudando a complexidade de algoritmos e 
como ela escala com o tamanho da entrada. Qual conceito fundamental da teoria da 
computação ele provavelmente analisará? 
o a) Linguagens formais. 
o b) Autômatos finitos. 
o c) Análise assintótica. 
o d) Máquinas de Turing. 
o e) Teoria da informação. 
Resposta: c) Análise assintótica. 
Justificativa: A análise assintótica é usada para descrever como o tempo de execução ou o 
espaço de memória de um algoritmo cresce com o tamanho da entrada, permitindo comparar 
a eficiência de diferentes algoritmos. 
2. Um cientista da computação teórica está investigando os limites do que pode ser 
computado por máquinas de Turing e quais problemas são inerentemente intratáveis. 
Qual conceito central da teoria da computação ele provavelmente analisará? 
o a) Linguagens formais. 
o b) Autômatos finitos. 
o c) Complexidade de tempo. 
o d) Decidibilidade. 
o e) Teoria da informação. 
Resposta: d) Decidibilidade. 
Justificativa: A decidibilidade refere-se à capacidade de determinar se um problema pode ser 
resolvido por um algoritmo em um tempo finito. 
3. Um cientista da computação teórica está estudando como as linguagens formais são 
usadas para descrever a sintaxe de linguagens de programação e como os 
compiladores analisam e traduzem o código-fonte. Qual conceito central da teoria da 
computação ele provavelmente analisará? 
o a) Gramáticas formais. 
o b) Autômatos finitos. 
o c) Complexidade de espaço. 
o d) Decidibilidade. 
o e) Teoria da informação. 
Resposta: a) Gramáticas formais. 
Justificativa: As gramáticas formais são usadas para descrever a sintaxe de linguagens de 
programação e são essenciais para a análise e tradução de código-fonte por compiladores. 
4. Um cientista da computação teórica está investigando como a teoria da informação é 
usada para quantificar a quantidade de informação contida em uma mensagem e como 
ela pode ser comprimida e transmitida de forma eficiente. Qual conceito central da 
teoria da computação ele provavelmente analisará? 
o a) Linguagens formais. 
o b) Autômatos finitos. 
o c) Complexidade de tempo. 
o d) Decidibilidade. 
o e) Entropia. 
Resposta: e) Entropia. 
Justificativa: A entropia é uma medida da quantidade de informação contida em uma 
mensagem e é um conceito central da teoria da informação. 
5. Um cientista da computação teórica está estudando como os autômatos finitos são 
usados para modelar sistemas com um número finito de estados e como eles podem 
ser usados para reconhecer padrões em sequências de entrada. Qual conceito central 
da teoria da computação ele provavelmente analisará? 
o a) Linguagens formais. 
o b) Autômatos finitos. 
o c) Complexidade de espaço. 
o d) Decidibilidade. 
o e) Teoria da informação. 
Resposta: b) Autômatos finitos. 
Justificativa: Os autômatos finitos são usados para modelar sistemas com um número finito de 
estados e são usados em várias aplicações, como reconhecimento de padrões e análise léxica.