QUESTIONÁRIO PARA A PROVA 2 DE TEC

24/06/2008

Decidibilidade:

• Problemas decidíveis - o que é? dê exemplos de linguagens/problemas decidíveis.
  
• Problemas indecidíveis - o que é? dê exemplos de linguagens/problemas indecidíveis.
• Método da diagonalização - o que é? como funciona?
• O qué a cardinalidade de conjuntos? O que são conjuntos contáveis? O que são conjuntos incontáveis? Dê exemplos.
  
• Problema da parada - é indecidível? como se prova? qual a importância deste resultado?O que é (ou como se define) linguagem "co-Turing-reconhecível"?

Complexidade de Algoritmos:

• O que significa "análise do pior caso"?
• O que significa "análise do caso médio"?
• O que é considerado o "tempo de execução" (ou "complexidade de tempo") de um algoritmo/MT?
• O que é a classe P?
  
• Porque a classe P é relevante de um ponto de vista prático?
• O que é verificabilidade polinomial?
• Quando se pode afirmar que uma linguagem está em NP?