Unidade 6 - Fundamentos de pensamento computacional

Prévia do material em texto

Unidade 7 - Teoria da complexidade computacional: Classes de problemas
1 - Os problemas de desisão são os mais utilizáveis no dia a dia. Porém, para determinar a carretude da conjectura P ≠ NP, constitui-se um problema de decisão que desafia os cientistas da computação e matemáticos desde seu surgimento. Levando em conta esse problema, considere as seguintes afirmativas.
I - Não há problema determinístico de tempo polinomial que solucione esse problema;
II - Existem apenas problemas não determinísticos para solucionar esse problema de decisão;
III - Existe um algoritmo determinístico de tempo polinomial para esse problema de decisão;
IV - Considerando-se, por exemplo, os algoritmos "retorne sim" e "retorne não", um deles será a solução para esse problema de decisão.
Quais alternativas estão corretas?
R: C. 
Somente as afirmativas III e IV estão corretas.
2 - Problemas decidíveis, porém difíceis, para os quais possivelmente não existe algoritmo que os resolvam em tempo polinomial, é denominado de:
R: B. 
intratável.
3 - Os problemas de decisão consistem na verificação (decisão) da veracidade ou não de determinada questão para o problema (o qual exige uma resposta SIM ou NAO).
Dentre as alternativas a seguir, qual está correta em se tratando de um exemplo de problema de decisão? 
R: B. 
Número composto.
4 - Na área de Informática, ou Ciência da Computação, costuma-se usar o termo busca ______ para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, logo, no melhor caso, o elemento a ser buscado é encontrado já na primeira tentativa da busca. No pior caso, o elemento a ser buscado se encontra na última posição, e são feitas N comparações, sendo N o número total de elementos.
A alternativa que melhor preenche a lacuna é:
E. 
busca linear.
5 - Para resolver um problema por meios computacionais, é necessário codificá-lo numa dada linguagem e escrever um algoritmo (um programa, nessa mesma linguagem), isto é, um método para resolver o problema num número finito de passos.
Um problema é ____ se existe um algoritmo polinomial que o resolva. Se todos os algoritmos conhecidos para resolver um problema forem exponenciais, o problema se diz ______.
A alternativa que preenche as lacuna de forma correta é?
R: A. 
tratável e intratável