terça-feira, 24 de junho de 2008

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?


Nenhum comentário:

Postar um comentário

Deixe seu comentário! Não uso verificação de palavras.

Receba as postagens deste blog por email