O que significa um processo sofrer preempção

1)Explique o que são algoritmos razoáveis e Não-razoáveis.
R= Razoáveis: Algoritmos limitados por um polinômio n elevado a k.(Problema tratáveis).
Não- Razoáveis: Algoritmos cujo tempo de execução é “acima de n elevado a K.(Problemas intratáveis).
2)O que são problemas tratáveis?
Se existir algum algoritmo de complexidade polinomial, então p é dito tratável; O problema tratável, sempre pode ser Resolvido por um processo automátiço,(computador).
3)Explique o que acontece quando o tamanho da Entrada aumenta, no problema da Torre de Hanói.
R= Cresce exponencialmente em função do Tamanho da
instância e existe a garantia da não Existência de algoritmos melhores.

4)Cite as funções de ordem Polinomial e as de Ordem Exponencial
O grau de polinômio é expresso através do maior Expoente natural entre os monômios que o formam.
R= Polinomial: O(1), O(log n),O(n) elevado a K.
Exponencial 2 elevado a n, n elevado n.
5)Descreva sobre o problema da parada (Halting Problem).
R= O problema da parada é um problema de decisão que pode ser enunciado da seguinte forma:
– Dadá uma descrição de um programa e uma Entrada finita, decida se o programa termina ou não.
6)Explique as diferenças dos problemas de Decisão, Configuração e Otimização
Decisão: Consiste Na verificação (decisão) da veracidade ou não de determinada questão pára o Problema (resposta SIM ou NÃO) – verificação da existência de determinada Solução.
Configuração: Consiste Na verificação da identificação de uma solução (segundo algum critério) pára o Problema – geração de uma solução (viável) pára o problema.
Otimização: Consiste Na verificação da existência e identificação da melhor (otimização) solução Possível, dentre as soluções viáveis pára o problema. 
7)Porque a Teoria da NP-Completude se baseia na Versão de Decisão dos problemas?
R= Um problema de otimização possui embutido Um problema de configuração que por sua vez possui embutido um problema de Decisão. Desta forma, se for comprovado que um problema de decisão é Intratável, também serão suas versões de avaliação e de otimização. Daí o fato De que toda a TEORIA DA NP-COMPLETUDE se baseia na VERSÃO DE DECISÃO dos Problemas.
8)O que significa dizer que um problema está na Classe P (Polinomial Time)? Cite Exemplos.
A classe P consiste nos problemas que podem Ser resolvidos em tempo polinomial, que são os próprios problemas tratáveis. Ex: Ordenação, busca, fatorial...
9)O que significa dizer que um problema está na Classe NP (Nondeterministic Polinomial Time)? Cite Exemplos.
R= A classe NP consiste nos problemas Que no seu melhor caso são resolvidos em tempo exponencial. SAT, Teorema de COOK...
10)Explique a questão formulada por Jack EDMONS.
R= Ele iguala um problema em P, a um em NP e diz que se for provada a sua pertinência, implica em dizer que todos os Algoritmos podem ser resolvidos em tempo polinomial.
11)Porquê Stephen COOK ganhou o prêmio Turing? Explique sua descoberta. 
R= Provou que existe um problema, o SAT Que se for encontrado um algoritmo polinomial pára o mesmo, prova-se que P=NP.
12)Supondo que algum pesquisador prove que P = NP, qual seria a consequência.
R =Isto Significa dizer que todos os problemas em NP podem ser reduzidos polinomialmente A SAT e, desta forma, se SAT puder ser resolvido em tempo polinomial (possuir algoritmo Eficiente) todo problema em NP também o será.

13) Supondo Que algum pesquisador prove que P ≠NP, qual seria a consequência.
R =Não há como Encontrar solução eficiente pára centenas de problemas.

14)Explique porque acredita-se que P ≠ NP.
R= Porque milhares de Pesquisadores já dedicaram horas ao problema nas últimas quatro décadas e não Obtiveram sucesso.

15)Quais são os dois passos necessários pára provar Que um determinado problema é NP-Completo?        
R= Pertencem a NP e são NP-difíceis.
1-Deve-se Elaborar um algoritmo não-determinístico que resolva tal problema em tempo Polinomial.
2- deve-se encontrar um problema Q em NP que seja Polinomialmente redutível a ele.

16)Explique o que é um algoritmo não-determinístico
R= É um algoritmo em que, dadá uma certa entrada pode ter Sáídas Diferentes em várias execuções. Um algoritmo é não-determinístico se ele é escrito em uma linguagem Não-determinística:
-Contém todos os comandos de uma linguagem regular;
-Contém um comando salto-nd(oráculo ou função NP_escolha()).

17)O que significa dizer que os problemas em P também Pertencem à classe NP?
R= Pois estes Algoritmos usam uma linguagem não-determinística, embora sem lançar mão do Comando salto-nd().

18) Formalmente, explique o que é um Redução Polinomial.
R= Formalmente, redução polinomial de um  problema R a um outro problema R, é um algoritmo polinomial que transforma uma instância x de R em Um instância y de R, de forma que:
R’(x)=“SIM” Se e somente se R(y)=“SIM”. 

19)Explique resumidamente o processo de prova que Um determinado problema ‘Prob’ é NP-Difícil.
R= Deve-se encontrar um problema em Np que seja Polinomialmente redutível a ele. (cuja transformação também deve ser em tempo polinomial).

20)Cite alguns exemplos de problemas NP-Completos.
R=
·SAT
·Hamilton Circuit
·Clique